betaFeedback

WorksMathematics

Off-Diagonal Induced Ramsey Numbers

Abstract

Given graphs FF and HH, the induced Ramsey number rind(F,H)r_{\mathrm{ind}}(F,H) is the smallest integer nn for which there exists a graph GG on nn vertices such that every red-blue colouring of E(G)E(G) contains either a blue induced copy of FF or a red induced copy of HH. A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph FF, this number is polynomial in v(H)v(H). We prove this conjecture, showing that there is an absolute constant C>0C > 0 such that rind(F,H)≤v(H)Cv(F)2r_{\mathrm{ind}}(F,H) \leq v(H)^{Cv(F)^2} for all graphs FF and HH. 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 rind(H)r_{\mathrm{ind}}(H) of a graph HH is the minimum number of vertices of a graph GG with the property that in every red-blue colouring of the edges of GG, there is an induced copy of HH all of whose edges are the same colour. These numbers were shown to be finite for all HH 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 HH. 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

rind(H)≤2O(k)r_{\mathrm{ind}}(H) \leq2^{O(k)}

for every graph HH with kk 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 FF and HH, we write

G→ind(F,H)G \xrightarrow{\mathrm{ind}} (F,H)

if for every red-blue colouring of the edges of GG, there exists either a blue induced copy of FF (that is, an induced copy of FF in GG all of whose edges are blue), or a red induced copy of HH. The induced Ramsey number of the pair (F,H)(F,H) is

rind(F,H)=min⁡{v(G):G→ind(F,H)}.r_{\mathrm{ind}}(F,H) = \min\{v(G) : G \xrightarrow{\mathrm{ind}} (F,H)\}.

In particular, note that rind(Ks,Kt)=R(s,t)r_{\mathrm{ind}}(K_s,K_t) = R(s,t), the usual off-diagonal Ramsey number, since every clique in a graph GG is also an induced subgraph of GG.

Kohayakawa, Prömel and Rödl [12] proved that

rind(F,H)≤v(H)O(v(F)log⁡χ(H))(1)r_{\mathrm{ind}}(F,H) \leq v(H)^{O(v(F)\log\chi(H))} \tag*{(1)}

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 FF and HH with at least one edge, and moreover conjectured [12 Conjecture 2] that rind(F,H)r_{\mathrm{ind}}(F,H) is bounded by a polynomial function of v(H)v(H), for every fixed graph FF. That is, for each graph FF, there exists C(F)>0C(F)>0 such that

rind(F,H)≤v(H)C(F)r_{\mathrm{ind}}(F,H) \le v(H)^{C(F)}

for every graph HH. Our main result confirms this conjecture with C(F)=O(v(F)2)C(F)=O(v(F)^2).

Theorem 1.1. There exists an absolute constant C>0C>0 such that

rind(F,H)≤v(H)Cv(F)2(2)r_{\mathrm{ind}}(F,H) \le v(H)^{Cv(F)^2} \tag*{(2)}

for all graphs FF and HH.

We also prove the following multicolour version of Theorem 1.1. Given graphs F1,…,FrF_1,\ldots,F_r, let rind(F1,…,Fr)r_{\mathrm{ind}}(F_1,\ldots,F_r) denote the smallest number of vertices of a graph GG with the property that every rr-colouring of E(G)E(G) contains an induced copy of FiF_i in colour ii for some i∈[r]i\in[r].

Theorem 1.2. There exists an absolute constant C>0C>0 such that for every r∈Nr\in\mathbb{N}

rind(F1,…,Fr,H)≤v(H)Cr2s2r_{\mathrm{ind}}(F_1,\ldots,F_r,H) \le v(H)^{Cr^2s^2}

for all graphs F1,…,FrF_1,\ldots,F_r and HH with v(F1)=⋯=v(Fr)=sv(F_1)=\cdots=v(F_r)=s and v(H)≥Crv(H)\ge Cr.

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 HH in each line of a projective plane PP. Note that this graph has many induced copies of HH, since each pair of vertices is in a unique line of PP, 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 HH with no induced red copy of HH, the density of blue edges is at least v(H)−2v(H)^{-2}. In [12], the authors used this fact to show that the blue graph is pseudorandom, and hence to embed FF in it.

Our strategy will have some high level similarities, but also two important changes. First, our host graph GG will be slightly different: instead of using a projective plane, we will place a random blow-up of HH in each line of FqdF_q^d, where d=4sd=4s. 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 FF 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 G′⊂GG'\subset G of graphs with no copy of FF in G′G' that is induced in GG, 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 HH in the remaining edges of GG, then GG avoids a fixed set of δn2\delta n^2 edges of KnK_n. 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) n2−1/sn^{2-1/s} “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 ss.

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 v(F)v(F) 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 v(H)=kv(H)=k and v(F1)=⋯=v(Fr)=sv(F_1)=\cdots=v(F_r)=s, and assume that s≥3s\ge3 and e(H)>0e(H)>0, since otherwise the desired bound is trivial. When r=1r=1 we may also assume that k≥sk\ge s, by swapping the roles of FF and HH if necessary, and noting that xy2≤yx2xy^2\le yx^2 for all x≥y≥3x\ge y\ge3.

The construction

Fix r∈Nr\in\mathbb{N} and let qq be a prime satisfying

k6r2s≤q≤2k6r2s,(3)k^{6r^2s}\le q\le2k^{6r^2s}, \tag*{(3)}

and set

d=4sandn=qd.d=4s \qquad\text{and}\qquad n=q^d.

Let L\mathcal{L} be the set of affine lines in Fqd\mathbb{F}_q^d. For each line L∈LL\in\mathcal{L}, choose independently and uniformly at random a function

πL:L→V(H).(4)\pi_L:L\to V(H). \tag*{(4)}

For distinct points x,y∈Fqdx,y\in\mathbb{F}_q^d, let LxyL_{xy} be the unique affine line containing xx and yy. We now define a random graph G=G(q,d,H)G=G(q,d,H) on vertex set Fqd\mathbb{F}_q^d by setting

xy∈E(G)⟺πLxy(x)πLxy(y)∈E(H).(5)xy\in E(G)\quad\Longleftrightarrow\quad\pi_{L_{xy}}(x)\pi_{L_{xy}}(y)\in E(H). \tag*{(5)}

Thus, on each line LL, the graph induced by GG is a random blow-up of HH, where the parts are the fibres of πL\pi_L.

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 n∈Nn \in\mathbb{N} and ε∈(0,1)\varepsilon\in(0,1), and let FF be a graph with s≥3s \ge3 vertices. There exists a family C⊂2E(Kn)×2E(Kn)\mathcal{C} \subset2^{E(K_n)} \times2^{E(K_n)} of pairs of graphs satisfying

