A Solution to the Kohayakawa-Prömel-Rödl Conjecture

Introduction

All graphs in this paper are undirected, finite and simple. For a graph $G$ and a vertex $v\in V(G)$, its neighborhood $N_G(v)$ is the set of vertices adjacent to $v$, and its closed neighborhood is $N_G[v]=N_G(v)\cup\{v\}$. The degree of a vertex $v\in V(G)$ is $d_G(v)=|N_G(v)|$. For a set of vertices $S\subseteq V(G)$, $G[S]$ is the subgraph of $G$ induced by $S$. For two disjoint subsets $S$ and $T$ of $V(G)$, let $E_G(S,T)$ denote the set of edges of $G$ with one end in $S$ and the other end in $T$, and let $e_G(S,T)=|E_G(S,T)|$.

Moreover, we write $E_G(v,T)$ or $e_G(v,T)$ instead of $E_G(\{v\},T)$ or $e_G(\{v\},T)$ for a vertex $v$. Undefined concepts or notation can be found in [5].

A cornerstone of classical Ramsey theory is the study of Ramsey numbers. For given graphs $G$ and $H$, the Ramsey number $r(G,H)$ is defined as the minimum integer $n$ such that every red/blue edge-coloring of the complete graph $K_n$ contains either a red copy of $G$ or a blue copy of $H$ as a subgraph. A natural and highly restrictive variant of this concept is the induced Ramsey problem. For graphs $F$, $G$, and $H$, we write $F \overset{\mathrm{ind}}{\longrightarrow} (G,H)$ if every red/blue edge-coloring of $F$ yields either a red induced copy of $G$ or a blue induced copy of $H$. Here, a red (resp. blue) induced copy of $G$ (resp. $H$) refers to an induced subgraph of $F$ that is isomorphic to $G$ (resp. $H$) and has all its edges colored red (resp. blue).

The foundational fact that such a graph $F$ always exists for any choice of $G$ and $H$ was independently proved in the 1970s by Deuber [7], Erdős, Hajnal, and Pósa [10], and Rödl [23, 24]. This seminal result sparked extensive research into induced Ramsey numbers. For any graphs $G$ and $H$, the induced Ramsey number, denoted by $r_{\mathrm{ind}}(G,H)$, is defined as the minimum number of vertices in a graph $F$ satisfying $F \overset{\mathrm{ind}}{\longrightarrow} (G,H)$. Moreover, when $G=H$, it is simply referred to as the induced Ramsey number of $G$, and is denoted by $r_{\mathrm{ind}}(G)$. Since in the case of complete graphs the induced subgraph is the same as the subgraph, it is obvious that $r_{\mathrm{ind}}(K_m,K_n)=r(K_m,K_n)$.

Much of the early focus was on the diagonal case $r_{\mathrm{ind}}(G)$. Erdős [9] conjectured an exponential upper bound $r_{\mathrm{ind}}(G) \leq2^{cn}$. A major breakthrough towards this conjecture was made by Kohayakawa, Prömel, and Rödl [20], who established a quasi-exponential upper bound of $2^{cn(\log n)^2}$. This was later improved by Conlon, Fox, and Sudakov [6] to $2^{cn\log n}$, bringing the bound even closer to Erdős’s original conjecture. Fox and Sudakov [13] further developed a unified approach that yielded linear bounds for specific structures such as paths and stars. In 2025, Aragão, Campos, Dahia, Filipe, and Marciano [1] fully resolved this conjecture.

However, the off-diagonal case $r_{\mathrm{ind}}(G,H)$ presents different challenges. In 1998, Kohayakawa, Prömel, and Rödl proposed the following conjecture regarding the polynomial boundedness of induced Ramsey numbers when one graph is fixed.

