WorksMathematics
Off-Diagonal Induced Ramsey Numbers
Abstract
Given graphs and , the induced Ramsey number is the smallest integer for which there exists a graph on vertices such that every red-blue colouring of contains either a blue induced copy of or a red induced copy of . A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph , this number is polynomial in . We prove this conjecture, showing that there is an absolute constant such that for all graphs and . The proof combines a variant of a random geometric construction of Kohayakawa, Prömel and Rödl with the hypergraph container method.
Introduction
The induced Ramsey number of a graph is the minimum number of vertices of a graph with the property that in every red-blue colouring of the edges of , there is an induced copy of all of whose edges are the same colour. These numbers were shown to be finite for all by Deuber [8], Erdős, Hajnal and Pósa [10], and Rödl [13], but the bounds given by these initial proofs were only double exponential (or worse) in the number of vertices of . Following significant improvements by Kohayakawa, Prömel and Rödl [12] in the 1990s, and by Conlon, Fox and Sudakov [7] in the 2010s, an exponential upper bound
for every graph with vertices was finally shown by Aragão, Campos, Dahia, Filipe and Marciano [1], confirming a conjecture of Erdős [9].
In this paper we will study the following natural asymmetric version of this question, which was first considered by Kohayakawa, Prömel and Rödl [12]. Given two graphs and , we write
if for every red-blue colouring of the edges of , there exists either a blue induced copy of (that is, an induced copy of in all of whose edges are blue), or a red induced copy of . The induced Ramsey number of the pair is
In particular, note that , the usual off-diagonal Ramsey number, since every clique in a graph is also an induced subgraph of .
Kohayakawa, Prömel and Rödl [12] proved that
BA and RF were supported by CNPq; MC was partially supported by Serrapilheira (grant R-2412-51283); and AK was supported by a Bolsa do IMPA.
for all graphs and with at least one edge, and moreover conjectured [12 Conjecture 2] that is bounded by a polynomial function of , for every fixed graph . That is, for each graph , there exists such that
for every graph . Our main result confirms this conjecture with .
Theorem 1.1. There exists an absolute constant such that
for all graphs and .
We also prove the following multicolour version of Theorem 1.1. Given graphs , let denote the smallest number of vertices of a graph with the property that every -colouring of contains an induced copy of in colour for some .
Theorem 1.2. There exists an absolute constant such that for every
for all graphs and with and .
The construction we will use to prove Theorems 1.1 and 1.2 is based on that of Kohayakawa, Prömel and Rödl [12], who proved the bound (1) by placing a random blow-up of in each line of a projective plane . Note that this graph has many induced copies of , since each pair of vertices is in a unique line of , so the copies do not interfere with one another. It is also not hard to show (see Observation 4.4) that in any red-blue colouring of a balanced blow-up of with no induced red copy of , the density of blue edges is at least . In [12], the authors used this fact to show that the blue graph is pseudorandom, and hence to embed in it.
Our strategy will have some high level similarities, but also two important changes. First, our host graph will be slightly different: instead of using a projective plane, we will place a random blow-up of in each line of , where . Working in a higher dimensional space will guarantee more randomness in our construction, which will be important in the proof.
The second change is that, instead of using a pseudorandom property to embed into the blue graph, we will exploit the randomness of the host graph and use the method of hypergraph containers. This method, developed independently by Balogh, Morris, and Samotij [2] and by Saxton and Thomason [15], has become a powerful and versatile tool for studying families of sets that avoid prescribed configurations; see [3, 14] for surveys.
The container method was first applied to induced Ramsey numbers by Conlon, Dellamonica, La Fleur, Rödl and Schacht [6], who used it to prove an upper bound for multicolour induced Ramsey numbers of uniform hypergraphs. Later, Balogh and Samotij [4] developed an efficient container theorem, which they used to give a short proof of a result of Fox and Sudakov [11] on multicolour induced Ramsey numbers of graphs. More recently, a new container theorem of Campos and Samotij [5] was the main tool used by Aragão, Campos, Dahia, Filipe and Marciano [1] to prove an exponential upper bound for diagonal induced Ramsey numbers.
Applying this method (more precisely, a container theorem from [5]) in our setting, we will be able to find a small family of ‘containers’ for pairs of graphs with no copy of in that is induced in , each of which contains few cliques (see Theorem 2.1). We will show, for each such container, that if there is also no induced copy of in the remaining edges of , then avoids a fixed set of edges of . The theorem will then follow easily by bounding the probability of this event and using a union bound over the choice of the container.
We remark that in order for this approach to work, we need to have at least (roughly) “bits” of randomness in our construction, in order to overcome the number of containers in the union bound. In [1, 4, 6], like in most applications of the hypergraph container method to graphs, this is achieved by choosing the edges (or hyperedges) independently at random. In our setting we instead achieve it by taking the dimension of our affine space to be larger than .
The rest of this paper is organised as follows. In § 2 we describe our construction and state the container theorem (Theorem 2.1) that we use to prove our main theorems. In § 3 we prove a simple supersaturation result (see Lemmas 3.1 and 3.2), and in § 4 we exploit the geometric structure of our construction to find a set containing many blue edges (see Lemma 4.1). In § 5 we prove Theorems 1.1 and 1.2, and in § 6 we ask whether the dependence on of the exponent in (2) can be improved from quadratic to linear. Finally, in Appendix A, we show how to deduce our container theorem from [5 Theorem D].
AI declaration and independent work: The proofs of Theorems 1.1 and 1.2 were developed by the authors without any use of AI tools, and the first draft of the proof was completed in May, 2026. The only use of AI tools in the writing was reviewing the final draft of the paper. On October 21st, 2026, an alternative proof of Theorem 1.1, using a different method, was posted to arXiv by Zhong, Kashima and Mao [16].
Preliminaries
In this section we introduce the random geometric construction used in the proof and explain how we will use the container method to bound the probability that there exists a colouring that avoids given monochromatic induced subgraphs. Throughout the proof we will let and , and assume that and , since otherwise the desired bound is trivial. When we may also assume that , by swapping the roles of and if necessary, and noting that for all .
The construction
Fix and let be a prime satisfying
and set
Let be the set of affine lines in . For each line , choose independently and uniformly at random a function
For distinct points , let be the unique affine line containing and . We now define a random graph on vertex set by setting
Thus, on each line , the graph induced by is a random blow-up of , where the parts are the fibres of .
The key container theorem
The key tool in our proof is the following container theorem, which is very similar to the one proved by Balogh and Samotij [4]. In Appendix A we will show how to deduce it from a container theorem of Campos and Samotij [5 Theorem D].
Theorem 2.1. Let and , and let be a graph with vertices. There exists a family of pairs of graphs satisfying
such that the following hold.
(a) For every pair of graphs with vertices for which there is no satisfying , there exists such that
(b) For every , there are at most copies of in .
Observe that if the graph admits a bad colouring, then the graph of blue edges does not contain any copies of which are induced in . By Theorem 2.1, it follows that there exists a container such that , , and the graph contains at most copies of . Our task will then be to show that
for some constant , which then easily implies that the event has sufficiently low probability that we may take a union bound over all the containers in .
The key point in considering is that this allows us to shift the perspective from induced copies of to cliques in . Then in case , we will be able to find many cliques in by using the pseudorandomness of and the fact is very dense. This will contradict Item (b) showing that for all containers we have .
Supersaturation
In this section we will prove a supersaturation lemma for -colourings of pseudorandom graphs. The proof is simple, but to warm ourselves up, let’s first prove it in the case , where the statement and proof are both a little easier to understand. Define
for each and .
Lemma 3.1. Let be a graph on vertices, and let and . If
for every with , then contains more than copies of .
Proof. Observe first that if (7) holds for a set , then the graph has more than vertices of degree at least . We may therefore construct ordered -cliques greedily, simply by choosing a vertex of degree at least in , where is the common neighbourhood of the vertices chosen so far. Since throughout the process, there are at least such vertices at each step. It follows that there are more than
ordered -cliques, and hence more than copies of , as claimed. □
For the proof of Theorem 1.2, we will instead need the following multicolour version of Lemma 3.1. Define
for each and , where .
Lemma 3.2. Let be a graph on vertices, and let and . If
for every with , then every -colouring of the edges of contains more than monochromatic copies of .
Proof. Note that if (9) holds for a set , then there is a colour such that the graph has more than vertices with degree at least in colour . We may therefore construct ordered left-coloured cliques of size greedily, simply by choosing such a vertex in each step, and intersecting with the colour neighbourhood of the chosen vertex. Since throughout the process, there are at least such vertices at each step, and we therefore obtain at least
ordered -cliques, where . Each of these -cliques contains at least one monochromatic copy of , and each is included in at most of the ordered -cliques, so it follows that there are more than monochromatic copies of , as claimed. □
Geometric lemmas
In this section we will prove the following lemma.
Lemma 4.1. With high probability, in every red-blue colouring of the edges of with no red induced copy of , we have
for every set of size .
To prove this, we will need two lemmas that exploit the geometric structure of our construction. The first of these says that every sufficiently large subset of has a large intersection with at least half of the lines in .
Lemma 4.2. For every set of size , we have
for at least half of the lines .
Proof. Let be a uniformly chosen random line, and observe that
and
Since and for every , it follows that
Therefore, by Chebyshev’s inequality, we obtain
as claimed, since .
Lemma 4.2 guarantees that every large subset of has substantial intersections with many lines. Together with the random choice of the maps , this will imply that large subsets span many edges of . This allows us to show that, with high probability, for many of these lines satisfying Lemma 4.2, the corresponding blow-up of is balanced even after restriction to a large set. To be precise, we have the following lemma.
Lemma 4.3. With high probability, for every set of size , at least lines satisfy
for every .
Proof. Fix a set of size , and let be the family of lines given by Lemma 4.2 applied to , so and
for every . Fix and , and observe that the random variable
has a binomial distribution with mean . By Chernoff’s inequality, it follows that
Taking a union bound over , we obtain
since is sufficiently large.
Now, recall that the random functions on distinct lines are independent. Therefore, by another Chernoff bound, we may bound the probability that (10) fails to hold for more than half of the lines in by
Since , a union bound over all choices of gives a bound on the probability that such a set exists of
as claimed. □
We next recall the following key observation from [12]. For the reader’s convenience, we give the short proof. Recall that we write to denote the -blow-up of .
Observation 4.4 (Lemma 13 of [12]). A red-blue colouring of with no red induced copy of contains at least blue edges.
Proof. There are transversal copies of in , and each must have at least one blue edge. Since each edge is contained in transversal copies of , the claim follows. □
Combining this observation with Lemma 4.3, we obtain the claimed lower bound on the density of blue edges in a large set of vertices.
Proof of Lemma 4.1. Let denote the event that the conclusion of Lemma 4.3 holds: that for every set of size , at least lines satisfy
for every . By Lemma 4.3, we may assume that holds.
Fix a red-blue colouring of the edges of with no red induced copy of , and a set of size . We claim that the desired bound
follows deterministically from the event . To prove this, let be the set of lines given by the event , so and (11) holds for every and every . For each and , choose a subset
and set
The construction of implies that : every pair with one endpoint in and the other in is an edge of exactly when .
By Observation 4.4, it follows that has at least blue edges. Since every pair of points lies on a unique line and , we conclude that
as claimed. □
Proof of the main theorems
In this section, we will prove Theorems 1.1 and 1.2. To do so, we will first apply Theorem 2.1 to find for each colouring of with no blue induced copy of and no red induced copy of a container pair .
We will then use Lemma 3.1 to show that there exists a large subset where is sparse. At the same time Lemma 4.1 will show that , and therefore , is dense in , which will imply an upper bound on . The final argument is then to union bound over pairs and use the property that .
Proof of Theorem 1.1. Let and be graphs with and . We may assume that and , and also that , since otherwise the claimed bound holds trivially. Set , define as in (6), and apply Theorem 2.1 to the graph with and . We obtain a family of pairs of graphs such that
and properties (a) and (b) in Theorem 2.1 hold.
Let be the random graph constructed in § 2, with , and suppose that there exists a red-blue colouring of with no blue induced copy of and no red induced copy of . Recall from Lemma 4.1 that with high probability we have
for every set of size in every red-blue colouring of the edges of with no red induced copy of . Since the graph of blue edges is induced -free in , property (a) of Theorem 2.1 implies that there exists such that
Set . We make the following claim.
Claim 5.1.
Proof of Claim 5.1. By Lemma 3.1 and property (b) of the container family , there exists a set with that contains at most edges of the graph . Noting that
since , it follows from (13) that
Since , at least of these edges are not contained in , and hence
by (14) and our choice of .
It now only remains to bound the probability of the event , and take a union bound over the choice of the container . To do so, we choose a maximal collection of non-edges of that are contained in pairwise distinct lines of . Since each line contains at most non-edges of , it follows from Claim 5.1 that
Now, recall from (5) that for each pair , we have
and therefore, by the definition (4) of ,
Since the maps are chosen independently for distinct lines, the events are independent whenever the pairs lie on distinct lines, so
Finally, taking a union bound over the family of containers, and recalling that (13) holds with high probability by Lemma 4.1, we deduce that
Now, since and , we have
since , and , and hence, by (12),
Moreover, since and , we have , and hence
Together with (15), this implies that
Thus with high probability, and hence, by (3), we have
as required. □
The proof of Theorem 1.2 is almost identical: we simply replace the application of Lemma 3.1 with an application of Lemma 3.2.
Proof of Theorem 1.2. Let and be graphs with and . We may assume that , that (by our assumption that ) and that . Set , define , where was defined in (8), and apply Theorem 2.1 to for each . We obtain families of containers, with
such that properties (a) and (b) in Theorem 2.1 hold for each (with respect to ).
Let be the random graph constructed in Section 2, and recall from Lemma 4.1 that with high probability we have
for every set of size and every red-blue colouring of the edges of with no red induced copy of . Suppose that there exists an -colouring of with no induced copy of in colour for each and no induced copy of in colour . By property (a) of Theorem 2.1, for each there exists a container such that
where denotes the set of edges of colour . We make the following claim.
Claim 5.2. Set . Then
for some .
Proof of Claim 5.2. Define to be the graph with vertex set and edge set
By Lemma 3.2 and property (b) of the container families , there exists with such that
Noting that
since , it follows from Lemma 4.1 that
where blue is the union of the colours in . Since , it follows that there exists such that at least of the edges of are not contained in , and hence
by (18) and our choice of .
It now only remains to bound the probability of the event , and take a union bound over the choice of the container . To do so, we choose a collection of non-edges of that are contained in pairwise distinct lines of , and calculate as in the proof of Theorem 1.1, to obtain
Taking a union bound over the families of containers, and recalling that (17) holds with high probability by Lemma 4.1, we deduce that
To bound , recall that , and note that , since . It follows that
since and , and therefore, by (16),
since . Noting that , since , it follows that
Together with (19), this implies that
Thus with high probability, and hence, by (3), we have
as required. □
Concluding remarks
We have proved that, for every fixed graph , the off-diagonal induced Ramsey number is polynomial in . This confirms the conjecture of Kohayakawa, Prömel, and Rödl in its qualitative form. Quantitatively, however, the dependence of the exponent on remains to be optimized: our argument gives
In particular whenever , the bound proved by Kohayakawa, Prömel, and Rödl is better than ours since they prove
A natural next problem is to then determine the correct dependence of the exponent on the fixed graph . This leads to the following question. Question 6.1. Is it true that
for all graphs and ?
If true, this would give the optimal form of the polynomial dependence on . In general the best lower bound on that we are aware of is just the usual Ramsey number . It would also be interesting to improve this lower bound.
Acknowledgements
The authors are grateful to Rob Morris for rewriting the article to improve the presentation and for pointing out how our proof could be generalized to more than two colours.
References
Proof of thm:containers
We will use the following container theorem of Campos and Samotij [5] to deduce Theorem 2.1.
Theorem A.1 ([5], Theorem D). Let be an -uniform hypergraph with a finite vertex set . For every , there exists a family and functions
such that:
(a) For each , we have .
(b) Each has at most elements.
(c) For every , there does not exist a hypergraph that satisfies
We will apply Theorem A.1 to the following hypergraph, which encodes induced copies of in a subgraph of . Let be a hypergraph with vertex set
and whose edges are the sets of the form
where is an arbitrary embedding. In other words, encodes all the possible induced copies of in a subgraph of . In particular, every pair of graphs on vertices for which there is no satisfying can be viewed as an independent set in considering the set
With these observations in mind, we are now ready to prove Theorem 2.1.
Proof of Theorem 2.1. Let and . For a set and , define
First we deal with the trivial case that . In this case we can take
the family of all independent sets of . Note that property (a) of Theorem 2.1 holds immediately, and for each there is no copy of in , since spans no edge, implying property (b) in Theorem 2.1. Moreover, we have
since .
We may now assume . Applying Theorem A.1 to the -uniform hypergraph , we obtain a family and functions
satisfying items (a)–(c) in Theorem A.1.
Then define
Fix a pair of graphs on vertices for which there is no satisfying . Note that the set
is an independent set in . By item (a) in Theorem A.1, there exists such that and . In particular, we must have
which proves property (a) of Theorem 2.1. Moreover, by item (b) in Theorem A.1 the size of the family can be bounded as
since and using that .
It remains to prove item (b) in Theorem 2.1. Given let
that is a hypergraph encoding copies of in . We have that is the number of copies of in , therefore we only need to show that .
Let and take some injective function such that , for each . Let , by item (c) in Theorem A.1, this hypergraph must satisfy
for some . First, we bound . Let be the unique integer satisfying . Thus,
where in the first inequality we use that for each there is some such that , and for the second we use that any pairs span at least vertices.
Now observe that
which implies
Then we obtain
Putting together (20) and (21) we obtain
using that and . This finishes the proof since
References
- [1]L. Aragão, M. Campos, G. Dahia, R. Filipe, and J. P. Marciano. An exponential upper bound for induced Ramsey numbers. arXiv:2509.22629, 2025. Version 2, 13 November 2025.arxiv.org/abs/2509.22629
- [2]J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. J. Amer. Math. Soc., 28:669–709, 2015.
- [3]J. Balogh, R. Morris, and W. Samotij. The method of hypergraph containers. In Proceedings of the International Congress of Mathematicians, Rio de Janeiro 2018, volume 4, pages 3077–3110. World Scientific, 2018.arxiv.org/abs/1801.04584
- [4]J. Balogh and W. Samotij. An efficient container lemma. Discrete Anal., 2020. Paper No. 17, 56 pp.arxiv.org/abs/1910.09208
- [5]M. Campos and W. Samotij. Towards an optimal hypergraph container lemma. Combinatorica, 46(3), 2026. Article 24.arxiv.org/abs/2408.06617
- [6]D. Conlon, D. Dellamonica, Jr., S. La Fleur, V. Rödl, and M. Schacht. A note on induced Ramsey numbers. In A Journey Through Discrete Mathematics, pages 357–366. Springer, 2017.DOI
- [7]D. Conlon, J. Fox, and B. Sudakov. On two problems in graph Ramsey theory. Combinatorica, 32:513–535, 2012.arxiv.org/abs/1002.0045
- [8]W. Deuber. Generalizations of Ramsey’s theorem. In Infinite and Finite Sets, Vol. I, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 323–332. North-Holland, Amsterdam, 1975.
- [9]P. Erdős. On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph theory and combinatorics (Cambridge, 1983), pages 1–17. Academic Press, London, 1984.
- [10]P. Erdős, A. Hajnal, and L. Pósa. Strong embeddings of graphs into colored graphs. In Infinite and Finite Sets, Vol. I, volume 10 of Colloquia Mathematica Societatis János Bolyai, pages 585–595. North-Holland, Amsterdam, 1975.
- [11]J. Fox and B. Sudakov. Density theorems for bipartite graphs and related Ramsey-type results. Combinatorica, 29(2):153–196, 2009.arxiv.org/abs/0707.4159
- [12]Y. Kohayakawa, H. J. Prömel, and V. Rödl. Induced Ramsey numbers. Combinatorica, 18:373–404, 1998.DOI
- [13]V. Rödl. The dimension of a graph and generalized Ramsey theorems. Master’s thesis, Charles University, Prague, 1973.
- [14]W. Samotij. Counting independent sets in graphs. European J. Combin., 48:5–18, 2015.arxiv.org/abs/1412.0940
- [15]D. Saxton and A. Thomason. Hypergraph containers. Invent. Math., 201:925–992, 2015.DOI
- [16]C. Zhong, M. Kashima, and Y. Mao. A solution to the kohayakawa–prömel–rödl conjecture, 2026.DOI