Ramsey's theorem
History and bounds

Similar to Ramsey's theorem, it is unclear a priori whether induced Ramsey numbers exist for every graph H. In the early 1970s, Erdős, Hajnal and Pósa, Deuber and Rödl independently proved that this is the case. However, the original proofs gave terrible bounds (e.g. 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 c such that every graph H on k vertices satisfies r (H) ≤ 2. If this conjecture is true, it would be optimal up to the constant 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

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 Kohayakawa, Prömel and Rödl, who proved the first almost-exponential bound of r (H) ≤ 2 for some constant c. Their approach was to consider a suitable random graph constructed on projective planes 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 colorings and the induced Ramsey problem on bounded degree graphs H.

Kohayakawa, Prömel and Rödl's bound remained the best general bound for a decade. In 2008, Fox and Sudakov provided an explicit construction for induced Ramsey numbers with the same bound. In fact, they showed that every (n, d,λ) -graph G with small λ and suitable d contains an induced monochromatic copy of any graph on k vertices in any coloring of edges of G in two colors. In particular, for some constant c, the Paley graph on n ≥ 2 vertices is such that all of its edge colorings in two colors contain an induced monochromatic copy of every k -vertex graph.

In 2010, Conlon, Fox and Sudakov were able to improve the bound to r (H) ≤ 2, which remains the current best upper bound for general induced Ramsey numbers. Similar to the previous work in 2008, they showed that every (n, d,λ) -graph G with small λ and edge density 1 ⁄ 2 contains an induced monochromatic copy of every graph on k vertices in any edge coloring in two colors. Currently, Erdős's conjecture that r (H) ≤ 2 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).
change_case:english_lowercase, startend:quotation