Shift graph

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

Further facts about shift graphs

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

Representation of shift graphs

The line representation of a shift graph.

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