Shift graph explained

In graph theory, the shift graph for

n,k \in N , n > 2 k > 0 is the graph whose vertices correspond to the ordered k -tuples a = (a _{1,} a _{2,} ... c, a _{k)} with 1 \leq a _{1} < a _{2} < … < 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 . 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 2 k +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 )) loglog … log n where the logarithm function is iterated {\displaystyle k -1 } times.

• Further connections to the chromatic theory of graphs and digraphs have been established in.^[1]
• Shift graphs, in particular

G _{n,3} also play a central role in the context of order dimension of interval orders.^[2]

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.

Notes and References

1. Simonyi . Gábor. Tardos . Gábor . Gábor Tardos. 2011. On directed local chromatic number, shift graphs, and Borsuk-like graphs. Journal of Graph Theory. 66. 65–82. 10.1002/jgt.20494. 0906.2897. 14215886.
2. Füredi . Z. . Zoltán Füredi. Hajnal . P.. Rödl . V. . Vojtěch Rödl. Trotter . W. T. . William T. Trotter. 1991. Interval Orders and Shift Graphs. Sets, Graphs and Numbers. Proc. Colloq. Math. Soc. Janos Bolyai. 60. 297–313.