Towards this conjecture, Kohayakawa, Prömel, and Rödl [20] proved that $r_{\mathrm{ind}}(G,H) \leq t^{Ck\log q}$ when $|V(G)|=k \leq|V(H)|=t$ and $q=\chi(H)\geq2$, where $C>0$ is an absolute constant. To further investigate Conjecture 1, they verified the conjecture for every $G\in\mathcal{S}$, where $\mathcal{S}$ is the smallest class of finite graphs containing the 1-vertex complete graph and closed under taking disjoint unions and joins. Since trees are not covered by $\mathcal{S}$, they also addressed them as a fundamental case, proving that for any $k$-vertex tree $T$ and $t$-vertex graph $H$, $r_{\mathrm{ind}}(T,H) \le ck^{2}t^{4}\left(\frac{\log(kt^{2})}{\log\log(kt^{2})}\right)^{2}$. Cycles have also been studied extensively. Haxell, Kohayakawa, and Łuczak [18] proved that the induced size-Ramsey number of $C_{\ell}$ is linear in $\ell$, which implies that $r_{\mathrm{ind}}(C_{\ell},C_{\ell})=O(\ell)$. Schaefer and Shah [25] gave explicit constructions yielding $r_{\mathrm{ind}}(C_{\ell},B)\le|V(B)|^{\lceil\log_{2}\ell\rceil+4}$ and $r_{\mathrm{ind}}(C_{\ell},T)\le|V(T)|^{\lceil\log_{2}\ell\rceil+1}$, where $\ell\ge3$, $B$ is bipartite, and $T$ is a tree. For a varying fan graph $F_r$, Zhong et al. [27] proved that $r_{\mathrm{ind}}(G,F_r)\le C_G r^2$ for every fixed graph $G$, where $C_G$ depends only on $G$. For other results on induced Ramsey numbers, see [2, 3, 14, 15, 16, 21].

In this paper, we resolve Conjecture [1] by proving the following general bound.

Therefore, Theorem 1.1 verifies Conjecture [1] with $f(G)=60|V(G)|^{2}+3$.

Deterministic counting lemmas

For a positive integer $r$, write $[r]=\{1,\ldots,r\}$. For a graph $R$ and $U\subseteq V(R)$, write $e_R(U)=e(R[U])$. All logarithms are natural unless another base is specified. An empty product is interpreted as $1$.

For a finite set $V$ of size $N$ and a real matrix $A:V\times V\to\mathbb{R}$, define the normalized cut norm by

The sets $S$ and $T$ need not be disjoint. A scalar subtracted from a matrix denotes the constant matrix on all of $V\times V$, including the diagonal.

We begin with a weighted form of the cut-norm estimate, which allows us to control sums involving functions taking values in $[0,1]$.

Proof. For a set $S\subseteq V$, let $\mathbf{1}_S$ denote its indicator function, that is,

We first express the functions $f$ and $g$ in terms of indicator functions of their level sets. Fix $x \in V$. Since $0 \le f(x) \le1$, for $a \in[0,1]$, we have

Therefore, $\int_0^1 \mathbf{1}_{\{f(x)\ge a\}}\, da = \int_0^{f(x)} 1\, da = f(x)$, and thus $f(x) = \int_0^1 \mathbf{1}_{\{f(x)\ge a\}}\, da$. Similarly, for every $y \in V$, we have $g(y) = \int_0^1 \mathbf{1}_{\{g(y)\ge b\}}\, db$. Thus,

Substituting this identity into the weighted sum gives

Here we may interchange the finite sum and the integrals since $V$ is finite.

For fixed $a,b \in[0,1]$, define the level sets $S_a = \{x \in V : f(x) \ge a\}$ and $T_b = \{y \in V : g(y) \ge b\}$. Then $\mathbf{1}_{\{f(x)\ge a\}} = \mathbf{1}_{S_a}(x)$ and $\mathbf{1}_{\{g(y)\ge b\}} = \mathbf{1}_{T_b}(y)$. Hence $\mathbf{1}_{S_a}(x)\mathbf{1}_{T_b}(y) = 1$ if and only if both $x \in S_a$ and $y \in T_b$, implying that

Combine this with the above equation, it follows that

By the definition of the cut norm, every pair of subsets $S,T\subseteq V$ satisfies

Applying this with $S=S_a$ and $T=T_b$, and then using the triangle inequality, we obtain

This proves the lemma. $\square$

Using the preceding estimate, we now compare induced embedding counts with ordinary homomorphism counts by replacing the nonedge factors one at a time.

Let $\Gamma$ be a graph on $V$, and define its nonedge matrix $Z_{\Gamma}$ by

