Editing Ramsey's theorem (section)

=== Generalizations ===
Similar to Ramsey numbers, we can generalize the notion of induced Ramsey numbers to hypergraphs and multicolor settings.

==== More colors ====
We can also generalize the induced Ramsey's theorem to a multicolor setting. For graphs {{math|''H''{{sub|1}}, ''H''{{sub|2}}, …, ''H{{sub|r}}''}}, define {{math|''r''{{sub|ind}}(''H''{{sub|1}}, ''H''{{sub|2}}, …, ''H{{sub|r}}'')}} to be the minimum number of vertices in a graph {{mvar|G}} such that, given any coloring of the edges of {{mvar|G}} into {{mvar|r}} colors, there exists an {{mvar|i}} such that {{math|1 ≤ ''i'' ≤ ''r''}} and such that {{mvar|G}} contains an induced subgraph isomorphic to {{mvar|H{{sub|i}}}} whose edges are all colored in the {{mvar|i}}-th color. Let {{math|1=''r''{{sub|ind}}(''H'';''q'') := ''r''{{sub|ind}}(''H'', ''H'', …, ''H'')}} ({{mvar|q}} copies of {{mvar|H}}).

It is possible to derive a bound on {{math|''r''{{sub|ind}}(''H'';''q'')}} which is approximately a [[Tower of twos|tower of two]] of height {{math|~ log ''q''}} by iteratively applying the bound on the two-color case. The current best known bound is due to Fox and Sudakov, which achieves {{math|''r''{{sub|ind}}(''H'';''q'') ≤ 2{{sup|''ck''{{sup|3}}}}}}, where {{mvar|k}} is the number of vertices of {{mvar|H}} and {{mvar|c}} is a constant depending only on {{mvar|q}}.<ref>{{cite journal
| last1=Fox | first1=Jacob | author-link1=Jacob Fox
| last2=Sudakov | first2=Benny | author-link2=Benny Sudakov
| arxiv=0707.4159v2
| title=Density theorems for bipartite graphs and related Ramsey-type results
| journal=[[Combinatorica]]
| volume=29
| pages=153–196
| year=2009
| issue=2 | doi=10.1007/s00493-009-2475-5 | doi-access=free}}</ref>

==== Hypergraphs ====
We can extend the definition of induced Ramsey numbers to {{mvar|d}}-uniform hypergraphs by simply changing the word ''graph'' in the statement to ''hypergraph''. Furthermore, we can define the multicolor version of induced Ramsey numbers in the same way as the previous subsection.

Let {{mvar|H}} be a {{mvar|d}}-uniform hypergraph with {{mvar|k}} vertices.  Define the tower function {{math|''t{{sub|r}}''(''x'')}} by letting {{math|1=''t''{{sub|1}}(''x'') = ''x''}} and for {{math|''i'' ≥ 1}}, {{math|1=''t''{{sub|''i''+1}}(''x'') = 2{{sup|''t{{sub|i}}''(''x'')}}}}. Using the hypergraph container method, Conlon, Dellamonica, La Fleur, Rödl and Schacht were able to show that for {{math|''d'' ≥ 3, ''q'' ≥ 2}}, {{math|''r''{{sub|ind}}(''H'';''q'') ≤ ''t{{sub|d}}''(''ck'')}} for some constant {{mvar|c}} depending on only {{mvar|d}} and {{mvar|q}}. In particular, this result mirrors the best known bound for the usual Ramsey number when {{math|1=''d'' = 3}}.<ref>{{cite book
| last1=Conlon | first1=David | author-link1=David Conlon
| last2=Dellamonica Jr. | first2=Domingos
| last3=La Fleur | first3=Steven
| last4=Rödl | first4=Vojtěch | author-link4=Vojtěch Rödl
| last5=Schacht | first5=Mathias
| arxiv=1601.01493
| chapter=A note on induced Ramsey numbers
| date=2017
| title=A Journey Through Discrete Mathematics
| pages=357–366 | editor-last1=Loebl | editor-first1=Martin
| editor-last2=Nešetřil | editor-first2=Jaroslav | editor-link2=Jaroslav Nešetřil
| editor-last3=Thomas | editor-first3=Robin | editor-link3=Robin Thomas (mathematician)
| publisher=Springer, Cham
| doi=10.1007/978-3-319-44479-6_13 | isbn=978-3-319-44478-9 | doi-access=free}}</ref>