Off-Diagonal Induced Ramsey Numbers

arXiv:2611.06886 · math.CO · Submitted 2026-11-04 · Read on arXiv

math.CO

Submitted: 2026-11-04

Updated: 2026-11-04

Comments: 14 pages

License: http://creativecommons.org/licenses/by/4.0/

The gist: Given graphs F and H, the induced Ramsey number r ind(F,H) is the smallest integer n for which there exists a graph G on n vertices such that every red-blue colouring of E(G) contains either a blue…

Terminology

Abstract

Given graphs F and H, the induced Ramsey number r ind(F,H) is the smallest integer n for which there exists a graph G on n vertices such that every red-blue colouring of E(G) contains either a blue induced copy of F or a red induced copy of H. A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph F, this number is polynomial in v(H). We prove this conjecture, showing that there is an absolute constant C > 0 such that r ind(F,H) at most v(H) Cv(F) squared for all graphs F and H. The proof combines a variant of a random geometric construction of Kohayakawa, Prömel and Rödl with the hypergraph container method.

Sources

Related papers