In particular, $Z_{\Gamma}(x,x)=0$ for any $x\in V$. Let $R$ be a subgraph of $\Gamma$, and denote its adjacency matrix by

In particular, $R(x,x)=0$ for any $x\in V$. For a graph $G$ with $V(G)=[k]$, let $\overline{E}(G)=\binom{[k]}{2}\setminus E(G)$ and $m=|\overline{E}(G)|$. Define

and

The first expression counts graph homomorphisms, with no injectivity requirement. In the second expression, if $x_i=x_j$ for two distinct indices, then $Z_{\Gamma}(x_i,x_j)=0$ and the monomial vanishes. Thus $I_G(R,Z_{\Gamma})$ counts the labeled induced embeddings of $G$ into $\Gamma$ whose edges all belong to $R$.

The next lemma adapts the standard cut-norm telescoping argument to a finite matrix setting. For the usual counting lemma, see [26 Section 4.5]. We include the whole proof just to show clearly that only the nonedge factors are changed.

The quantity $T_s$ should be viewed as an intermediate count in which the first $s$ nonedge factors have already been replaced by the constant $\sigma$, while the remaining $m-s$ nonedge factors are still kept as $Z_{\Gamma}$. In particular, when $s=0$, no nonedge factor has been replaced, and so

On the other hand, when $s=m$, every nonedge factor has been replaced by $\sigma$, and hence

It is therefore enough to estimate the change between $T_{s-1}$ and $T_s$ at each single replacement.

Fix $s\in[m]$ and set $e_s=ab$. By the definition of $T_{s-1}$ and $T_s$, the two expressions differ only in the factor corresponding to this nonedge; that is, the factor is $Z_{\Gamma}(x_i,x_j)$ in $T_{s-1}$, whereas it has been replaced by $\sigma$ in $T_s$. Therefore

We now fix all coordinates $x_r$ with $r\in[k]\setminus\{a,b\}$ and regard only $x_a$ and $x_b$ as variables.

Proof. Every factor appearing in (1), except for the constant factor $\sigma^{s-1}$, is associated with an unordered pair of distinct vertices of $G$.

Now $e_s=ab$ is a nonedge of $G$, so the edge product contains no factor of the form $R(x_a,x_b)$. Among the nonedge factors, the unique factor corresponding to the pair $ab$ is the one being replaced at the $s$th step, namely $Z_{\Gamma}(x_i,x_j)-\sigma$. Thus, every other factor can involve at most one of the two variables $x_a$ and $x_b$. Thus, each remaining factor depends either only on $x_i$, only on $x_j$, or on neither of them. □

By Claim 1, after the other $k-2$ coordinates have been fixed, we may collect all factors depending only on $x_i$ into a function $f:V\to[0,1]$, all factors depending only on $x_j$ into a function $g:V\to[0,1]$, and all factors depending on neither $x_i$ nor $x_j$, together with the constant factor $\sigma^{s-1}$, into a constant $c\in[0,1]$. Thus, for this fixed choice of the other coordinates, the contribution to $T_{s-1}-T_s$ has the form $c\sum_{x_a,x_b\in V}(Z_{\Gamma}(x_a,x_b)-\sigma)f(x_a)g(x_b)$. Since every value of $R$ and $Z_{\Gamma}$ is either 0 or 1, while $0<\sigma\le1$, then every product formed from such factors lies in $[0,1]$.

Since $\lVert Z_{\Gamma}-\sigma\rVert_{\square}\le\varepsilon$, we can apply Lemma 2.1 with the matrix $A=Z_{\Gamma}-\sigma$ to obtain

Because $0 \le c \le1$, we have

This estimate holds for every fixed choice of the remaining $k-2$ coordinates. There are exactly $N^{k-2}$ possible choices for these coordinates. Summing the above estimate over all of them yields $|T_{s-1}-T_s|\le N^{k-2}\cdot\varepsilon N^2=\varepsilon N^k$. Thus $T_0-T_m=\sum_{s=1}^{m}(T_{s-1}-T_s)$, and hence $|T_0-T_m|\le\sum_{s=1}^{m}|T_{s-1}-T_s|\le m\varepsilon N^k$. Recalling that $T_0=I_G(R,Z_{\Gamma})$ and $T_m=\sigma^m\operatorname{hom}(G,R)$, we obtain