∣C∣≤exp⁡(8s4⋅ε−2s+1n2−2s+1log⁡n)|\mathcal{C}| \le\exp\left(8s^4 \cdot\varepsilon^{-\frac{2}{s+1}} n^{2-\frac{2}{s+1}} \log n\right)

such that the following hold.

(a) For every pair of graphs G′⊂GG' \subset G with nn vertices for which there is no U⊂V(G)U \subset V(G) satisfying G′[U]=G[U]≅FG'[U] = G[U] \cong F, there exists (X,Y)∈C(X,Y) \in\mathcal{C} such that

Gc⊂XandG′⊂Y.G^{c} \subset X \qquad\text{and} \qquad G' \subset Y.

(b) For every (X,Y)∈C(X,Y) \in\mathcal{C}, there are at most εns\varepsilon n^s copies of KsK_s in X∩YX \cap Y.

Observe that if the graph GG admits a bad colouring, then the graph GB⊂GG_B \subset G of blue edges does not contain any copies of FF which are induced in GG. By Theorem 2.1, it follows that there exists a container (X,Y)∈C(X,Y) \in\mathcal{C} such that Gc⊂XG^c \subset X, GB⊂YG_B \subset Y, and the graph X∩YX \cap Y contains at most εns\varepsilon n^s copies of KsK_s. Our task will then be to show that

e(X)<(1−δ)(n2)e(X) < (1-\delta)\binom{n}{2}

for some constant δ>0\delta> 0, which then easily implies that the event Gc⊂XG^c \subset X has sufficiently low probability that we may take a union bound over all the containers in C\mathcal{C}.

The key point in considering X∩YX \cap Y is that this allows us to shift the perspective from induced copies of FF to cliques in X∩YX \cap Y. Then in case e(X)≥(1−δ)(n2)e(X) \ge(1-\delta)\binom{n}{2}, we will be able to find many cliques in X∩YX \cap Y by using the pseudorandomness of GB⊂YG_B \subset Y and the fact XX is very dense. This will contradict Item (b) showing that for all containers we have e(X)<(1−δ)(n2)e(X) < (1-\delta)\binom{n}{2}.

Supersaturation

In this section we will prove a supersaturation lemma for rr-colourings of pseudorandom graphs. The proof is simple, but to warm ourselves up, let’s first prove it in the case r=1r=1, where the statement and proof are both a little easier to understand. Define

ε(s,α)=α(s+12)s!(6)\varepsilon(s,\alpha)=\frac{\alpha^{\binom{s+1}{2}}}{s!} \tag*{(6)}

for each s∈Ns \in\mathbb{N} and α>0\alpha> 0.

Lemma 3.1. Let JJ be a graph on nn vertices, and let s∈Ns \in\mathbb{N} and α∈(0,1)\alpha\in(0,1). If

e(J[S])≥α∣S∣2(7)e(J[S]) \ge\alpha|S|^2 \tag*{(7)}

for every S⊂V(J)S \subset V(J) with ∣S∣≥αs−1n|S| \ge\alpha^{s-1}n, then JJ contains more than ε(s,α)ns\varepsilon(s,\alpha)n^s copies of KsK_s.

Proof. Observe first that if (7) holds for a set SS, then the graph J[S]J[S] has more than α∣S∣\alpha|S| vertices of degree at least α∣S∣\alpha|S|. We may therefore construct ordered ss-cliques greedily, simply by choosing a vertex of degree at least α∣S∣\alpha|S| in J[S]J[S], where SS is the common neighbourhood of the vertices chosen so far. Since ∣S∣≥αs−1n|S| \ge\alpha^{s-1}n throughout the process, there are at least α∣S∣\alpha|S| such vertices at each step. It follows that there are more than

∏i=1sαin=α(s+12)ns\prod_{i=1}^{s} \alpha^{i}n=\alpha^{\binom{s+1}{2}}n^{s}

ordered ss-cliques, and hence more than ε(s,α)ns\varepsilon(s,\alpha)n^{s} copies of KsK_s, as claimed. □

For the proof of Theorem 1.2, we will instead need the following multicolour version of Lemma 3.1. Define

ε(s,r,α)=α(t+12)ts(8)\varepsilon(s,r,\alpha)=\frac{\alpha^{\binom{t+1}{2}}}{t^{s}} \tag*{(8)}

for each r,s∈Nr,s\in\mathbb{N} and α>0\alpha>0, where t=r(s−1)+1t=r(s-1)+1.

Lemma 3.2. Let JJ be a graph on nn vertices, and let r,s∈Nr,s\in\mathbb{N} and α∈(0,1)\alpha\in(0,1). If

e(J[S])≥αr∣S∣2(9)e(J[S])\ge\alpha r|S|^{2} \tag*{(9)}

for every S⊂V(J)S\subset V(J) with ∣S∣≥αr(s−1)n|S|\ge\alpha^{r(s-1)}n, then every rr-colouring of the edges of JJ contains more than ε(s,r,α)ns\varepsilon(s,r,\alpha)n^{s} monochromatic copies of KsK_s.

Proof. Note that if (9) holds for a set SS, then there is a colour ii such that the graph J[S]J[S] has more than α∣S∣\alpha|S| vertices with degree at least α∣S∣\alpha|S| in colour ii. We may therefore construct ordered left-coloured cliques of size r(s−1)+1r(s-1)+1 greedily, simply by choosing such a vertex in each step, and intersecting SS with the colour ii neighbourhood of the chosen vertex. Since ∣S∣≥αr(s−1)n|S|\ge\alpha^{r(s-1)}n throughout the process, there are at least α∣S∣\alpha|S| such vertices at each step, and we therefore obtain at least

∏i=1r(s−1)+1αin=α(t+12)nt\prod_{i=1}^{r(s-1)+1}\alpha^{i}n=\alpha^{\binom{t+1}{2}}n^{t}

ordered tt-cliques, where t=r(s−1)+1t=r(s-1)+1. Each of these tt-cliques contains at least one monochromatic copy of KsK_s, and each KsK_s is included in at most tsnt−st^{s}n^{t-s} of the ordered tt-cliques, so it follows that there are more than ε(s,r,α)ns\varepsilon(s,r,\alpha)n^{s} monochromatic copies of KsK_s, 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 GG with no red induced copy of HH, we have

e(GB[S])≥∣S∣226k2e(G_B[S])\ge\frac{|S|^{2}}{2^{6}k^{2}}

