Shift graph

In graph theory, the shift graph G_n,k for $n,k\in \mathbb{\mathbb{N}},n>2k>0$ is the graph whose vertices correspond to the ordered $k$-tuples $a=(a_1,a_2,\dots ,a_k)$ with $1\le a_1<a_2<\cdots <a_k\le 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\le i\le 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\le i\le 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\ge 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\ge 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 $k-1$ times.
• Further connections to the chromatic theory of graphs and digraphs have been established in.
• Shift graphs, in particular $G_{n,3}$ 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 $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.