The preceding lemma is entirely deterministic once the host graph $\Gamma$ is fixed. In particular, it holds simultaneously for every spanning subgraph $R\subseteq\Gamma$, and no probabilistic independence between the red graph $R$ and the host graph $\Gamma$ is required. This is important in our Ramsey application, since the red graph is determined only after an arbitrary coloring of the already chosen host.

We also stress that the intermediate quantities $T_s$ are summed over all of $V^k$, without imposing injectivity. For $T_0=I_G(R,Z_{\Gamma})$, injectivity is automatic because both $R$ and $Z_{\Gamma}$ have zero diagonal; if $x_i=x_j$, then the factor corresponding to the pair $\{i,j\}$ vanishes. After a nonedge factor $Z_{\Gamma}(x_i,x_j)$ is replaced by the constant $\sigma$, this automatic exclusion of collisions may disappear. Thus the intermediate $T_s$ should not be interpreted as induced embedding counts. Allowing all tuples in $V^k$ is precisely what permits the remaining factors in a single replacement step to separate as $cf(x_i)g(x_j)$.

To apply the preceding counting estimate, we also need a lower bound on the number of red homomorphisms. The following lemma provides such a bound under a local edge-density condition.

We now construct many ordered $k$-tuples spanning a copy of $K_k$ in $R$. Let $W_0 = V(R)$. Since $|W_0| = N \ge\rho^{k-1}N$, Claim 1 can apply to $W_0$. Hence at least $\rho|W_0| = \rho N$ vertices of $W_0$ have degree at least $\rho|W_0|$ in $R[W_0]$. Choose one such vertex $x_1$ and set $W_1 = W_0 \cap N_R(x_1)$. For each $j = 2,3,\ldots,k$, we recursively apply Claim 1 to $W_{j-1}$ to find a vertex $x_j \in W_{j-1}$ with $|W_{j-1} \cap N_R(x_j)| \ge\rho|W_{j-1}|$ and set $W_j = W_{j-1} \cap N_R(x_j)$. Note that we have $|W_{j-1}| \ge\rho^{j-1}N \ge\rho^{k-1}N$ in each step, so Claim 1 can apply.

By the construction, it follows that $x_j \in\bigcap_{\ell=1}^{j-1} N_R(x_\ell)$ for all $j \in\{2,3,\ldots,k\}$, and hence $\{x_1,x_2,\ldots,x_k\}$ is a clique of $R$. Furthermore, since we have $\rho|W_{j-1}| \ge\rho^jN$ different choice of $x_j$ for each $j$th step, $\operatorname{hom}(K_k,R)$, the number of ordered copies of $K_k$ in $R$ is bounded by

where the last inequality follows from $k \ge2$ and $0 < \rho\le1$.

For any graph $G$ with $k$ vertices, each ordered copy of $K_k$ in $R$ contains an ordered copy of $G$ in itself, and thus we have $\operatorname{hom}(G,R) \ge\operatorname{hom}(K_k,R)$, as desired.

The projective-plane

We now introduce the random host graph. For a prime $p$, let $N = p^2+p+1$. A finite projective plane of order $p$ is an incidence structure $\mathcal{P}=(V,\mathcal{L})$ with its point set as $V$ and its line set as $\mathcal{L}$ with the following properties (see [17]):

• $|V|=N$ and $|\mathcal{L}|=N$;

• every line $L\in\mathcal{L}$ contains exactly $p+1$ points;

• every point $v\in V$ lies on exactly $p+1$ lines;

• any two distinct lines intersect in exactly one point

• any two distinct points determine a unique line.

It is well known that finite projective planes exist whenever $p$ is a prime power.

We will use the following elementary incidence calculation.

