Integralidad de los modelos arco-circulares unitarios que son minimales

FRANCISCO J. SOULIGNAC; PABLO TERLISKY

La Plata

Workshop; VII Latin American Workshop on Cliques in Graphs; 2016

Un modelo \emph{arco-circular (CA)} es un par $\M=(C,\A)$ tal que $C$ un círculo y $\A$ una familia finita de arcos de $C$.  Suponemos que $C$ tiene un punto especial, denotado por $0$; cuando $0$ no pertenece a ningún arco de $\A$, decimos que $\M$ es de  \emph{intervalos (IG)}. Los modelos \emph{UCA} y \emph{UIG} se corresponden a los modelos CA e IG cuyos arcos tienen todos la misma longitud, respectivamente.Dos modelos CA son \emph{equivalentes} cuando los extremos de sus arcos aparecen en el mismo orden en un recorrido de sus círculos desde $0$.Un modelo IG $\M$ es $(\ell, d)$-IG cuando los arcos tienen longitud $\ell > 0$ y cada par de extremos está a distancia al menos $d > 0$.  %Fijado $d$, existe un valor mínimo $\ell'$ tal que $\M$ es equivalente a un modelo $(\ell', d)$-IG.  Decimos que $\M$ es \emph{$(\infty,d)$-minimal} cuando, para todo modelo $(\ell', d)$-IG $\M'$ equivalente, ocurre que: 1.\ $\ell \leq \ell'$ y 2.\ $s_i \leq s_i'$ para $1 \leq i \leq n$, donde $s_i$ (resp.\ $s_i'$) es la posición del $i$-ésimo extremo de $\M$ (resp.\ $\M'$) desde $0$.  Esta definición fue propuesta en 1990 por Pirlot, quien demostró que (a) todo modelo UIG $\M$ es equivalente a un modelo $(\infty,d)$-minimal y (b) $\ell$ es múltiplo de $d$ cuando $\M$ es $(\infty,d)$-minimal.  Un modelo CA $\M$ es $(c, \ell, d)$-CA cuando el círculo tiene circunferencia $c > 0$, los arcos tienen longitud $\ell > 0$ y los extremos están a distancia al menos $d > 0$.  Teniendo en cuenta que el punto $0$ no juega ningún rol en los modelos CA, decimos que $\M$ es \emph{$d$-minimal} cuando, para todo modelo $(c', \ell', d)$-CA equivalente, 1.\ $\ell \leq \ell'$ y 2.\ $c \leq c'$.  Vale notar que todo modelo PIG $(\infty,d)$-minimal es $d$-minimal; la recíproca es falsa.  El término $d$-minimal fue propuesto por Soulignac para demostrar que todo modelo UCA es equivalente a un modelo $d$-minimal y conjeturar que $\ell$ y $c$ son múltiplos de $d$.   En este trabajo demostramos esta conjetura, a la vez que obtenemos algoritmos más eficientes para encontrar modelos $d$-minimales.