Editing Ramsey's theorem (section)

=== History and bounds ===

Similar to Ramsey's theorem, it is unclear a priori whether induced Ramsey numbers exist for every graph {{mvar|H}}. In the early 1970s, [[Paul Erdős|Erdős]], [[András Hajnal|Hajnal]] and [[Lajos Pósa (mathematician)|Pósa]], Deuber, and [[Vojtěch Rödl|Rödl]] independently proved that this is the case.<ref name=":0" /><ref name=":1" /><ref name=":2" /> However, the original proofs gave terrible bounds (e.g. [[Tower of twos|towers of twos]]) on the induced Ramsey numbers. It is interesting to ask if better bounds can be achieved. In 1974, [[Paul Erdős]] conjectured that there exists a constant {{mvar|c}} such that every graph {{mvar|H}} on {{mvar|k}} vertices satisfies {{math|''r''{{sub|ind}}(''H'') ≤ 2{{sup|''ck''}}}}.<ref>{{cite conference
| last1=Erdős | first1=P. | author-link1=Paul Erdős
| title=Problems and results on finite and infinite graphs
| book-title=Recent advances in graph theory (Proceedings of the Second Czechoslovak Symposium, Prague, 1974)
| publisher=Academia, Prague
| date=1975
| pages=183–192}}</ref> If this conjecture is true, it would be optimal up to the constant {{mvar|c}} because the complete graph achieves a lower bound of this form (in fact, it's the same as Ramsey numbers). However, this conjecture is still open as of now.

In 1984, Erdős and Hajnal claimed that they proved the bound<ref>{{cite journal |last1=Erdős |first1=Paul |title=On some problems in graph theory, combinatorial analysis and combinatorial number theory |journal=Graph Theory and Combinatorics |date=1984 |pages=1–17 |url=https://users.renyi.hu/~p_erdos/1984-11.pdf}}</ref>
:<math>r_{\text{ind}}(H) \le 2^{2^{k^{1+o(1)}}}.</math>
However, that was still far from the exponential bound conjectured by Erdős. It was not until 1998 when a major breakthrough was achieved by [[Yoshiharu Kohayakawa|Kohayakawa]], Prömel and Rödl, who proved the first almost-exponential bound of {{math|''r''{{sub|ind}}(''H'') ≤ 2{{sup|''ck''(log ''k''){{sup|2}}}}}} for some constant {{mvar|c}}. Their approach was to consider a suitable random graph constructed on [[projective plane]]s and show that it has the desired properties with nonzero probability. The idea of using random graphs on projective planes have also previously been used in studying Ramsey properties with respect to [[vertex coloring]]s and the induced Ramsey problem on bounded [[Degree (graph theory)|degree]] graphs {{mvar|H}}.<ref>{{Cite journal
| last1=Kohayakawa | first1=Y.
| last2=Prömel | first2=H.J.
| last3=Rödl | first3=V.
| date=1998
| title=Induced Ramsey Numbers
| url=https://www.cs.umd.edu/~gasarch/TOPICS/induced_ramsey/KSS.pdf
| journal=[[Combinatorica]]
| volume=18
| issue=3
| pages=373–404
| doi=10.1007/PL00009828 | doi-access=free}}</ref>

Kohayakawa, Prömel and Rödl's bound remained the best general bound for a decade. In 2008, [[Jacob Fox|Fox]] and [[Benny Sudakov|Sudakov]] provided an explicit construction for induced Ramsey numbers with the same bound.<ref name=":3">{{cite journal
| last1=Fox | first1=Jacob | author-link1=Jacob Fox
| last2=Sudakov | first2=Benny | author-link2=Benny Sudakov
| date=2008
| title=Induced Ramsey-type theorems
| journal=[[Advances in Mathematics]]
| volume=219
| issue=6
| pages=1771–1800
| doi=10.1016/j.aim.2008.07.009 | doi-access=free| arxiv=0706.4112
}}</ref> In fact, they showed that every [[Pseudorandom graph#Consequences of eigenvalue bounding|{{math|(''n'',''d'',λ)}}-graph]] {{mvar|G}} with small {{math|λ}} and suitable {{mvar|d}} contains an induced monochromatic copy of any graph on {{mvar|k}} vertices in any coloring of edges of {{mvar|G}} in two colors. In particular, for some constant {{mvar|c}}, the [[Paley graph]] on {{math|''n'' ≥ 2{{sup|''ck'' log{{sup|2}}''k''}}}} vertices is such that all of its edge colorings in two colors contain an induced monochromatic copy of every {{mvar|k}}-vertex graph.

In 2010, [[David Conlon|Conlon]], Fox and Sudakov were able to improve the bound to {{math|''r''{{sub|ind}}(''H'') ≤ 2{{sup|''ck'' log ''k''}}}}, which remains the current best upper bound for general induced Ramsey numbers.<ref>{{cite journal
| last1=Conlon | first1=David | author-link1=David Conlon
| last2=Fox | first2=Jacob | author-link2=Jacob Fox
| last3=Sudakov | first3=Benny | author-link3=Benny Sudakov
| title=On two problems in graph Ramsey theory
| date=2012
| arxiv=1002.0045
| journal=[[Combinatorica]]
| volume=32
| issue=5 | pages=513–535
| doi=10.1007/s00493-012-2710-3 | doi-access=free}}</ref> Similar to the previous work in 2008, they showed that every [[Pseudorandom graph#Consequences of eigenvalue bounding|{{math|(''n'',''d'',λ)}}-graph]] {{mvar|G}} with small {{math|λ}} and edge density {{math|{{frac|1|2}}}} contains an induced monochromatic copy of every graph on {{mvar|k}} vertices in any edge coloring in two colors. Currently, Erdős's conjecture that {{math|''r''{{sub|ind}}(''H'') ≤ 2{{sup|''ck''}}}} remains open and is one of the important problems in [[extremal graph theory]].

For lower bounds, not much is known in general except for the fact that induced Ramsey numbers must be at least the corresponding Ramsey numbers. Some lower bounds have been obtained for some special cases (see Special Cases).

It is sometimes quite difficult to compute the Ramsey number. Indeed, the inequalities
 2{{sup|''n/2''}} ≤ R(''K''{{sub|n}}, ''K''{{sub|n}}) ≤  2{{sup|''2n''}}
were proved by Erdos and Szekeres in 1947. <ref>{{Erdos, P. and Szekeres, G. (1947) Some remarks on the theory of graphs. ˝ Bull. Amer. Math. Soc. 53
292–294.}}</ref>