Proof. Counting incidences with points in $U$ gives $\sum_{L\in\mathcal{L}} |U\cap L|=(p+1)|U|$. Counting ordered pairs of distinct points in $U$ gives $\sum_{L\in\mathcal{L}} |U\cap L|(|U\cap L|-1)=|U|(|U|-1)$, since every such pair belongs to a unique line. Consequently, $\sum_{L\in\mathcal{L}} |U\cap L|^2=\sum_{L\in\mathcal{L}} |U\cap L|(|U\cap L|-1)+\sum_{L\in\mathcal{L}} |U\cap L|=|U|^2+p|U|$.

Now we set $\mu=\frac{(p+1)|U|}{N}$. Since $(p+1)^2=N+p$, we have

where the last inequality follows from $|U|\le|V|=N$. Suppose that $|U|\ge64p$. Each line $L$ with $|U\cap L|<\frac{\mu}{2}$ contributes to the above sum by at least $\frac{\mu^2}{4}$, so the number of such lines is at most $\frac{4p|U|}{\mu^2}$. By the definition of $\mu$, we have $\mu\ge\frac{|U|}{2p}$, and hence

Thus, at least $\frac{3N}{4}$ lines satisfies $|U\cap L|\ge\frac{\mu}{2}\ge\frac{|U|}{4p}$, as required. □

The randomness will be placed on incidences rather than on points. Fix a graph $H$ with $V(H)=[t]$. For each incidence $(x,L)$ with $x\in L$, choose a label $\lambda_L(x)$ independently and uniformly from $[t]$. There are $N(p+1)$ independent labels. In particular, $\lambda_L(x)$ and $\lambda_{L'}(x)$ are independent when $L\ne L'$.

For distinct $x,y\in V$, let $L(x,y)$ be their unique common line. Define a random graph $\Gamma$ on $V$ by

This is the projective-plane random graph introduced in the form used here in [20 Section 2.1]. For $L\in\mathcal{L}$ and $i\in[t]$, set $L_i=\{x\in L\mid\lambda_L(x)=i\}$. For distinct $i,j\in[t]$, the bipartite graph between $L_i$ and $L_j$ is complete if $ij\in E(H)$ and empty if $ij\notin E(H)$. Moreover, each $L_i$ is an independent set, since $H$ has no loops. Therefore, every choice of one point from each of the $t$ nonempty classes $L_i$ gives an induced copy of $H$ in $\Gamma$.

Set

For distinct $x,y$, $xy$ is an edge of $\Gamma$ if $x$ and $y$ map to some edge of $H$ by $\lambda_{L(x,y)}$. Since there are $2e(H)$ possibilities of such maps, for the nonedge matrix, we conclude that

Also, we have

The diagonal entries of $Z_{\Gamma}$ are zero rather than having $\sigma$; their contribution will be retained explicitly in the cut-norm estimate.

Properties of the random host

We first show that all sufficiently large vertex sets meet every label class on many lines. This property depends only on the random labels, not on any subsequent edge-coloring.

Proof. Fix a set $U \subseteq V$ with $|U| \ge\frac{N}{t^b}$. Since $N \ge p^2$ and $p \ge512t^{b+2}$, we have $|U| \ge\frac{p^2}{t^b} \ge64p$. Let

By Lemma 3.1, $|Q(U)| \ge\frac{3N}{4}$. Note that $Q(U)$ depends only on $U$ and the incidence structure of the projective plane, before any random labels are exposed.

Now fix a line $L \in Q(U)$ and a label $i \in[t]$. Since the labels $\{\lambda_L(x) \mid x \in L\}$ are independent and uniformly distributed on $[t]$, it means that the random variable $X_i=|U \cap L_i|$ has distribution $X_i \sim\operatorname{Bin}(|U \cap L|,1/t)$, that is, $\mu_i=\frac{|U \cap L|}{t}$. Since $L \in Q(U)$, $\mu_i \ge\frac{|U|}{4tp}$. Thus $\frac{|U|}{8tp} \le\frac{\mu_i}{2}$, and hence

By the Chernoff bound, we have $\Pr(X_i < \frac{\mu_i}{2}) \le e^{-\mu_i/8}$, and hence

If $L$ fails (7), then there must exist some $i \in[t]$ such that $|U \cap L_i| < \frac{|U|}{8tp}$. Thus, by the union bound over the $t$ labels, we have $\mathbb{P}(L\text{ fails }{xref}`(7)`) \le t\exp\left(-\frac{|U|}{32tp}\right)$. No independence among the random variables $|U \cap L_1|,\ldots,|U \cap L_t|$ is needed here. Set $s=\frac{N}{t^b}$ and $\eta_0=t\exp\left(-\frac{s}{32tp}\right)$. Since every set under consideration satisfies $|U| \ge s$, then $\mathbb{P}(L\text{ fails }{xref}`(7)`) \le\eta_0$ for every $L \in Q(U)$. Moreover, since $N \ge p^2$, we have $s=\frac{N}{t^b} \ge\frac{p^2}{t^b}$, and hence $\eta_0 \le t\exp\left(-\frac{p}{32t^{b+1}}\right)$. Using $p \ge512t^{b+2}$, we obtain that $\eta_0 \le te^{-16t}<1$.

For this fixed set $U$, the failure events corresponding to distinct lines are independent. Indeed, whether a line $L$ satisfies (7) depends only on the incidence labels $\{\lambda_L(x)\mid x\in L\}$. If $L \ne L'$, these_超碰 are disjoint collections of point–line incidence variables. Even when $L$ and $L'$ meet at a point $x$, the labels $\lambda_L(x)$ and $\lambda_{L'}(x)$ are independent by construction.

Suppose that fewer than $\frac{N}{2}$ lines satisfy (7). Since $|\mathcal{Q}(U)| \ge\frac{3N}{4}$, it follows that at least $\frac{3N}{4}-\frac{N}{2}=\frac{N}{4}$ lines in $\mathcal{Q}(U)$ must fail (7). Set $r=\left\lceil\frac{N}{4}\right\rceil$. Using the binomial expansion, we have

Note that there are at most $2^N$ subsets of $V$. Thus a union bound over all sets with $|U|\geq s$ shows that the probability that there exists some $U\subseteq V$ with $|U|\geq s$ for which fewer than $\frac{N}{2}$ lines satisfy (7) is at most $4^N\eta_0^{N/4}$. Since $\eta_0=t\exp\left(-\frac{s}{32tp}\right)$, $N\geq p^2$ and $p\geq512t^{b+2}$, we obtain that

with $t\geq2$.

Thus, with probability at least $1-e^{-2N}$, every set $U\subseteq V$ with $|U|\geq\frac{N}{t^b}$ has at least $\frac{N}{2}$ lines satisfying (7).

The conclusion of Lemma 4.1 is a property of a realized labeled host. Since the union bound ranges over every vertex set, it also applies to sets selected after observing the labels or after choosing an edge-coloring.

We now extract a deterministic consequence of this property.

Proof. Fix such a coloring and a set $U$ with $|U|\geq N/t^b$. For a line $L$ satisfying (7), let $W_i=U\cap L_i$ and $q=\frac{|U|}{8tp}$. Each $W_i$ has at least $q>0$ points and is therefore nonempty. Choose one point independently and uniformly from each $W_i$. The resulting transversal is an induced copy of $H$ in the host. Since no such copy is entirely blue, every transversal contains at least one red edge.

For $ij\in E(H)$, let $r_{ij}$ be the number of red edges between $W_i$ and $W_j$. Since each edge counted as $r_{ij}$ contributes to $\prod_{\ell\notin\{i,j\}}|W_\ell|$ many transversals, we have

and hence

Thus, each line satisfying (7) contributes at least $q^2$ red edges in $U$. Every unordered pair of points lies on exactly one line, so no red edge is counted twice when we sum over lines. By Lemma 4.1, at least $\frac{N}{2}$ lines satisfy (7), and hence

If $H$ has no edges, the transversal is automatically blue, and hence the hypothesis of a coloring without a blue induced $H$ is impossible. This also covers that case.

We next establish a second property of the random host graph, namely that its nonedge matrix $Z_\Gamma$ is close, in cut norm, to the constant matrix of density $\sigma$. This property is proved independently of the label-distribution property established. We derive a separate failure probability for it and later combine the two estimates by a union bound.

No pair determined by a different line can be affected because the label of $x$ on another line $L'$ is the different random variable $\lambda_{L'}(x)$.

Each affected unordered pair $\{x,y\}$ contributes at most two ordered pairs to the sum defining $X_{S,T}$, namely $(x,y)$ and $(y,x)$. Therefore, changing one incidence label changes $X_{S,T}$ by at most $2p$.

We may now apply Lemma $4.3$ to the $N(p+1)$ independent incidence labels. Since the change caused by any one label is at most $2p$, for every $a>0$ we obtain

The quantity appearing in the cut norm is not $X_{S,T}-\mathbb{E}X_{S,T}$, but rather $X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert$. The two centres differ only because of the diagonal terms. Indeed, by (7), $\lvert\mathbb{E}X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert\rvert=\sigma\lvert S\cap T\rvert\leq N$. Hence, by the triangle inequality, we have

Suppose now that $\lvert X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert\rvert>\varepsilon N^2$. Then $\lvert X_{S,T}-\mathbb{E}X_{S,T}\rvert>\varepsilon N^2-N$. Since $\varepsilon N\geq2$, we have $N\leq\frac{\varepsilon N^2}{2}$, and therefore $\varepsilon N^2-N\geq\frac{\varepsilon N^2}{2}$. Consequently, $\lvert X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert\rvert>\varepsilon N^2$ implies $\lvert X_{S,T}-\mathbb{E}X_{S,T}\rvert>\frac{\varepsilon N^2}{2}$.

Applying (8) with $a=\varepsilon N^2/2$, we obtain, for this fixed pair $S,T$,

We now pass from a fixed pair $S,T$ to all pairs of subsets. By the definition of the normalized cut norm, we have

Since $\sum_{x\in S,y\in T}(Z_{\Gamma}(x,y)-\sigma)=X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert$, the event $\lVert Z_{\Gamma}-\sigma\rVert_{\square}>\varepsilon$ is equivalent to the existence of subsets $S,T\subseteq V$ such that $\lvert X_{S,T}-\sigma\lvert S\rvert\lvert T\rvert\rvert>\varepsilon N^2$.

There are $2^N$ choices for $S$ and independently $2^N$ choices for $T$, so there are at most $4^N$ ordered pairs $(S,T)$. Hence, by the union bound,

It remains to simplify the exponent. Since $N=p^2+p+1\geq p^2$ and $p+1\leq2p$, we have

Therefore the right-hand side of (9) is at most $2\exp\left[N\left(\log4-\frac{\varepsilon^2p}{16}\right)\right]$. Finally, the assumption $\varepsilon^2p\geq64$ gives $\frac{\varepsilon^2p}{16}\geq4$, and hence, since $\log4<2$, $\log4-\frac{\varepsilon^2p}{16}\leq\log4-4<-2$. Thus $\mathbb{P}\left(\lVert Z_{\Gamma}-\sigma\rVert_{\square}>\varepsilon\right)\leq2e^{-2N}$, as required. ◤凰

The edges of the random host graph are not independent. The independent variables in the proof of Lemma 4.4 are exclusively the point–line labels. The influence bound $2p$ accounts for all ordered pairs that a single label can affect, including when $S$ and $T$ overlap.

Proof of the main theorem

Proof of Theorem 1.1. Fix $k,t\ge2$, a graph $G$ with $|V(G)|=k$, and a graph $H$ with $V(H)=[t]$. If $H$ has no edges, the edgeless graph on $t$ vertices already contains a blue induced copy of $H$ in every edge-coloring, so the theorem holds. We may therefore assume that $e(H)\ge1$.

Choose the parameters $b=10k$, $A=30k^2$, $\rho=t^{-10}$ and $\varepsilon=t^{-12k^2}$. By Bertrand’s postulate, there is a prime $p$ with $t^A\le p\le2t^A$. Take the random host graph of § 2 on $N=p^2+p+1$ vertices.

Since $k\ge2$, then $A-b-2=30k^2-10k-2\ge9$. This, together with $t\ge2$, implies that $p\ge t^A\ge t^{b+2}t^9\ge512t^{b+2}$. Thus Lemma 4.1 can apply. Since $\varepsilon^2p\ge t^{6k^2}\ge64$ and $\varepsilon N\ge\varepsilon p^2\ge t^{48k^2}\ge2$, Lemma 4.4 also applies. Recall that Lemma 4.1 fails with probability at most $e^{-2N}$, while Lemma 4.4 fails with probability at most $2e^{-2N}$. Therefore, by the union bound, the probability that both conclusions hold simultaneously is at least $1-e^{-2N}-2e^{-2N}=1-3e^{-2N}>0$. Hence there exists at least one realization of the incidence labels for which both conclusions hold. Fix such a realization and let $\Gamma$ denote the resulting host graph. In particular, Lemma 4.1 holds for this fixed host graph and $\lVert Z_\Gamma-\sigma\rVert_\square\le\varepsilon$.

Consider any red–blue coloring of $E(\Gamma)$, and let $R$ be its red spanning subgraph. If the coloring contains a blue induced copy of $H$, then we are done. Otherwise, by Lemma 4.2, we have $e_R(U)\ge\frac{|U|^2}{128t^2}$ for every $U\subseteq V$ with $|U|\ge N/t^{10k}$. Since $t^8\ge128$ for $t\ge2$, we have $\frac{1}{128t^2}\ge\rho$. Also, $\frac{N}{t^{10k}}=\rho^kN$. Therefore, $e_R(U)\ge\rho|U|^2$ when $|U|\ge\rho^kN$. To apply Lemma 2.3, we need the same inequality for all sets satisfying $|U|\ge\rho^{k-1}N$. Since $0<\rho<1$, we have $\rho^{k-1}\ge\rho^k$. Therefore every set with $|U|\ge\rho^{k-1}N$ also satisfies $|U|\ge\rho^kN$. Then $\operatorname{hom}(G,R)\ge\rho^{k^2}N^k=t^{-10k^2}N^k$.

Let $m=\binom{k}{2}-e(G)$, so that $m$ is the number of nonedges of $G$. By Lemma 2.2, we can obtain that $|I_G(R,Z_\Gamma)-\sigma^m\operatorname{hom}(G,R)|\le m\varepsilon N^k$, that is, $I_G(R,Z_\Gamma)\ge\sigma^m\operatorname{hom}(G,R)-m\varepsilon N^k$. Since $\sigma\ge\frac{1}{t}$ and $\varepsilon=t^{-12k^2}$, it follows that

Since $m\le\binom{k}{2}<k^2$, we have $2k^2-m>k^2$. Since $t\ge2$, then $t^{2k^2-m}>t^{k^2}\ge2^{k^2}$. Moreover, $m\le\binom{k}{2}<k^2<2^{k^2}$ for every $k\ge2$. Hence $t^{2k^2-m}>m$. Then $I_G(R,Z_\Gamma)>0$.

We now explain explicitly why this implies the existence of a red induced copy of $G$ in the host graph $\Gamma$. By definition, we have

Every factor in every summand is either 0 or 1. Since the total sum is positive, there exists at least one tuple $(x_1,\ldots,x_k)\in V(\Gamma)^k$ such that

Then we have $R(x_i,x_j)=1$ for each $ij\in E(G)$, implying that $x_ix_j\in R$. Also, for each $ij\in\overline{E}(G)$, we have $Z_\Gamma(x_i,x_j)=1$, implying that $ij\notin E(G)$. In particular, since either $R(x,x)=0$ or $Z_\Gamma(x,x)=0$ for any vertex $x\in V$, $(x_1,\ldots,x_k)$ are pairwise distinct $k$ vertices. Therefore, $(x_1,\ldots,x_k)$ induces a red copy of $G$, and $\Gamma\xrightarrow{\mathrm{ind}} (G,H)$.

Since $p\leq2t^A$, we have $N=p^2+p+1\leq4t^{2A}+2t^A+1\leq7t^{2A}$. Since $A=30k^2$, this gives $N\leq7t^{60k^2}$. Also, $t\geq2$, we have $7\leq t^3$, and hence $7t^{60k^2}\leq t^{60k^2+3}$. Hence $r_{\mathrm{ind}}(G,H)\leq7t^{60k^2}\leq t^{60k^2+3}$.

All the estimates above hold for every $k,t\geq2$, so no additional asymptotic or small-parameter cases remain. □