Shift graph

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

Further facts about shift graphs

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

Representation of shift graphs

The line representation of a shift graph.

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