for every set S⊂V(G)S\subset V(G) of size ∣S∣≥2k2qd−1|S|\ge2k^{2}q^{d-1}.

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 V(G)=FqdV(G)=\mathbb{F}_q^d has a large intersection with at least half of the lines in L\mathcal{L}.

Lemma 4.2. For every set S⊂V(G)S\subset V(G) of size ∣S∣≥8qd−1|S|\ge8q^{d-1}, we have

∣S∩L∣≥∣S∣2qd−1|S\cap L|\ge\frac{|S|}{2q^{d-1}}

for at least half of the lines L∈LL\in\mathcal{L}.

Proof. Let L∈LL \in\mathcal{L} be a uniformly chosen random line, and observe that

E[∣S∩L∣]=∣S∣qd−1\mathbb{E}[|S \cap L|] = \frac{|S|}{q^{d-1}}

and

Var⁡(∣S∩L∣)=∑x,y∈SP(x,y∈L)−q−2(d−1)∣S∣2.\operatorname{Var}(|S \cap L|) = \sum_{x,y \in S} \mathbb{P}(x,y \in L) - q^{-2(d-1)}|S|^2.

Since P(x∈L)=q−(d−1)\mathbb{P}(x \in L) = q^{-(d-1)} and P(x,y∈L)=1∣L∣≤q−2(d−1)\mathbb{P}(x,y \in L) = \frac{1}{|\mathcal{L}|} \leq q^{-2(d-1)} for every x≠yx \neq y, it follows that

Var⁡(∣S∩L∣)≤∣S∣qd−1.\operatorname{Var}(|S \cap L|) \leq\frac{|S|}{q^{d-1}}.

Therefore, by Chebyshev’s inequality, we obtain

P(∣S∩L∣<E[∣S∩L∣]2)≤4⋅Var⁡(∣S∩L∣)E[∣S∩L∣]2≤4qd−1∣S∣≤12,\mathbb{P}\left(|S \cap L| < \frac{\mathbb{E}[|S \cap L|]}{2}\right) \leq4 \cdot\frac{\operatorname{Var}(|S \cap L|)}{\mathbb{E}[|S \cap L|]^2} \leq\frac{4q^{d-1}}{|S|} \leq\frac{1}{2},

as claimed, since ∣S∣≥8qd−1|S| \geq8q^{d-1}.

Lemma 4.2 guarantees that every large subset of V(G)V(G) has substantial intersections with many lines. Together with the random choice of the maps πL\pi_L, this will imply that large subsets span many edges of GG. This allows us to show that, with high probability, for many of these lines L∈LL \in\mathcal{L} satisfying Lemma 4.2, the corresponding blow-up of HH 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 S⊂V(G)S \subset V(G) of size ∣S∣≥2k2qd−1|S| \geq2k^2q^{d-1}, at least ∣L∣/4|\mathcal{L}|/4 lines L∈LL \in\mathcal{L} satisfy

∣πL−1(u)∩S∣≥∣S∣4kqd−1(10)|\pi_L^{-1}(u) \cap S| \geq\frac{|S|}{4kq^{d-1}} \tag*{(10)}

for every u∈V(H)u \in V(H).

Proof. Fix a set S⊂V(G)S \subset V(G) of size ∣S∣≥2k2qd−1|S| \geq2k^2q^{d-1}, and let LS\mathcal{L}_S be the family of lines given by Lemma 4.2 applied to SS, so ∣LS∣≥∣L∣/2|\mathcal{L}_S| \geq|\mathcal{L}|/2 and

∣S∩L∣≥∣S∣2qd−1≥k2|S \cap L| \geq\frac{|S|}{2q^{d-1}} \geq k^2

for every L∈LSL \in\mathcal{L}_S. Fix L∈LSL \in\mathcal{L}_S and u∈V(H)u \in V(H), and observe that the random variable

Z=∣πL−1(u)∩S∣Z = |\pi_L^{-1}(u) \cap S|

has a binomial distribution with mean ∣S∩L∣/k|S \cap L|/k. By Chernoff’s inequality, it follows that

P(∣πL−1(u)∩S∣<∣S∣4kqd−1)≤P(∣πL−1(u)∩S∣<∣S∩L∣2k)≤e−k/8.\mathbb{P}\left(|\pi_L^{-1}(u) \cap S| < \frac{|S|}{4kq^{d-1}}\right) \leq\mathbb{P}\left(|\pi_L^{-1}(u) \cap S| < \frac{|S \cap L|}{2k}\right) \leq e^{-k/8}.

Taking a union bound over u∈V(H)u \in V(H), we obtain

P(min⁡u∈V(H)∣πL−1(u)∩S∣<∣S∣4kqd−1)≤k⋅e−k/8<14,\mathbb{P}\left(\min_{u \in V(H)}|\pi_L^{-1}(u) \cap S| < \frac{|S|}{4kq^{d-1}}\right) \leq k \cdot e^{-k/8} < \frac{1}{4},

since kk is sufficiently large.

Now, recall that the random functions πL\pi_L on distinct lines L∈LL \in\mathcal{L} 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 LS\mathcal{L}_S by

P(∣{L∈LS:min⁡u∈V(H)∣πL−1(u)∩S∣<∣S∣4kqd−1}∣≥∣LS∣2)≤exp⁡(−∣LS∣8).\mathbb{P}\left(\left|\left\{L \in\mathcal{L}_S : \min_{u \in V(H)}|\pi_L^{-1}(u) \cap S| < \frac{|S|}{4kq^{d-1}}\right\}\right| \geq\frac{|\mathcal{L}_S|}{2}\right) \leq\exp\left(-\frac{|\mathcal{L}_S|}{8}\right).

Since ∣LS∣≥12⋅q2d−2|\mathcal{L}_S| \ge\frac{1}{2}\cdot q^{2d-2}, a union bound over all choices of SS gives a bound on the probability that such a set SS exists of

2nexp⁡(−q2d−216)≤exp⁡(qd−q2d−216)=o(1),2^n\exp\left(-\frac{q^{2d-2}}{16}\right) \le\exp\left(q^d-\frac{q^{2d-2}}{16}\right)=o(1),

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 H(t)H(t) to denote the tt-blow-up of HH.

Observation 4.4 (Lemma 13 of [12]). A red-blue colouring of H(t)H(t) with no red induced copy of HH contains at least t2t^2 blue edges.

