Off-Diagonal Induced Ramsey Numbers
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality