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}$${\estilo de visualización k}$${\displaystyle a=(a_{1},a_{2},\puntosc ,a_{k})}$${\displaystyle 1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n}$${\estilo de visualización a,b}$${\displaystyle a_{i}=b_{i+1}}$$Estilo de visualización a_{i+1}=b_{i}}$${\displaystyle 1\leq i\leq k-1}$${\estilo de visualización k}$${\estilo de visualización n}$$Estilo de visualización G_{n,k}$${\displaystyle a\to b}$$Estilo de visualización 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}$

• Los ciclos impares tienen una longitud de al menos , en particular están libres de triángulos.$Estilo de visualización G_{n,k}$${\estilo de visualización 2k+1}$$Estilo de visualización 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}$$Estilo de visualización 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]$Estilo de visualización G_{n,3}$

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. $Estilo de visualización G_{n,2}$$Estilo de visualización K_{n}$${\estilo de visualización 1}$${\estilo de visualización n}$${\estilo de visualización 2}$$Estilo de visualización G_{n,2}$

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