Shift graph

In graph theory, the shift graph $G n, k$ for $n,k\in \mathbb {N} ,\ n>2k>0$ is the graph whose vertices correspond to the ordered $k$ -tuples $a=(a_{1},a_{2},\dotsc ,a_{k})$ with $1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n$ and where two vertices $a,b$ are adjacent if and only if $a_{i}=b_{i+1}$ or $a_{i+1}=b_{i}$ for all $1\leq i\leq k-1$ . Shift graphs are triangle-free, and for fixed $k$ their chromatic number tend to infinity with $n$ .^[1] It is natural to enhance the shift graph $G_{n,k}$ with the orientation $a\to b$ if $a_{i+1}=b_{i}$ for all $1\leq i\leq k-1$ . Let ${\overrightarrow {G}}_{n,k}$ be the resulting directed shift graph. Note that ${\overrightarrow {G}}_{n,2}$ is the directed line graph of the transitive tournament corresponding to the identity permutation. Moreover, ${\overrightarrow {G}}_{n,k+1}$ is the directed line graph of ${\overrightarrow {G}}_{n,k}$ for all $k\geq 2$ .

Further facts about shift graphs

Odd cycles of $G_{n,k}$ have length at least $2k+1$ , in particular $G_{n,2}$ is triangle free.
For fixed $k\geq 2$ the asymptotic behaviour of the chromatic number of $G_{n,k}$ is given by $\chi (G_{n,k})=(1+o(1))\log \log \cdots \log n$ where the logarithm function is iterated ${\displaystyle k-1}$ times.^[1]
Further connections to the chromatic theory of graphs and digraphs have been established in.^[2]
Shift graphs, in particular $G_{n,3}$ also play a central role in the context of order dimension of interval orders.^[3]

Representation of shift graphs

The shift graph $G_{n,2}$ is the line-graph of the complete graph $K_{n}$ in the following way: Consider the numbers from $1$ to $n$ ordered on the line and draw line segments between every pair of numbers. Every line segment corresponds to the $2$ -tuple of its first and last number which are exactly the vertices of $G_{n,2}$ . Two such segments are connected if the starting point of one line segment is the end point of the other.

Note: This seems false, since $\{1,2\}$ and $\{1,3\}$ will be non-adjacent. Someone should check this.

References

^ ^a ^b Erdős, P.; Hajnal, A. (1968), "On chromatic number of infinite graphs", Theory of Graphs (Proc. Colloq., Tihany, 1966) (PDF), New York: Academic Press, pp. 83–98, MR 0263693
^ Simonyi, Gábor; Tardos, Gábor (2011). "On directed local chromatic number, shift graphs, and Borsuk-like graphs". Journal of Graph Theory. 66: 65–82. arXiv:0906.2897. doi:10.1002/jgt.20494. S2CID 14215886.
^ Füredi, Z.; Hajnal, P.; Rödl, V.; Trotter, W. T. (1991). "Interval Orders and Shift Graphs". Sets, Graphs and Numbers. 60. Proc. Colloq. Math. Soc. Janos Bolyai: 297–313.

[infinite_graphs-1] Erdős, P.; Hajnal, A. (1968), "On chromatic number of infinite graphs", Theory of Graphs (Proc. Colloq., Tihany, 1966) (PDF), New York: Academic Press, pp. 83–98, MR 0263693

[2] Simonyi, Gábor; Tardos, Gábor (2011). "On directed local chromatic number, shift graphs, and Borsuk-like graphs". Journal of Graph Theory. 66: 65–82. arXiv:0906.2897. doi:10.1002/jgt.20494. S2CID 14215886.

[interval_orders-3] Füredi, Z.; Hajnal, P.; Rödl, V.; Trotter, W. T. (1991). "Interval Orders and Shift Graphs". Sets, Graphs and Numbers. 60. Proc. Colloq. Math. Soc. Janos Bolyai: 297–313.

[1]

[2]

[3]