Proof. There are tkt^k transversal copies of HH in H(t)H(t), and each must have at least one blue edge. Since each edge is contained in tk−2t^{k-2} transversal copies of HH, 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 A\mathcal{A} denote the event that the conclusion of Lemma 4.3 holds: that for every set S⊂V(G)S \subset V(G) of size ∣S∣≥2k2qd−1|S| \ge2k^2q^{d-1}, at least ∣L∣/4|\mathcal{L}|/4 lines L∈LL \in\mathcal{L} satisfy

∣πL−1(u)∩S∣≥t=∣S∣4kqd−1(11)|\pi_L^{-1}(u)\cap S| \ge t=\frac{|S|}{4kq^{d-1}} \tag*{(11)}

for every u∈V(H)u \in V(H). By Lemma 4.3, we may assume that A\mathcal{A} holds.

Fix a red-blue colouring of the edges of GG with no red induced copy of HH, and a set S⊂V(G)S \subset V(G) of size ∣S∣≥2k2qd−1|S| \ge2k^2q^{d-1}. We claim that the desired bound

e(GB[S])≥∣S∣226k2e(G_B[S]) \ge\frac{|S|^2}{2^6k^2}

follows deterministically from the event A\mathcal{A}. To prove this, let LS⊂L\mathcal{L}_S \subset\mathcal{L} be the set of lines given by the event A\mathcal{A}, so ∣LS∣≥∣L∣/4|\mathcal{L}_S| \ge|\mathcal{L}|/4 and (11) holds for every L∈LSL \in\mathcal{L}_S and every u∈V(H)u \in V(H). For each L∈LSL \in\mathcal{L}_S and u∈V(H)u \in V(H), choose a subset

Tu⊂πL−1(u)∩Swith∣Tu∣=t,T_u \subset\pi_L^{-1}(u)\cap S \qquad\text{with}\qquad|T_u|=t,

and set

T=⋃u∈V(H)Tu.T=\bigcup_{u\in V(H)}T_u.

The construction of GG implies that G[T]=H(t)G[T]=H(t): every pair with one endpoint in TuT_u and the other in TvT_v is an edge of GG exactly when uv∈E(H)uv\in E(H).

By Observation 4.4, it follows that G[T]⊂G[S]G[T]\subset G[S] has at least t2t^2 blue edges. Since every pair of points lies on a unique line and ∣LS∣≥∣L∣/4≥q2d−2/4|\mathcal{L}_S|\ge|\mathcal{L}|/4\ge q^{2d-2}/4, we conclude that

e(GB[S])≥t2⋅∣LS∣≥(∣S∣4kqd−1)2⋅q2d−24=∣S∣226k2,e(G_B[S])\ge t^2\cdot|\mathcal{L}_S|\ge\left(\frac{|S|}{4kq^{d-1}}\right)^2\cdot\frac{q^{2d-2}}{4}=\frac{|S|^2}{2^6k^2},

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 GG with no blue induced copy of FF and no red induced copy of HH a container pair (X,Y)(X,Y).

We will then use Lemma 3.1 to show that there exists a large subset SS where X∩YX \cap Y is sparse. At the same time Lemma 4.1 will show that GBG_{\mathrm{B}}, and therefore Y⊃GBY \supset G_{\mathrm{B}}, is dense in SS, which will imply an upper bound on e(X)e(X). The final argument is then to union bound over pairs (X,Y)(X,Y) and use the property that Gc⊂XG^{\mathrm{c}} \subset X.

Proof of Theorem 1.1. Let FF and HH be graphs with v(F)=sv(F)=s and v(H)=kv(H)=k. We may assume that k≥s≥3k \ge s \ge3 and k≥27k \ge2^{7}, and also that e(H)>0e(H)>0, since otherwise the claimed bound holds trivially. Set α=k−3\alpha=k^{-3}, define ε=ε(s,α)\varepsilon=\varepsilon(s,\alpha) as in (6), and apply Theorem 2.1 to the graph FF with n=qdn=q^{d} and ε=ε(s,α)\varepsilon=\varepsilon(s,\alpha). We obtain a family C\mathcal{C} of pairs of graphs such that

∣C∣≤exp⁡(8s4ε−2s+1n2−2s+1log⁡n)(12)|\mathcal{C}| \le\exp\left(8s^{4}\varepsilon^{-\frac{2}{s+1}}n^{2-\frac{2}{s+1}}\log n\right) \tag*{(12)}

and properties (a) and (b) in Theorem 2.1 hold.

Let GG be the random graph constructed in § 2, with r=1r=1, and suppose that there exists a red-blue colouring of GG with no blue induced copy of FF and no red induced copy of HH. Recall from Lemma 4.1 that with high probability we have

e(GB[S])≥∣S∣226k2≥2α∣S∣2(13)e(G_{\mathrm{B}}[S]) \ge\frac{|S|^{2}}{2^{6}k^{2}} \ge2\alpha|S|^{2} \tag*{(13)}

for every set S⊂V(G)S \subset V(G) of size ∣S∣≥2k2qd−1|S| \ge2k^{2}q^{d-1} in every red-blue colouring of the edges of GG with no red induced copy of HH. Since the graph of blue edges GB⊂GG_{\mathrm{B}} \subset G is induced FF-free in GG, property (a) of Theorem 2.1 implies that there exists (X,Y)∈C(X,Y)\in\mathcal{C} such that

Gc⊂XandGB⊂Y.G^{\mathrm{c}} \subset X \qquad\text{and}\qquad G_{\mathrm{B}} \subset Y.

Set δ=α2s−1\delta=\alpha^{2s-1}. We make the following claim.

Claim 5.1.

e(X)≤(1−δ)(n2).e(X) \le(1-\delta)\binom{n}{2}.

Proof of Claim 5.1. By Lemma 3.1 and property (b) of the container family C\mathcal{C}, there exists a set S⊂V(G)S \subset V(G) with ∣S∣≥αs−1n|S| \ge\alpha^{s-1}n that contains at most α∣S∣2\alpha|S|^{2} edges of the graph X∩YX \cap Y. Noting that

∣S∣≥αs−1n=qdk3s−3≥2k2qd−1,(14)|S| \ge\alpha^{s-1}n=\frac{q^{d}}{k^{3s-3}} \ge2k^{2}q^{d-1}, \tag*{(14)}

since q≥k3sq \ge k^{3s}, it follows from (13) that

e(GB[S])≥2α∣S∣2.e(G_{\mathrm{B}}[S]) \ge2\alpha|S|^{2}.

Since GB⊂YG_{\mathrm{B}} \subset Y, at least α∣S∣2\alpha|S|^{2} of these edges are not contained in XX, and hence

e(X)≤(n2)−α∣S∣2≤(1−δ)(n2),e(X) \le\binom{n}{2}-\alpha|S|^{2}\le(1-\delta)\binom{n}{2},

