Gráfico de desplazamiento

En teoría de grafos , el grafo de desplazamiento G _{n , k} para es el grafo cuyos vértices corresponden a las -tuplas ordenadas con y donde dos vértices son adyacentes si y solo si o para todos . Los grafos de desplazamiento no tienen triángulos y para fijos su número cromático tiende a infinito con . ^[1] Es natural mejorar el grafo de desplazamiento con la orientación si para todos . Sea el grafo de desplazamiento dirigido resultante. Nótese que es el grafo de línea dirigida del torneo transitivo correspondiente a la permutación identidad. Además, es el grafo de línea dirigida de para todos . ${\displaystyle n,k\in \mathbb {N} ,\ n>2k>0}$ ${\displaystyle k}$ ${\displaystyle a=(a_{1},a_{2},\dotsc ,a_{k})}$ ${\displaystyle 1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n}$ ${\displaystyle a,b}$ ${\displaystyle a_{i}=b_{i+1}}$ ${\displaystyle a_{i+1}=b_{i}}$ ${\displaystyle 1\leq i\leq k-1}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle G_{n,k}}$ ${\displaystyle a\to b}$ ${\displaystyle a_{i+1}=b_{i}}$ ${\displaystyle 1\leq i\leq k-1}$ ${\displaystyle {\overrightarrow {G}}_{n,k}}$ ${\displaystyle {\overrightarrow {G}}_{n,2}}$ ${\displaystyle {\overrightarrow {G}}_{n,k+1}}$ ${\displaystyle {\overrightarrow {G}}_{n,k}}$ ${\displaystyle k\geq 2}$

Más datos sobre los gráficos de desplazamiento

• Los ciclos impares tienen una longitud de al menos , en particular están libres de triángulos. ${\displaystyle G_{n,k}}$ ${\displaystyle 2k+1}$ ${\displaystyle G_{n,2}}$
• Para fijo el comportamiento asintótico del número cromático de viene dado por donde la función logaritmo se itera veces. ^[1] ${\displaystyle k\geq 2}$ ${\displaystyle G_{n,k}}$ ${\displaystyle \chi (G_{n,k})=(1+o(1))\log \log \cdots \log n}$ ${\displaystyle {\displaystyle k-1}}$
• Se han establecido más conexiones con la teoría cromática de grafos y dígrafos en ^{[2] .}
• Los gráficos de desplazamiento, en particular, también juegan un papel central en el contexto de la dimensión de orden de los órdenes de intervalo. ^[3] ${\displaystyle G_{n,3}}$

Representación de gráficos de desplazamiento

La representación lineal de un gráfico de desplazamiento.

El gráfico de desplazamiento es el gráfico lineal del gráfico completo de la siguiente manera: considere los números de a ordenados en la línea y dibuje segmentos de línea entre cada par de números. Cada segmento de línea corresponde a la -tupla de su primer y último número que son exactamente los vértices de . Dos de estos segmentos están conectados si el punto inicial de un segmento de línea es el punto final del otro. ${\displaystyle G_{n,2}}$ ${\displaystyle K_{n}}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 2}$ ${\displaystyle G_{n,2}}$

Nota: Esto parece falso, ya que y no serán adyacentes. Alguien debería comprobarlo. ${\displaystyle \{1,2\}}$ ${\displaystyle \{1,3\}}$

Referencias

1. Erdős, P. ; Hajnal, A. (1968), "Sobre el número cromático de grafos infinitos", Teoría de grafos (Proc. Colloq., Tihany, 1966) (PDF) , Nueva York: Academic Press, págs. 83–98, MR  0263693
2. Simonyi, Gábor; Tardos, Gábor (2011). "Sobre números cromáticos locales dirigidos, grafos de desplazamiento y grafos tipo Borsuk". Journal of Graph Theory . 66 : 65–82. arXiv : 0906.2897 . doi :10.1002/jgt.20494. S2CID  14215886.
3. Füredi, Z. ; Hajnal, P.; Rödl, V. ; Trotter, WT (1991). "Órdenes de intervalo y gráficos de desplazamiento". Conjuntos, gráficos y números . 60 . Proc. Colloq. Math. Soc. Janos Bolyai: 297–313.