# Shift graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Shift_graph
> Markdown URL: https://mediated.wiki/source/Shift_graph.md
> Source: https://en.wikipedia.org/wiki/Shift_graph
> Source revision: 1262149263
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [graph theory](/source/graph_theory), the '''shift graph''' {{math|''G''<sub>''n'',''k''</sub>}} for <math> n,k \in \mathbb{N},\ n > 2k > 0 </math> is the graph whose vertices correspond to the ordered <math>k</math>-tuples <math> a = (a_1, a_2, \dotsc, a_k)</math> with <math>1 \leq a_1 < a_2 < \cdots < a_k \leq n </math> and where two vertices <math> a, b </math> are adjacent if and only if <math>a_i = b_{i+1}</math> or <math>a_{i+1} = b_i</math> for all <math> 1 \leq i \leq k-1 </math>. Shift graphs are [triangle-free](/source/Triangle-free_graph), and for fixed <math>k</math> their [chromatic number](/source/Graph_coloring) tend to infinity with <math>n</math>.<ref name="infinite_graphs">{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Hajnal | first2 = A. | author2-link = András Hajnal
 | contribution = On chromatic number of infinite graphs
 | location = New York
 | mr = 0263693
 | pages = 83–98
 | publisher = Academic Press
 | title = Theory of Graphs (Proc. Colloq., Tihany, 1966)
 | url = http://www.renyi.hu/~p_erdos/1968-04.pdf
 | year = 1968}}</ref> It is natural to enhance the shift graph <math>G_{n,k}</math> with the orientation <math>a \to b</math> if <math>a_{i+1}=b_i</math> for all <math>1\leq i\leq k-1</math>. Let <math>\overrightarrow{G}_{n,k}</math> be the resulting directed shift graph.
Note that <math>\overrightarrow{G}_{n,2}</math> is the directed [line graph](/source/Line_graph) of the [transitive tournament](/source/Tournament_(graph_theory)) corresponding to the identity permutation. Moreover, <math>\overrightarrow{G}_{n,k+1}</math> is the directed line graph of <math>\overrightarrow{G}_{n,k}</math> for all <math>k \geq 2</math>.

==Further facts about shift graphs==
*Odd cycles of <math>G_{n,k}</math> have length at least <math>2k+1</math>, in particular <math>G_{n,2}</math> is triangle free.
*For fixed <math>k \geq 2</math> the asymptotic behaviour of the [chromatic number](/source/chromatic_number) of <math>G_{n,k}</math> is given by <math>\chi(G_{n,k}) = (1 + o(1))\log\log\cdots\log n </math> where the logarithm function is iterated <math>{\displaystyle k-1}</math> times.<ref name="infinite_graphs" />
*Further connections to the chromatic theory of graphs and digraphs have been established in.<ref>{{cite journal
| last1=Simonyi | first1=Gábor
| last2=Tardos | first2=Gábor | authorlink2=Gábor Tardos
| year=2011
| title=On directed local chromatic number, shift graphs, and Borsuk-like graphs
| journal=[Journal of Graph Theory](/source/Journal_of_Graph_Theory)
| volume = 66
| pages=65–82
| doi=10.1002/jgt.20494
| arxiv=0906.2897| s2cid=14215886
}}</ref>
*Shift graphs, in particular <math>G_{n,3}</math> also play a central role in the context of order dimension of interval orders.<ref name="interval_orders">{{cite journal
| last1=Füredi | first1=Z. | authorlink1=Zoltán Füredi
| last2=Hajnal | first2=P.
| last3=Rödl | first3=V. | authorlink3=Vojtěch Rödl
| last4=Trotter | first4=W. T. | authorlink4=William T. Trotter
| date=1991
| title=Interval Orders and Shift Graphs
| journal=Sets, Graphs and Numbers
| publisher=Proc. Colloq. Math. Soc. Janos Bolyai
| volume=60
| pages=297–313}}</ref>

==Representation of shift graphs==

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

==References==
{{Reflist}}

{{DEFAULTSORT:Shift Graphs}}
Category:Graph coloring

---
Adapted from the Wikipedia article [Shift graph](https://en.wikipedia.org/wiki/Shift_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Shift_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.