by (14) and our choice of δ=α2s−1\delta=\alpha^{2s-1}.

It now only remains to bound the probability of the event Gc⊂XG^{c} \subset X, and take a union bound over the choice of the container (X,Y)(X,Y). To do so, we choose a maximal collection W⊂XcW \subset X^{c} of non-edges of XX that are contained in pairwise distinct lines of Fqd\mathbb{F}_{q}^{d}. Since each line contains at most (q2)\binom{q}{2} non-edges of XX, it follows from Claim 5.1 that

∣W∣≥δ(n2)(q2)−1≥δn2q2.|W| \ge\delta\binom{n}{2}\binom{q}{2}^{-1} \ge\frac{\delta n^{2}}{q^{2}}.

Now, recall from (5) that for each pair xy∈Wxy \in W, we have

xy∈E(G)⟺πLxy(x)πLxy(y)∈E(H),xy \in E(G) \quad\Longleftrightarrow\quad\pi_{L_{xy}}(x)\pi_{L_{xy}}(y) \in E(H),

and therefore, by the definition (4) of πLxy\pi_{L_{xy}},

P(xy∈E(G))=2e(H)k2≤1−1k.\mathbb{P}(xy \in E(G)) = \frac{2e(H)}{k^{2}} \le1-\frac{1}{k}.

Since the maps πL\pi_L are chosen independently for distinct lines, the events {xy∈E(G)}\{xy \in E(G)\} are independent whenever the pairs xyxy lie on distinct lines, so

P(Gc⊂X)≤P(W⊂G)≤(1−1k)δn2/q2≤exp⁡(−α2sn2q2).\mathbb{P}(G^{c} \subset X) \le\mathbb{P}(W \subset G) \le\left(1-\frac{1}{k}\right)^{\delta n^{2}/q^{2}} \le\exp\left(-\frac{\alpha^{2s}n^{2}}{q^{2}}\right).

Finally, taking a union bound over the family C\mathcal{C} of containers, and recalling that (13) holds with high probability by Lemma 4.1, we deduce that

P(G⟶ind(F,H))≤∣C∣⋅exp⁡(−α2sn2q2)+o(1).(15)\mathbb{P}\left(G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F,H)\right) \le|\mathcal{C}|\cdot\exp\left(-\frac{\alpha^{2s}n^{2}}{q^{2}}\right)+o(1). \tag*{(15)}

Now, since ε=α(s+1)/2/s!\varepsilon=\alpha^{(s+1)/2}/s! and n=q4sn=q^{4s}, we have

ε−2/(s+1)≤s2αsandn−2/(s+1)log⁡n≤4sq5,\varepsilon^{-2/(s+1)} \le\frac{s^{2}}{\alpha^{s}} \qquad\text{and}\qquad n^{-2/(s+1)}\log n \le\frac{4s}{q^{5}},

since s!≤ss+1s! \le s^{s+1}, log⁡q≤q\log q \le q and s≥3s \ge3, and hence, by (12),

log⁡∣C∣n2≤8s4ε−2/(s+1)n−2/(s+1)log⁡n≤25s7αsq5.\frac{\log|\mathcal{C}|}{n^{2}} \le8s^{4}\varepsilon^{-2/(s+1)}n^{-2/(s+1)}\log n \le\frac{2^{5}s^{7}}{\alpha^{s}q^{5}}.

Moreover, since q≥k4sq \ge k^{4s} and α=k−3\alpha=k^{-3}, we have q3α3s≥k3s≥26s7q^{3}\alpha^{3s} \ge k^{3s} \ge2^{6}s^{7}, and hence

log⁡∣C∣n2≤25s7αsq5≤α2s2q2.\frac{\log|\mathcal{C}|}{n^{2}} \le\frac{2^{5}s^{7}}{\alpha^{s}q^{5}} \le\frac{\alpha^{2s}}{2q^{2}}.

Together with (15), this implies that

P(G⟶ind(F,H))≤exp⁡(−α2sn22q2)+o(1)=o(1).\mathbb{P}\left(G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F,H)\right) \le\exp\left(-\frac{\alpha^{2s}n^{2}}{2q^{2}}\right)+o(1)=o(1).

Thus G⟶ind(F,H)G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F,H) with high probability, and hence, by (3), we have

rind(F,H)≤n=q4s≤24sk24s2≤k25s2,r_{\mathrm{ind}}(F,H) \le n=q^{4s}\le2^{4s}k^{24s^{2}}\le k^{25s^{2}},

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 F1,…,FrF_1,\ldots,F_r and HH be graphs with v(F1)=⋯=v(Fr)=sv(F_1)=\cdots=v(F_r)=s and v(H)=kv(H)=k. We may assume that s≥3s\ge3, that k≥r+27k\ge r+2^7 (by our assumption that v(H)≥Crv(H)\ge C_r) and that e(H)>0e(H)>0. Set α=r−1k−3\alpha=r^{-1}k^{-3}, define ε=r−1ε(s,r,α)\varepsilon=r^{-1}\varepsilon(s,r,\alpha), where ε(s,r,α)\varepsilon(s,r,\alpha) was defined in (8), and apply Theorem 2.1 to FiF_i for each i∈[r]i\in[r]. We obtain families C1,…,Cr\mathcal{C}_1,\ldots,\mathcal{C}_r of containers, with

∣Ci∣≤exp⁡(8s4ε−2s+1n2−2s+1log⁡n),(16)|\mathcal{C}_i|\le\exp\left(8s^4\varepsilon^{-\frac{2}{s+1}}n^{2-\frac{2}{s+1}}\log n\right), \tag*{(16)}

such that properties (a) and (b) in Theorem 2.1 hold for each Ci\mathcal{C}_i (with respect to FiF_i).

Let GG be the random graph constructed in Section 2, and recall from Lemma 4.1 that with high probability we have

e(GB[S])≥∣S∣226k2≥2αr∣S∣2(17)e(G_B[S])\ge\frac{|S|^2}{2^6k^2}\ge2\alpha r|S|^2 \tag*{(17)}

for every set S⊂V(G)S\subset V(G) of size ∣S∣≥2k2qd−1|S|\ge2k^2q^{d-1} and every red-blue colouring of the edges of GG with no red induced copy of HH. Suppose that there exists an (r+1)(r+1)-colouring of GG with no induced copy of FiF_i in colour ii for each i∈[r]i\in[r] and no induced copy of HH in colour r+1r+1. By property (a) of Theorem 2.1, for each i∈[r]i\in[r] there exists a container (Xi,Yi)∈Ci(X_i,Y_i)\in\mathcal{C}_i such that

