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$. 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.
• 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.