Editing Ramsey's theorem (section)

=== Special cases ===
While the general bounds for the induced Ramsey numbers are exponential in the size of the graph, the behaviour is much different on special classes of graphs (in particular, sparse ones). Many of these classes have induced Ramsey numbers polynomial in the number of vertices.

If {{mvar|H}} is a [[Cycle (graph theory)|cycle]], [[Path (graph theory)|path]] or [[Star (graph theory)|star]] on {{mvar|k}} vertices, it is known that {{math|''r''{{sub|ind}}(''H'')}} is linear in {{mvar|k}}.<ref name=":3" />

If {{mvar|H}} is a [[Tree (graph theory)|tree]] on {{mvar|k}} vertices, it is known that {{math|1=''r''{{sub|ind}}(''H'') = ''O''(''k''{{sup|2}} log{{sup|2}}''k'')}}.<ref>{{cite book
| last1=Beck | first1=József
| date=1990
| chapter=On Size Ramsey Number of Paths, Trees and Circuits. II
| title=Mathematics of Ramsey Theory
| editor-last1=Nešetřil | editor-first1=J.
| editor-last2=Rödl | editor-first2=V.
| series=Algorithms and Combinatorics
| volume=5
| pages=34–45
| publisher=Springer, Berlin, Heidelberg
| doi=10.1007/978-3-642-72905-8_4 | isbn=978-3-642-72907-2
| doi-access=free}}</ref> It is also known that {{math|''r''{{sub|ind}}(''H'')}} is [[Big O notation#Family of Bachmann–Landau notations|superlinear]] (i.e.  {{math|1=''r''{{sub|ind}}(''H'') = ω(''k'')}}). Note that this is in contrast to the usual Ramsey numbers, where the [[Burr–Erdős conjecture]] (now proven) tells us that {{math|''r''(''H'')}} is linear (since trees are 1-[[Degeneracy (graph theory)|degenerate]]).

For graphs {{mvar|H}} with number of vertices {{mvar|k}} and bounded degree {{math|Δ}}, it was conjectured that {{math|''r''{{sub|ind}}(''H'') ≤ ''cn''{{sup|''d''(Δ)}}}}, for some constant {{mvar|d}} depending only on {{math|Δ}}. This result was first proven by Łuczak and Rödl in 1996, with {{math|''d''(Δ)}} growing as a [[tower of twos]] with height {{math|''O''(Δ{{sup|2}})}}.<ref>{{Cite journal
| last1=Łuczak | first1=Tomasz
| last2=Rödl | first2=Vojtěch
| date=March 1996
| title=On induced Ramsey numbers for graphs with bounded maximum degree
| journal=[[Journal of Combinatorial Theory]]
| series=Series B
| volume=66
| issue=2
| pages=324–333
| doi=10.1006/jctb.1996.0025 | doi-access=free}}</ref> More reasonable bounds for {{math|''d''(Δ)}} were obtained since then. In 2013, Conlon, Fox and Zhao showed using a [[Graph removal lemma#Graph counting lemma|counting lemma]] for sparse [[pseudorandom graph]]s that {{math|''r''{{sub|ind}}(''H'') ≤ ''cn''{{sup|2Δ+8}}}}, where the exponent is best possible up to constant factors.<ref>{{cite journal
| last1=Conlon | first1=David | author-link1=David Conlon
| last2=Fox | first2=Jacob | author-link2=Jacob Fox
| last3=Zhao | first3=Yufei
| title=Extremal results in sparse pseudorandom graphs
| journal=[[Advances in Mathematics]]
| volume=256
| date=May 2014
| pages=206–29
| arxiv=1204.6645
| doi=10.1016/j.aim.2013.12.004 | doi-access=free}}</ref>