Gc⊂XiandGi⊂Yi,G^c\subset X_i \qquad\text{and}\qquad G_i\subset Y_i,

where GiG_i denotes the set of edges of colour ii. We make the following claim.

Claim 5.2. Set δ=α2rs−1\delta=\alpha^{2rs-1}. Then

e(Xi)≤(1−δ)(n2)e(X_i)\le(1-\delta)\binom{n}{2}

for some i∈[r]i\in[r].

Proof of Claim 5.2. Define JJ to be the graph with vertex set V(G)V(G) and edge set

E(J)=⋃i=1rE(Xi∩Yi).E(J)=\bigcup_{i=1}^{r}E(X_i\cap Y_i).

By Lemma 3.2 and property (b) of the container families C1,…,Cr\mathcal{C}_1,\ldots,\mathcal{C}_r, there exists S⊂V(G)S\subset V(G) with ∣S∣≥αr(s−1)n|S|\ge\alpha^{r(s-1)}n such that

e(J[S])<αr∣S∣2.e(J[S])<\alpha r|S|^2.

Noting that

∣S∣≥αr(s−1)n=qd(rk3)r(s−1)≥2k2qd−1,(18)|S|\ge\alpha^{r(s-1)}n=\frac{q^d}{(rk^3)^{r(s-1)}}\ge2k^2q^{d-1}, \tag*{(18)}

since q≥k4rs2≥(rk3)rsq\ge k^{4r s^2}\ge(rk^3)^{rs}, it follows from Lemma 4.1 that

e(GB[S])≥2αr∣S∣2,e(G_B[S])\ge2\alpha r|S|^2,

where blue is the union of the colours in [r][r]. Since GB⊂Y1∪⋯∪YrG_B\subset Y_1\cup\cdots\cup Y_r, it follows that there exists i∈[r]i\in[r] such that at least α∣S∣2\alpha|S|^2 of the edges of YiY_i are not contained in XiX_i, and hence

e(Xi)≤(n2)−α∣S∣2≤(1−δ)(n2),e(X_i)\le\binom{n}{2}-\alpha|S|^2\le(1-\delta)\binom{n}{2},

by (18) and our choice of δ=α2rs−1\delta=\alpha^{2rs-1}.

It now only remains to bound the probability of the event Gc⊂XiG^c \subset X_i, and take a union bound over the choice of the container (Xi,Yi)(X_i,Y_i). To do so, we choose a collection W⊂XicW \subset X_i^c of δn2/q2\delta n^2/q^2 non-edges of XiX_i that are contained in pairwise distinct lines of Fqd\mathbb{F}_q^d, and calculate as in the proof of Theorem 1.1, to obtain

P(Gc⊂Xi)≤P(W⊂G)≤(1−1k)δn2/q2≤exp⁡(−α2rsn2q2).\mathbb{P}(G^c \subset X_i) \le\mathbb{P}(W \subset G) \le\left(1-\frac{1}{k}\right)^{\delta n^2/q^2} \le\exp\left(-\frac{\alpha^{2r}sn^2}{q^2}\right).

Taking a union bound over the families C1,…,Cr\mathcal{C}_1,\ldots,\mathcal{C}_r of containers, and recalling that (17) holds with high probability by Lemma 4.1, we deduce that

P(G⟶ind(F1,…,Fr,H))≤∑i=1r∣Ci∣⋅exp⁡(−α2rsn2q2)+o(1).(19)\mathbb{P}\left(G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F_1,\ldots,F_r,H)\right) \le\sum_{i=1}^{r}|\mathcal{C}_i|\cdot\exp\left(-\frac{\alpha^{2r}sn^2}{q^2}\right)+o(1). \tag*{(19)}

To bound ∣Ci∣|\mathcal{C}_i|, recall that ε=α(t+12)/(rts)\varepsilon=\alpha^{\binom{t+1}{2}}/(r t^s), and note that (t+12)≤r2s(s+1)/2\binom{t+1}{2}\le r^2s(s+1)/2, since t≤rst\le rs. It follows that

ε−2s+1≤(rs)2α2r2sandn−2s+1log⁡n≤4sq5,\varepsilon^{-\frac{2}{s+1}}\le\frac{(rs)^2}{\alpha^{2r^2s}} \qquad\text{and}\qquad n^{-\frac{2}{s+1}}\log n\le\frac{4s}{q^5},

since n=q4sn=q^{4s} and s≥3s\ge3, and therefore, by (16),

log⁡∣Ci∣n2≤8s4ε−2s+1n−2s+1log⁡n≤1α2r2sq5,\frac{\log|\mathcal{C}_i|}{n^2}\le8s^4\varepsilon^{-\frac{2}{s+1}}n^{-\frac{2}{s+1}}\log n\le\frac{1}{\alpha^{2r^2s}q^5},

since α=r−1k−3\alpha=r^{-1}k^{-3}. Noting that q3≥k18r2s≥2α−4r2sq^3\ge k^{18r^2s}\ge2\alpha^{-4r^2s}, since k≥rk\ge r, it follows that

log⁡∣Ci∣n2≤1α2r2sq5≤α2r2s2q2.\frac{\log|\mathcal{C}_i|}{n^2}\le\frac{1}{\alpha^{2r^2s}q^5}\le\frac{\alpha^{2r^2s}}{2q^2}.

Together with (19), this implies that

P(G⟶ind(F1,…,Fr,H))≤rexp⁡(−α2rsn22q2)+o(1)=o(1).\mathbb{P}\left(G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F_1,\ldots,F_r,H)\right)\le r\exp\left(-\frac{\alpha^{2r}sn^2}{2q^2}\right)+o(1)=o(1).

Thus G⟶ind(F1,…,Fr,H)G \mathrel{\overset{\mathrm{ind}}{\longrightarrow}} (F_1,\ldots,F_r,H) with high probability, and hence, by (3), we have

rind(F1,…,Fr,H)≤n=q4s≤24sk24r2s2≤k25r2s2,r_{\mathrm{ind}}(F_1,\ldots,F_r,H)\le n=q^{4s}\le2^{4s}k^{24r^2s^2}\le k^{25r^2s^2},

as required. □

Concluding remarks

We have proved that, for every fixed graph FF, the off-diagonal induced Ramsey number rind(F,H)r_{\mathrm{ind}}(F,H) is polynomial in v(H)v(H). This confirms the conjecture of Kohayakawa, Prömel, and Rödl in its qualitative form. Quantitatively, however, the dependence of the exponent on v(F)v(F) remains to be optimized: our argument gives

rind(F,H)≤v(H)O(v(F)2).r_{\mathrm{ind}}(F,H)\le v(H)^{O(v(F)^2)}.

In particular whenever v(F)≥log⁡v(H)v(F)\ge\log v(H), the bound proved by Kohayakawa, Prömel, and Rödl is better than ours since they prove

rind(F,H)≤v(H)O(v(F)log⁡v(H)).r_{\mathrm{ind}}(F,H)\le v(H)^{O(v(F)\log v(H))}.

A natural next problem is to then determine the correct dependence of the exponent on the fixed graph FF. This leads to the following question. Question 6.1. Is it true that

rind(F,H)≤v(H)O(v(F))r_{\mathrm{ind}}(F,H) \le v(H)^{O(v(F))}

for all graphs FF and HH?

If true, this would give the optimal form of the polynomial dependence on v(H)v(H). In general the best lower bound on rind(F,H)r_{\mathrm{ind}}(F,H) that we are aware of is just the usual Ramsey number r(F,H)r(F,H). 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 H\mathcal{H} be an rr-uniform hypergraph with a finite vertex set VV. For every p∈(0,1/(8r2)]p \in(0,1/(8r^{2})], there exists a family S⊆2V\mathcal{S} \subseteq2^{V} and functions

g:I(H)→Sandf:S→2Vg:\mathcal{I}(\mathcal{H}) \to\mathcal{S} \qquad\text{and}\qquad f:\mathcal{S} \to2^{V}

such that:

  • (a) For each I∈I(H)I \in\mathcal{I}(\mathcal{H}), we have g(I)⊂I⊂f(g(I))g(I) \subset I \subset f(g(I)).

  • (b) Each S∈SS \in\mathcal{S} has at most 8r2p∣V∣8r^2p|V| elements.

  • (c) For every S∈SS \in\mathcal{S}, there does not exist a hypergraph HS⊂H[f(S)]\mathcal{H}_S \subset\mathcal{H}[f(S)] that satisfies

Δℓ(HS)<pℓ−1e(HS)∣f(S)∣for all ℓ∈{2,…,r}.\Delta_\ell(\mathcal{H}_S) < \frac{p^{\ell-1}e(\mathcal{H}_S)}{|f(S)|} \qquad\text{for all } \ell\in\{2,\ldots,r\}.

We will apply Theorem A.1 to the following hypergraph, which encodes induced copies of FF in a subgraph of KnK_n. Let H\mathcal{H} be a hypergraph with vertex set

V(H)=E(Kn)×{0,1},V(\mathcal{H}) = E(K_n) \times\{0,1\},

and whose edges are the sets of the form

(φ(E(F))×{1})∪(φ(E(Ks)∖E(F))×{0}),\bigl(\varphi(E(F)) \times\{1\}\bigr) \cup\bigl(\varphi(E(K_s) \setminus E(F)) \times\{0\}\bigr),

where φ:V(F)→V(Kn)\varphi: V(F) \to V(K_n) is an arbitrary embedding. In other words, H\mathcal{H} encodes all the possible induced copies of FF in a subgraph of KnK_n. In particular, every pair of graphs G0⊂G1G_0 \subset G_1 on nn vertices for which there is no U⊂V(G0)U \subset V(G_0) satisfying G0[U]=G1[U]≅FG_0[U] = G_1[U] \cong F can be viewed as an independent set in H\mathcal{H} considering the set

I={(e,1):e∈E(G0)}∪{(e,0):e∈E(G1‾)}⊂V(H).I = \{(e,1): e \in E(G_0)\} \cup\{(e,0): e \in E(\overline{G_1})\} \subset V(\mathcal{H}).

With these observations in mind, we are now ready to prove Theorem 2.1.

Proof of Theorem 2.1. Let p=(εn)−2s+1p=(\varepsilon n)^{-\frac{2}{s+1}} and r=(s2)r=\binom{s}{2}. For a set A⊂V(H)A \subset V(\mathcal{H}) and i∈{0,1}i \in\{0,1\}, define

A(i)={e∈E(Kn):(e,i)∈A}.A^{(i)}=\{e \in E(K_n):(e,i)\in A\}.

First we deal with the trivial case that p>1/(32r2)p>1/(32r^2). In this case we can take

C={(I(0),I(1)):I∈I(H)},\mathcal{C}=\{(I^{(0)},I^{(1)}):I\in\mathcal{I}(\mathcal{H})\},

the family of all independent sets of H\mathcal{H}. Note that property (a) of Theorem 2.1 holds immediately, and for each I∈I(H)I\in\mathcal{I}(\mathcal{H}) there is no copy of KsK_s in I(0)∩I(1)I^{(0)}\cap I^{(1)}, since II spans no edge, implying property (b) in Theorem 2.1. Moreover, we have

∣I(H)∣≤2∣V(H)∣≤2n2≤exp⁡(8s4ε−2s+1n2−2s+1log⁡n),|\mathcal{I}(\mathcal{H})|\leq2^{|V(\mathcal{H})|}\leq2^{n^2}\leq\exp\left(8s^4\varepsilon^{-\frac{2}{s+1}}n^{2-\frac{2}{s+1}}\log n\right),

since 8s4ε−2s+1n−2s+1≥18s^4\varepsilon^{-\frac{2}{s+1}}n^{-\frac{2}{s+1}}\geq1.

We may now assume p≤1/(32r2)p\leq1/(32r^2). Applying Theorem A.1 to the rr-uniform hypergraph H\mathcal{H}, we obtain a family S⊂2V(H)\mathcal{S}\subset2^{V(\mathcal{H})} and functions

g:I(H)→Sandf:S→2V(H)g:\mathcal{I}(\mathcal{H})\to\mathcal{S}\qquad\text{and}\qquad f:\mathcal{S}\to2^{V(\mathcal{H})}

satisfying items (a)–(c) in Theorem A.1.

Then define

C={(C(0),C(1)):C∈f(S)}.\mathcal{C}=\{(C^{(0)},C^{(1)}):C\in f(\mathcal{S})\}.

Fix a pair of graphs G0⊂G1G_0\subset G_1 on nn vertices for which there is no U⊂V(G1)U\subset V(G_1) satisfying G0[U]=G1[U]≅FG_0[U]=G_1[U]\cong F. Note that the set

I={(e,1):e∈E(G0)}∪{(e,0):e∈E(G1‾)}⊂V(H)I=\{(e,1):e\in E(G_0)\}\cup\{(e,0):e\in E(\overline{G_1})\}\subset V(\mathcal{H})

is an independent set in H\mathcal{H}. By item (a) in Theorem A.1, there exists S∈SS \in\mathcal{S} such that S=g(I)S = g(I) and S⊂I⊂f(S)=CS \subset I \subset f(S) = C. In particular, we must have

I(1)=G0⊂C(1)andI(0)=G1c⊂C(0).I^{(1)} = G_0 \subset C^{(1)} \qquad\text{and}\qquad I^{(0)} = G_1^c \subset C^{(0)}.

which proves property (a) of Theorem 2.1. Moreover, by item (b) in Theorem A.1 the size of the family C\mathcal{C} can be bounded as

∣C∣≤(n22pn2)≤exp⁡(8s4⋅ε−2s+1n2−2s+1log⁡n).|\mathcal{C}| \leq\binom{n^2}{2pn^2} \leq\exp\left(8s^4\cdot\varepsilon^{-\frac{2}{s+1}}n^{2-\frac{2}{s+1}}\log n\right).

since ∣V∣≤n2|V| \leq n^2 and using that p=(εn)−2s+1p = (\varepsilon n)^{-\frac{2}{s+1}}.

It remains to prove item (b) in Theorem 2.1. Given (X,Y)∈C(X,Y) \in\mathcal{C} let

KX,Y:={K⊂X∩Y:K≅Ks},\mathcal{K}_{X,Y} := \{K \subset X \cap Y : K \cong K_s\},

that is a hypergraph encoding copies of KsK_s in X∩YX \cap Y. We have that e(KX,Y)e(\mathcal{K}_{X,Y}) is the number of copies of KsK_s in X∩YX \cap Y, therefore we only need to show that e(KX,Y)≤εnse(\mathcal{K}_{X,Y}) \leq\varepsilon n^s.

Let C=(X×{0})∪(Y×{1})C = (X \times\{0\}) \cup(Y \times\{1\}) and take some injective function ϕ:KX,Y→H[C]\phi: \mathcal{K}_{X,Y} \to\mathcal{H}[C] such that ϕ(K)⊂K×{0,1}\phi(K) \subset K \times\{0,1\}, for each K∈KX,YK \in\mathcal{K}_{X,Y}. Let HC:=ϕ(KX,Y)\mathcal{H}_C := \phi(\mathcal{K}_{X,Y}), by item (c) in Theorem A.1, this hypergraph must satisfy

e(HC)≤∣C∣Δℓ(HC)pℓ−1e(\mathcal{H}_C) \leq\frac{|C|\Delta_\ell(\mathcal{H}_C)}{p^{\ell-1}}

for some ℓ∈{2,3,…,(s2)}\ell\in\left\{2,3,\ldots,\binom{s}{2}\right\}. First, we bound Δℓ(HC)\Delta_\ell(\mathcal{H}_C). Let vℓ∈{3,…,s}v_\ell\in\{3,\ldots,s\} be the unique integer satisfying (vℓ−12)<ℓ≤(vℓ2)\binom{v_\ell-1}{2} < \ell\leq\binom{v_\ell}{2}. Thus,

Δℓ(HC)≤Δℓ(KX,Y)≤(n−vℓs−vℓ)≤ns−vℓ,(20)\Delta_\ell(\mathcal{H}_C) \leq\Delta_\ell(\mathcal{K}_{X,Y}) \leq\binom{n-v_\ell}{s-v_\ell} \leq n^{s-v_\ell}, \tag*{(20)}

where in the first inequality we use that for each E∈HCE \in\mathcal{H}_C there is some K∈KX,YK \in\mathcal{K}_{X,Y} such that E⊂KE \subset K, and for the second we use that any ℓ\ell pairs span at least vℓv_\ell vertices.

Now observe that

ℓ−1≤(vℓ2)−1=(vℓ+1)(vℓ−2)2≤(s+1)(vℓ−2)2,\ell- 1 \leq\binom{v_\ell}{2} - 1 = \frac{(v_\ell+1)(v_\ell-2)}{2} \leq\frac{(s+1)(v_\ell-2)}{2},

which implies

2(ℓ−1)s+1≤vℓ−2.\frac{2(\ell-1)}{s+1} \leq v_\ell- 2.

Then we obtain

p−ℓ+1=(εn)2(ℓ−1)s+1≤(εn)2(ℓ−1)vℓ+1≤(εn)vℓ−2.(21)p^{-\ell+1} = (\varepsilon n)^{\frac{2(\ell-1)}{s+1}} \leq(\varepsilon n)^{\frac{2(\ell-1)}{v_\ell+1}} \leq(\varepsilon n)^{v_\ell-2}. \tag*{(21)}

Putting together (20) and (21) we obtain

∣C∣Δℓ(HC)pℓ−1≤ns−vℓ+2(εn)vℓ−2≤εns,\frac{|C|\Delta_\ell(\mathcal{H}_C)}{p^{\ell-1}} \leq n^{s-v_\ell+2}(\varepsilon n)^{v_\ell-2} \leq\varepsilon n^s,

using that vℓ≥3v_\ell\geq3 and ε∈(0,1)\varepsilon\in(0,1). This finishes the proof since

e(KX,Y)=e(HC)≤εns.e(\mathcal{K}_{X,Y}) = e(\mathcal{H}_C) \leq\varepsilon n^s.

References

  1. [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. [2]J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. J. Amer. Math. Soc., 28:669–709, 2015.
  3. [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. [4]J. Balogh and W. Samotij. An efficient container lemma. Discrete Anal., 2020. Paper No. 17, 56 pp.arxiv.org/abs/1910.09208
  5. [5]M. Campos and W. Samotij. Towards an optimal hypergraph container lemma. Combinatorica, 46(3), 2026. Article 24.arxiv.org/abs/2408.06617
  6. [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. [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. [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. [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. [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. [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. [12]Y. Kohayakawa, H. J. Prömel, and V. Rödl. Induced Ramsey numbers. Combinatorica, 18:373–404, 1998.DOI
  13. [13]V. Rödl. The dimension of a graph and generalized Ramsey theorems. Master’s thesis, Charles University, Prague, 1973.
  14. [14]W. Samotij. Counting independent sets in graphs. European J. Combin., 48:5–18, 2015.arxiv.org/abs/1412.0940
  15. [15]D. Saxton and A. Thomason. Hypergraph containers. Invent. Math., 201:925–992, 2015.DOI
  16. [16]C. Zhong, M. Kashima, and Y. Mao. A solution to the kohayakawa–prömel–rödl conjecture, 2026.DOI

Paper details

vlnc:W_cz7n98y4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents