2. Preliminaries

In this section, we fix notation used throughout the paper and present auxiliary results needed in our arguments. We start with basic notation. The set of the first k positive integers is denoted by [k], and the set of all k-element subsets of A is denoted by $\binom{A}{k}$ . If A is a measurable subset of ${\mathbb{R}}^k$ , we write $\mu(A)$ for the measure of A; throughout the paper, we always consider the standard Borel measure on ${\mathbb{R}}^k$ .

All graphs considered in this paper are simple and loopless. If G is a graph, then the vertex set of G is denoted by V(G) and the edge set by E(G); the numbers of vertices and edges of G are denoted by v(G) and $e\left(G\right)$ , respectively. If A is a subset of vertices of G, then G[A] is the subgraph induced by A, i.e. the graph with the vertex set A and the edge set $E(G)\cap\binom{A}{2}$ . Finally, if F is a subset of edges of G, then $\langle F\rangle$ is the spanning subgraph of G with the edge set F; the host graph G will always be clear from the context. A homomorphism from a graph H to G is mapping f from V(H) to V(G) such that if uv is an edge of H, then f(u)f(v) is an edge of G, and the homomorphism density of H in G, denoted by t(H,G), is the probability that a random mapping from V(H) to V(G) is a homomorphism.

The n-vertex path is denoted by $P_n$ , the n-vertex cycle by $C_n$ , the complete graph with n vertices by $K_n$ , and the complete bipartite graph with parts consisting of a and b vertices by $K_{a,b}$ . Finally, $K_{a|\ell,b}$ is the graph obtained from $K_{a,b}$ by adding an $\ell$ -edge path to one of the vertices in the a-vertex part. In particular, $K_{a|0,b}$ is just the graph $K_{a,b}$ .

2.1 Graph limits

We treat the notion of common graphs using tools from the theory of graph limits. In this subsection, we provide an introduction to the most important concepts; we refer the reader to the monograph by Lovász [Reference LovászLov12] for a more complete treatment. In the theory of graph limits, large graphs are represented by an analytic object called graphon. A graphon is a measurable function $W:[0,1]^2\to [0,1]$ that is symmetric, i.e. $W(x,y)=W(y,x)$ for all $x,y\in [0,1]$ . When no confusion can arise, we use p to denote the graphon equal to $p\in [0,1]$ everywhere. More generally, a kernel is a symmetric measurable function $U:[0,1]^2\to{\mathbb{R}}$ . In particular, a graphon is a kernel with range in [0,1]. A graphon can be thought of as a continuous version of the adjacency matrix of a graph. Because of this analogy, we refer to the elements of the domain [0,1] as to vertices of W. The degree of a vertex $x\in [0,1]$ of a graphon W is defined as

\[\deg_W(x)=\int_{[0,1]}W(x,y)\,\textit{d} y.\]

The homomorphism density of a graph H in a graphon W is defined as

(2) \begin{equation}t(H,W) = \int_{[0,1]^{V(H)}} \prod_{uv\in E(H)} W(x_u,x_v) \,\textit{d} x_{V(H)}.\end{equation}

For brevity, we often speak about the density of H in W instead of the homomorphism density of H in W. The density of a graphon W is the density of $K_2$ in W, i.e. $t(K_2,W)$ . Analogously, we define the homomorphism density of a graph H in a kernel U using (2), and we define the density of a kernel U to be $t(K_2,U)$ .

We now cast the definition of graphs with the Sidorenko property and commons graphs in the language of graph limits; see, e.g., [KNN $^{+}$ 22] for further details. A graph H has the Sidorenko property if the following holds for every graphon W:

\[p^{e\left(H\right)}\le t(H,W)\]

where p is the density of W. A graph H is common if it holds that

\[2^{1-e\left(H\right)}\le t(H,W)+t(H,1-W)\]

for every graphon W. Finally, for an integer $k\ge 2$ , we say that a graph H is k-common if

\[k^{1-e\left(H\right)}\le t(H,W_1)+\cdots+t(H,W_k)\]

holds for all graphons $W_1,\ldots,W_k$ such that $W_1+\cdots+W_k=1$ .

We next define the notion of a norm for kernels, which gives a metric on the space of kernels and so on graphons. The cut norm of a kernel U is defined as

\[\|U\|_{\square} = \sup_{S, T \subseteq [0,1]} \bigg\lvert \int_{S \times T} U(x,y) \,\textit{d} x \,\textit{d} y\bigg\rvert,\]

where the supremum is taken over all measurable subsets S and T of [0,1]. If U is a kernel with $\|U\|_{\infty}\le 1$ , then it holds [Reference LovászLov12, Lemma 8.12] that

(3) \begin{equation}\|U\|_{\square}^4\le t(C_4,U)\le 4\|U\|_{\square}.\end{equation}

Similarly, it holds that $t(P_2,U)\le 2\|U\|_{\square}$ . Since $C_4$ has the Sidorenko property, it holds that $t(C_4,W)\ge p^4$ for every graphon W with density p. If a graphon W with density p is actually far from the p-constant graphon, then the density of $C_4$ is much larger than $p^4$ as given in the lemma.

Lemma 2.1 (Cooper et al. [Reference Cooper, Král͏̌ and MartinsCKM18, Lemma 11]). The following holds for every graphon W with density p:

\[p^4+\frac{\|W-p\|_{\square}^4}{8}\le t(C_4,W).\]

On the other hand, the counting lemma, which we now state, implies that $t(C_4,W)\le p^4+4\|W-p\|_{\square}$ for every graphon W with density p.

Lemma 2.2 (Counting lemma, Lovász [Reference LovászLov12, Lemma 10.23]) The following holds for every graph H and all graphons $W_1$ and $W_2$ :

\[\lvert t(H,W_1)-t(H,W_2)\rvert\le e\left(H\right)\cdot\|W_1-W_2\|_{\square}.\]

We next define a notion used in [KNN $^{+}$ 22] that can be viewed as an analogue of a subgraph in a graphon. Consider a measurable function $h:[0,1]\to [0,1]$ such that $\|h\|_1>0$ . Let $f:[0,\|h\|_1]\to [0,1]$ be the measurable function defined as

\[f(z) := \inf \bigg\{t\in [0,1]\mbox{ such that }\int_{[0,t]} h(x)\,\textit{d} x\ge z\bigg\}.\]

Note that it holds that $\int_A h(x)\,\textit{d} x=\mu(f^{-1}(A))$ for every measurable subset $A \subseteq [0,1]$ . We define the graphon W[h] by setting

\[W[h](x,y)=W\big(f(x\cdot \|h\|_1),\;f(y\cdot \|h\|_1)\big)\quad\mbox{for $(x,y)\in [0,1]^2$.}\]

Note that if h is the indicator function of a measurable subset A, then W[h] is obtained by restricting W to A and rescaling; if this is the case, we write W[A] for the graphon W[h]. It can be shown that

\[ t(H,W[h])=\frac{1}{\|h\|_1^{v(H)}}\int_{[0,1]^{V(H)}} \prod_{u\in V(H)}h(u) \prod_{uv\in E(H)} W(x_u,x_v) \,\textit{d} x_{V(H)}\]

holds for every graph H. In particular, it holds that

(4) \begin{equation}t(H,W)\geq \|h\|_1^{v(H)}\cdot t(H,W[h]).\end{equation}

We conclude this subsection by defining a notion of an almost independent set in a graphon. For a graphon W and $\delta>0$ , $\mathcal{H}_{\delta}(W)$ is the set of all measurable functions $h:[0,1]\to [0,1]$ with $\|h\|_1>0$ such that the density of W[h] is at most $\delta$ . The $\delta$ -independence ratio of W is defined as

\[\alpha_{\delta}(W)=\sup_{h\in\mathcal{H}_{\delta}(W)}\|h\|_1;\]

if the set $\mathcal{H}_{\delta}(W)$ is empty, then we set $\alpha_{\delta}(W)=0$ . We remark that this notion is closely related to the notion of $(\rho,d)$ -dense graphs widely used in Ramsey theory: a graph is $(\rho,d)$ -dense if any subset of at least $\rho\cdot v(G)$ vertices of G induces a subgraph with density at least d. Indeed, if a graphon W is a limit graphon of a sequence of $(\rho,d)$ -dense graphs, then $\alpha_{\delta}(W)<\rho$ for every $\delta<d$ .

2.2 Rooted graphs

A rooted graph is a graph with one or more vertices distinguished as roots. We use superscripts to emphasize that a graph is rooted and indicate the number of roots. In particular, $H^\bullet$ will denote a rooted graph with a single root, $H^{\bullet\bullet}$ will denote a rooted graph with two roots, and $H^{\bullet\cdots\bullet}$ will denote a rooted graph with three or more roots. In all rooted graphs considered in this paper, the set of roots will always form an independent set. To simplify our notation, if $H^\bullet$ is a rooted graph, v(H) and $e\left(H\right)$ denote the number of vertices and edges of $H^\bullet$ , respectively, as these quantities are the same regardless of the presence or the absence of roots. Examples of rooted graphs considered further include the following. The rooted graph $P_{n}^{\bullet}$ is the graph obtained from the n-vertex path by choosing one of its end vertices as a root. The rooted graph $K_{a,b}^{\bullet}$ is the graph obtained from the complete bipartite graph $K_{a,b}$ by choosing one of the vertices of the a-vertex part as a root. Finally, the rooted graph $K_{a|\ell,b}^{\bullet}$ is the graph obtained from $K_{a|\ell,b}$ by choosing the end vertex of the appended $\ell$ -edge path as a root.

If $G^\bullet$ and $H^\bullet$ are two rooted graphs, then $G^\bullet\oplus H^\bullet$ is the (unrooted) graph obtained by identifying their roots. Note that $K_{a|\ell,b}=P_{\ell+1}^\bullet\oplus K_{a,b}^\bullet$ . Similarly, if $G^{\bullet\bullet}$ and $H^{\bullet\bullet}$ are two rooted graphs with two roots, then $G^{\bullet\bullet}\oplus H^{\bullet\bullet}$ is the graph obtained by identifying the corresponding roots, and if $G^{\bullet\cdots\bullet}$ and $H^{\bullet\cdots\bullet}$ are two rooted graphs with the same number of roots, then $G^{\bullet\cdots\bullet}\oplus H^{\bullet\cdots\bullet}$ is the graph obtained by identifying the corresponding roots; the correspondence will always be clear from the context.

We next extend the notion of homomorphism density to rooted graphs. Let $H^{\bullet\cdots\bullet}$ be a rooted graph with k roots, and let $v_1,\ldots,v_n$ be the vertices of $H^{\bullet\cdots\bullet}$ listed in a way that the vertices $v_1,\ldots,v_k$ are the roots. If U is a kernel and $x_1,\ldots,x_k\in [0,1]$ , we define $t_{x_1,\ldots,x_k}(H^{\bullet\cdots\bullet},U)$ as

(5) \begin{equation}t_{x_1,\ldots,x_k}(H^{\bullet\cdots\bullet},U)=\int_{[0,1]^{n-k}}\prod_{v_iv_j\in E(H^{\bullet\cdots\bullet})}U(x_i,x_j)\,\textit{d} x_{k+1}\cdots dx_n.\end{equation}

Observe that if W is a graphon, then $\deg_W(x)=t_x(P_2^\bullet,W)$ for $x\in [0,1]$ . Finally, if $G^{\bullet\cdots\bullet}$ and $H^{\bullet\cdots\bullet}$ are two rooted graphs such that each has k roots and the roots induce an independent set, it holds that

(6) \begin{equation}t\big(G^{\bullet\cdots\bullet}\oplus H^{\bullet\cdots\bullet},U\big)=\int_{[0,1]^k}t_{x_1,\ldots,x_k}\big(G^{\bullet\cdots\bullet},U\big) t_{x_1,\ldots,x_k}\big(H^{\bullet\cdots\bullet},U\big)\,\textit{d} x_1\cdots d x_k\end{equation}

for every kernel U; note that the assumption that the roots of $G^{\bullet\cdots\bullet}$ and $H^{\bullet\cdots\bullet}$ form independent sets is needed for (6) to hold.

2.3 Spectral properties of graphons and kernels

We now review spectral properties of graphons and kernels; we refer to [Reference LovászLov12, 7.5] for further details. Fix a kernel U with $\|U\|_\infty\le 1$ . We can think of U as a Hilbert–Schmidt integral operator from $L_2[0,1]$ to $L_2[0,1]$ defined as

\[(Uf)(x)= \int_{0}^1 U(x,y) f(y) \,\textit{d} y.\]

Let $\lambda_1,\lambda_2,\ldots$ be the non-zero eigenvalues of U listed in the non-increasing order of the absolute value (with multiplicities), and let $f_1,f_2,\ldots$ be the corresponding orthonormal eigenfunctions, i.e. $\|f_i\|_2=1$ for every i and the functions are orthogonal to each other in $L_2[0,1]$ . Note that

\[\sum_i \lambda_i f_i(x)f_i(y)\]

converges to U in the $L_2$ -norm. We remark that if U is a graphon with density p, then $\lambda_1$ is at least p. Since we have assumed that $\|U\|_\infty\le 1$ , it holds that $(Uf_i)(x)\le\|f_i\|_2=1$ for every $x\in [0,1]$ , i.e. $\|Uf_i\|_\infty\le 1$ , which implies that $\|f_i\|_{\infty}\le \lvert\lambda_i\rvert^{-1}$ .

The spectrum of U can be used to express the density of cycles and paths. Expressing the density of cycles is easier: it holds for every $n\ge 3$ that

(7) \begin{equation}t(C_n,U) = \sum_{i} \lambda_i^n.\end{equation}

To express the density of paths, we need to introduce additional notation. Let ${\mathfrak{j}}:[0,1]\to [0,1]$ be the constant function equal to 1, and set $\alpha_i\in [0,\pi/2]$ to be the real such that $\langle {\mathfrak{j}},f_i\rangle=\cos\alpha_i$ (we may assume without loss of generality by replacing $f_i$ with $-f_i$ that the product is non-negative). Further set $\delta=1-\cos\alpha_1$ . Informally speaking, for a graphon W, $\delta$ measures how close W is to having all the degrees the same, in particular, $\delta=0$ if and only if $\deg_W(x)=p$ for almost every $x\in [0,1]$ where p is the density of W. The following holds for every $n\ge 2$ (for $n=2$ , the equality is a particular case of (7.21) in [Reference LovászLov12]):

(8) \begin{equation}t(P_n,U) = \langle {\mathfrak{j}},U^{n-1}{\mathfrak{j}}\rangle = \sum_{i} \lambda_i^{n-1}\cos^2\alpha_i.\end{equation}

In the rest of this subsection, we deal with graphons only and estimate some of the introduced parameters. These estimates will be used repeatedly in the proofs of Theorems 3.1 and 4.1. Fix a graphon W with density $p\in [0,1]$ , and let $\gamma=t(C_4,W)-p^4$ . Note that $\gamma\ge 0$ since the cycle $C_4$ has the Sidorenko property; on the other hand, $\gamma\le 4\|W-p\|_{\square}$ by the counting lemma (Lemma 2.2). Since the density of $C_4$ in W is at least $\lambda_1^4$ , it follows that

(9) \begin{equation}\lambda_1\le p+\frac{\gamma}{4p^3}\le p+\frac{\|W-p\|_{\square}}{p^3}.\end{equation}

We derive from $\lambda_1\ge p$ and (7) that

(10) \begin{equation}\lvert\lambda_i\rvert\le\gamma^{1/4}\end{equation}

holds for every $i\ge 2$ . Hence, we derive from (10) that

(11) \begin{equation}\sum_{i\ge 2} \lambda_i^m \le \gamma^{\\frac{m-4}{4}}\sum_{i\ge 2}\lambda_i^{4} \le \gamma^{m/4}\end{equation}

holds for every $m\ge 4$ . In addition, (10) yields that it holds for every $m\ge 0$ that

\[\bigg\lvert\sum_{i\ge 2}\lambda_i^m\cos^2\alpha_i\bigg\rvert\le\sum_{i\ge 2}\lvert\lambda_i\rvert^m\cos^2\alpha_i\le\max_{i\ge 2}\lvert\lambda_i\rvert^m\cdot\sum_{i\ge 2}\cos^2\alpha_i\le\max_{i\ge 2}\lvert\lambda_i\rvert^m\le\gamma^{m/4},\]

which implies by (8) that

(12) \begin{equation}\lambda_1^{m}(1-\delta)^2-\gamma^{m/4}\le t(P_{m+1},W)\le\lambda_1^{m}(1-\delta)^2+\gamma^{m/4}.\end{equation}

We next estimate $\delta$ in terms of $\gamma$ and subsequently in terms of $\|W-p\|_{\square}$ . Since the path $P_5$ has the Sidorenko property and (8) holds, we obtain that

\begin{align*} p^4 \le t(P_5,W)& = \sum_i \lambda_i^{4}\cos^2\alpha_i\le \lambda_1^4(1-\delta)^2 + \sum_{i\ge 2}\lambda_i^4= \lambda_1^4(1-\delta)^2-\lambda_1^4+\sum_i\lambda_i^4 \\& \le p^4(1-\delta)^2-p^4+\sum_i\lambda_i^4= p^4(1-\delta)^2+\gamma\le p^4(1-\delta)+\gamma.\end{align*}

It follows that

(13) \begin{equation}\delta\le\frac{\gamma}{p^4}\le\frac{4\|W-p\|_{\square}}{p^4}.\end{equation}

Since the eigenfunctions $f_i$ are orthonormal, we obtain that

(14) \begin{equation}\sum_i\cos^2\alpha_i=\sum_{i}\langle {\mathfrak{j}}, f_i\rangle^2\le\|{\mathfrak{j}}\|_2^2=1. \end{equation}

The inequality (14) implies that

(15) \begin{equation}\sum_{i\ge 2}\cos^2\alpha_i\le 1 - (1-\delta)^2 = 2\delta-\delta^2\le 2\delta.\end{equation}

In particular, $\cos\alpha_i\le 2\delta^{1/2}$ for every $i\ge 2$ . Using (8) for $n=2$ , (10) and (15), we obtain that

\[p=\sum_i\lambda_i\cos^2\alpha_i\le\lambda_1(1-\delta)^2+\gamma^{1/4}\sum_{i\ge 2}\cos^2\alpha_i\le\lambda_1(1-\delta)^2+2\delta\gamma^{1/4}.\]

This implies for $\delta\in [0,1]$ that

(16) \begin{equation}\lambda_1 \ge \frac{p-2\delta\gamma^{1/4}}{(1-\delta)^2} \ge (p-2\delta\gamma^{1/4})(1+\delta)^2 \ge p(1+2\delta) - 2\delta\gamma^{1/4}(1+\delta)^2 \ge p(1+2\delta) - 8\delta\gamma^{1/4}.\end{equation}

2.4 Estimates on densities

We now review several estimates on densities of graphs in graphons and kernels. A large number of the estimates that we present is standard and we state them explicitly just for referencing in the rest of the paper. We start with one of such estimates, which follows by the standard use of Jensen’s inequality; see, e.g., [KNN $^{+}$ 22, Proposition 1.10]. The two lemmas are also implied by the weak Hölder property that all complete bipartite graphs have since they are weakly norming [Reference HatamiHat10]; also see [Reference LovászLov12, 14.1] for in-depth discussion.

Lemma 2.3. The following holds for every graphon W and all integers m,mʹ,n such that $m\geq m'$ :

\[t(K_{m,n},W)\geq t(K_{m',n},W)^{m/m'}.\]

Two applications of Lemma 2.3 yield the following.

Lemma 2.4. The following holds for every graphon W and all integers $m, n \geq 2$ :

\[ t(K_{m,n}, W) \geq t(C_4, W)^{mn/4}.\]

The estimates in the rest of the subsection concern kernels. We start with a well-known estimate, which follows by a straightforward application of the Cauchy–Schwarz inequality.

Lemma 2.5. The following holds for any kernel U:

(17) \begin{equation}0 \leq t(K_{1,2}, U) \leq t(C_4, U)^{1/2}.\end{equation}

The next lemma follows by using Jensen’s inequality and the following two identities:

\[t(K_{1,k},U)=\int_{[0,1]} t_x(P_2^{\bullet},U)^k\,\textit{d} x\quad\mbox{and}\quad t(K_{2,k},U)=\int_{[0,1]^2} t_{x,y}(K_{2,1}^{\bullet\bullet},U)^k\,\textit{d} x\,\textit{d} y.\]

Lemma 2.6. The following holds for any kernel U with $\|U\|_\infty\le 1$ and every integer $k\ge 2$ :

\[\lvert t(K_{1,k},U)\rvert\le t(K_{1,2},U)^{k/2}\le t(K_{1,2},U)\quad\mbox{and}\quad \lvert t(K_{2,k},U)\rvert\le t(C_4,U)^{k/2}\le t(C_4,U).\]

The remaining estimates that we present were proven by Lovász in [Reference LovászLov11]; we state them with corresponding references to the statements in the paper [Reference LovászLov11], which contain them or imply them. We remark that the second inequality in Lemma 2.9 follows using Lemma 2.5.

Lemma 2.7 (Lovász [Reference LovászLov11, Lemma 3.3]) Let $f_1,\dots, f_n: [0,1]^k \to \mathbb{R}$ be bounded measurable functions such that for each variable there are at most two functions $f_i$ that depend on that variable. It holds that

\[\int_{[0,1]^k} \prod_{i\in [n]}f_i(x_1,\ldots,x_n)\,\textit{d} x_1\cdots dx_k\leq\prod_{i\in [n]}\|f_i\|_2.\]

Lemma 2.8 (Lovász [Reference LovászLov11, Corollary 3.12]). The following holds for any kernel U with $\|U\|_\infty\le 1$ and every integer $k\ge 2$ :

\[t(C_{2k}, U) \leq t(C_4, U)^{k/2}.\]

Lemma 2.9 (Lovász [Reference LovászLov11, Lemma 3.14]). The following holds for any kernel U with $\|U\|_\infty\le 1$ and every integer $k\ge 1$ :

\[t(P_{k+3},U)^4 \leq t(P_{3},U)^4 t(C_4,U)^{k}\le t(C_4,U)^{k+2}.\]

Lemma 2.10 (Lovász [Reference LovászLov11, Lemma 3.19]). The following holds for any kernel U with $\|U\|_\infty\le 1$ and every bipartite graph G with minimum degree two and girth at least four that is not a single cycle or a complete bipartite graph:

\[\lvert t(G,U)\rvert\le t(C_4,U)^{5/4}.\]

Lemma 2.11 (Lovász [Reference LovászLov11, Lemma 3.21]). The following holds for any kernel U with $\|U\|_\infty\le 1$ and any tree T that is not a star:

\[\lvert t(T,U)\rvert\le t(P_3,U)t(C_4,U)^{1/4}.\]

Lemma 2.12 (Lovász [Reference LovászLov11, Lemma 3.22]). The following holds for any kernel U with $\|U\|_\infty\le 1$ and every bipartite graph G with girth at least four that has exactly one vertex of degree one:

\[\lvert t(G,U)\rvert\le\frac{\big(t(C_4,U)+t(P_3,U)\big)\cdot t(C_4,U)^{1/8}}{2}.\]

2.5 Entropy-based estimates

We next estimate the density of a graph $K_{a|\ell,b}$ . The next lemma asserts that a graph $K_{a|\ell,b}$ has the Sidorenko property in a strong sense as $t(K_{1,2},G)\ge t(K_2,G)^2$ . Our proof is based on the entropy argument, which has been pioneered in this context by Szegedy [Reference SzegedySze14].

Lemma 2.13 Let a, b and $\ell$ be any positive even integers. It holds that for any graph G,

\[t(K_{a|\ell,b},G)\ge t(K_{1,2},G)^{(ab+\ell)/2}.\]

Proof. Fix integers a, b and $\ell$ , and a graph G, and let n be the number of vertices of G. We say that a triple $(x_1,x_2,y)$ of vertices of G is feasible if $x_1y$ and $x_2y$ are edges of G. We define several probability distributions on vertices of G and their tuples. The first distribution is the uniform distribution on $t(K_{1,2},G)n^3$ feasible triples $(x_1,x_2,y)$ ; note that the entropy of this distribution is

(18) \begin{equation}H(x_1,x_2,y)=3\log n+\log t(K_{1,2},G).\end{equation}

The second distribution is the distribution on $(a+1)$ -tuples $(x_1,\ldots,x_a,y)$ that we first choose y according to the marginal distribution of the uniform distribution on feasible triples and we then choose $x_1,\ldots,x_a$ to be neighbors of y chosen uniformly and independently of each other. Observe that the marginal distribution on y and any two of the vertices $x_1,\ldots,x_a$ is the uniform distribution on feasible triples and so the following holds:

\begin{align*}H(x_1,\ldots,x_a,y) &= \frac{a}{2}H(x_1,x_2|y)+H(y)= \frac{a}{2}H(x_1,x_2,y)-\frac{a-2}{2}H(y)\\&\ge \frac{a}{2}H(x_1,x_2,y)-\frac{a-2}{2}\log n.\end{align*}

The third distribution is the distribution on $(a+b)$ -tuples $(x_1,\ldots,x_a,y_1,\ldots,y_b)$ that we first choose $x_1,\ldots,x_a$ according to the marginal distribution derived from the second distribution and we then choose each of $y_1,\ldots,y_b$ according to the second distribution conditioned on the choice of $x_1,\ldots,x_a$ . Observe that

\begin{align*}H(x_1,\ldots,x_a,y_1,\ldots,y_b) & = b\cdot H(y|x_1,\ldots,x_a)+H(x_1,\ldots,x_a)\\& = b\cdot H(x_1,\ldots,x_a,y)-(b-1)H(x_1,\ldots,x_a)\\& \ge b\cdot H(x_1,\ldots,x_a,y)-a(b-1)\log n\\& \ge \frac{ab}{2}H(x_1,x_2,y)-\frac{(a-2)b}{2}\log n-a(b-1)\log n\\& = \frac{ab}{2}H(x_1,x_2,y)-\frac{3ab-2a-2b}{2}\log n.\end{align*}

Finally, the last distribution, which is a distribution on $(a+b+\ell)$ -tuples of vertices, is obtained as follows. We first choose $(x_1,\ldots,x_a,y_1,\ldots,y_b)$ according to the third distribution; note that the marginal distribution of $x_1$ is the same as its marginal distribution of the uniform distribution on feasible triples. Next choose $(x_1,y'_1,x'_1)$ uniformly among all feasible triples with the first coordinate equal to $x_1$ , then $(x'_1,y'_2,x'_2)$ uniformly among all feasible triples with the first coordinate equal to $x'_1$ , then $(x'_2,y'_3,x'_3)$ uniformly among all feasible triples with the first coordinate equal to $x'_2$ and so on until the triple $(x'_{\ell/2-1},y'_{\ell/2},x'_{\ell/2})$ has been chosen. Observe that

\[H(x_1,y'_1,x'_1,\ldots,y'_{\ell/2},x'_{\ell/2}) =\frac{\ell}{2} H(y,x_2|x_1)+H(x_1)=\frac{\ell}{2} H(x_1,y,x_2)-\bigg(\frac{\ell}{2}-1\bigg)H(x_1).\]

It follows that $H(x_1,\ldots,x_a,y_1,\ldots,y_b,y'_1,x'_1,\ldots,y'_{\ell/2},x'_{\ell/2})$ is equal to

\begin{align*}& H(x_1,y'_1,x'_1,\ldots,y'_{\ell/2},x'_{\ell/2})+H(x_1,\ldots,x_a,y_1,\ldots,y_b)-H(x_1) \\&\quad \ge \frac{ab+\ell}{2}H(x_1,x_2,y)-\frac{3ab-2a-2b}{2}\log n-\frac{\ell}{2}H(x_1) \\&\quad \ge \frac{ab+\ell}{2}H(x_1,x_2,y)-\frac{3ab-2a-2b+\ell}{2}\log n \\&\quad = (a+b+\ell)\log n+\frac{ab+\ell}{2}\log t(K_{1,2},G),\end{align*}

where the last inequality is implied by (18). Since $H(x_1,\ldots,x_a,y_1,\ldots,y_b,y'_1,x'_1,\ldots,y'_{\ell/2},x'_{\ell/2})$ is at most $\log\big(t(K_{a|\ell,b},G)n^{a+b+\ell}\big)$ , we conclude that $\log t(K_{a|\ell,b},G)\ge\frac{ab+\ell}{2}\log t(K_{1,2},G)$ , i.e. $t(K_{a|\ell,b},G)\ge t(K_{1,2},G)^{(ab+\ell)/2}$ as desired.

Our second estimate on the density of a graph $K_{a|\ell,b}$ is a quantitative bound on the density of $K_{a|\ell,b}$ in a graphon W depending on its distance from the constant graphon with the same density.

Lemma 2.14. For all positive even integers a, b and $\ell$ such that ${\ell} \leq ab/4$ , it holds that

\[t(K_{a|\ell,b},W)\ge p^{ab+\ell}\big(1+10^{-9}\|W-p\|_{\square}^{16}\big))^{ab/4+\ell/4}\]

for every graphon W with density p.

Proof. Fix integers a, b and $\ell$ , and a graphon W with density p; set $\varepsilon=\|W-p\|_{\square}$ . Let A be the set of $x\in [0,1]$ such that $\deg_W(x)\le p(1-0.001\varepsilon^5)$ . We distinguish two cases depending on the measure of A.

The first case is the case when $\mu(A)<0.001p\varepsilon^5$ , i.e. the degree of most of the vertices of W is close to p. Consider the graphon $W_1$ defined as

\[W_1(x,y)=\begin{cases}0 & \mbox{if $x\in A$ or $y\in A$, and} \\W(x,y) & \mbox{otherwise.}\end{cases}\]

Observe that

(19) \begin{equation}\deg_{W_1}(x)\ge p(1-0.001\varepsilon^5)-\mu(A)\geq p(1-0.002\varepsilon^5)\end{equation}

for every $x\not\in A$ . It follows that the density $p_1$ of $W_1$ is at least

\[ p_1 \geq (1-\mu(A)) (1-0.002p\varepsilon^5)\geq (1-0.001p\varepsilon^5)p(1-0.002\varepsilon^5) \geq p(1-0.003\varepsilon^5).\]

Note that the cut distance between W and $W_1$ is at most $2\mu(A)+\mu(A)^2\leq 3\mu(A)\leq 0.003p\varepsilon^5$ . Hence, the triangle inequality implies that

\[\|W_1-p_1\|_{\square}\ge \|W-p\|_{\square} - \|W-W_1\|_{\square} - \lvert p-p_1\rvert \ge \varepsilon-0.006p \varepsilon^5 \ge 0.994\varepsilon.\]

Lemma 2.1 now yields that

\[t(C_4,W_1) \ge p_1^4+\frac{0.994^4\varepsilon^4}{8}\ge p_1^4(1+0.122\varepsilon^4)\ge p^4\big(1-0.003\varepsilon^5\big)^4(1+0.122\varepsilon^4)\ge p^4\big(1+0.1\varepsilon^4\big).\]

Hence, Lemma 2.4 implies (the last inequality follows from $\ell\leq ab/4$ ) that

\[t(K_{a,b},W_1)\ge t(C_4, W_1)^{ab/4}\geq p^{ab}\big(1+0.1\varepsilon^4\big)^{ab/4}\geq p^{ab}\big(1+0.03\varepsilon^4\big)^{ab/4+2\ell}.\]

Therefore, we obtain using (19) that

\[ t(K_{a|\ell,b},W_1) \ge p^{ab+\ell}\big(1+0.03\varepsilon^4\big)^{ab/4+2\ell}\big(1-0.002\varepsilon^5\big)^\ell\ge p^{ab+\ell}\big(1+0.03\varepsilon^4\big)^{ab/4+\ell}.\]

As $t(K_{a|\ell,b},W) \geq t(K_{a|\ell,b},W_1)$ , the estimate in the statement of the lemma follows.

We next analyze the complementary case, i.e. the case when the measure of A is at least $0.001p\varepsilon^5$ . We obtain the following estimate on $t(K_{1,2},W)$ using the Cauchy–Schwarz inequality:

\begin{align*}t(K_{1,2},W) & =\int_{[0,1]} \deg_W(x)^2 \,\textit{d} x = \int_{A} \deg_W(x)^2 \,\textit{d} x + \int_{[0,1]\setminus A} \deg_W(x)^2 \,\textit{d} x \\& \geq\frac{1}{\mu(A)}\bigg(\int_{A}\deg_W(x)\,\textit{d} x\bigg)^2 +\frac{1}{1-\mu(A)}\bigg(\int_{[0,1]\setminus A}\deg_W(x)\,\textit{d} x\bigg)^2 \\& =\frac{1}{\mu(A)}\bigg(\int_{A}\deg_W(x)\,\textit{d} x\bigg)^2 +\frac{1}{1-\mu(A)}\bigg(p-\int_{A}\deg_W(x)\,\textit{d} x\bigg)^2 \\& = p^2 + \frac{\mu(A)}{1-\mu(A)}\bigg(p-\frac{\int_{A}\deg_W(x)\,\textit{d} x}{\mu(A)}\bigg)^2 \\& \geq p^2 + \frac{0.001p\varepsilon^5}{1-0.001p\varepsilon^5}(0.001p\varepsilon^5)^2 \geq p^2 + 10^{-9}\varepsilon^{15}p^3.\end{align*}

Observe that $\varepsilon=\|W-p\|_{\square}\le\|W\|_{\square}+\|p\|_{\square}=2p$ and so $t(K_{1,2},W)\ge p^2(1+10^{-9}\varepsilon^{16}/2)$ . Therefore, Lemma 2.13 now yields that

\[ t(K_{a|\ell,b},W) \ge t(K_{1,2},W)^{(ab+\ell)/2}\ge p^{ab+\ell}(1+10^{-9}\varepsilon^{16}/2)^{ab/2+\ell/2} \ge p^{ab+\ell}(1+10^{-9}\varepsilon^{16})^{ab/4+\ell/4}.\]

The estimate given in the statement of the lemma is now established.

3. Locally Sidorenko component

In this section, we establish that a certain family of graphs that contain any fixed high-girth graph as an induced subgraph has the Sidorenko property in a local sense. As discussed in §§ 1.1 and 1.2, the main contribution of this section is Theorem 3.1 asserting that the value of $\varepsilon_0$ is independent of $\ell$ and so, when $H^\bullet$ is fixed, of the graph $H^\bullet\oplus P_{\ell}^\bullet$ . The proof is inspired by the proof of an extension of a result by Lovász [Reference LovászLov11] due to Fox and the last author [Reference Fox, Wei, Drmota, Kang, Krattenthaler and NešetřilFW17]; however, it does not follow from either of these results even when the bound is not required to be uniform. We remark that the lower bound of 50 on the girth of G given in Theorem 3.1 can certainly be decreased, possibly all the way to 4, at the expense of making the proof of Theorem 3.1 significantly more technical; we decided to prove the theorem with the lower bound of 50 as proving it with an even larger lower bound on the girth would not simplify the proof substantially.

Theorem 3.1. For every graph G with girth at least 50 and every real number $p_0 \in (0,1)$ , there exist a real $\varepsilon_0>0$ and a connected rooted graph $H^\bullet$ containing G as an induced subgraph such that the following holds for every graphon W with density $p \geq p_0$ and $\|W-p\|_{\square}\leq\varepsilon_0$ :

\[t(H^\bullet\oplus P_{\ell}^\bullet,W)\ge p^{e\left(H\right)+\ell-1}\]

for every integer $\ell\ge 9$ .

Proof. Fix a graph G and a real $p_0\in (0,1)$ . The graph $H^\bullet$ is obtained from the graph G by attaching a 3-edge path and a 12-edge path to two different vertices of G, attaching a cycle of length four to the end vertex of the 12-edge path not contained in G, and choosing the end vertex of the 3-edge path not contained in G as the root. The construction of $H^\bullet$ is illustrated in Figure 2. In what follows, we use H for the non-rooted graph with the same vertices and edges as $H^\bullet$ , i.e. $H^\bullet$ can be obtained from H be distinguishing the vertex $v_0$ as the root.

Figure 2.

The graph $H^\bullet$ from the statement of Theorem 3.1.

We show that the statement of the theorem holds for $\varepsilon_0$ chosen as

\[\varepsilon_0=\min\bigg\{\frac{p_0^4}{10^{12}},\frac{p_0^{64}}{2^{8e\left(H\right)+90}}\bigg\}.\]

In particular, $\varepsilon_0$ satisfies that

(20) \begin{equation}\frac{3\varepsilon_0^{1/4}}{p_0}\le\frac{1}{100}\bigg(1-\frac{4\varepsilon_0}{p_0^4}\bigg)^2.\end{equation}

We remark that the estimate (20) will be used later to show that the middle inequality in (31) holds for all $m\ge 2$ and the first inequality in (33) holds for all $m=2,\ldots,\ell$ whenever $\lambda_1\in [p_0,1]$ , $\delta\in [0,4\varepsilon_0/p_0^4]$ and $\gamma\in [0,4\varepsilon_0]$ .

Consider a graph $H^\bullet\oplus P_{\ell}^\bullet$ for $\ell\ge 9$ and a graphon W with density $p\ge p_0$ such that $\|W-p\|_{\square}\leq\varepsilon_0$ . To simplify our notation, we write $H_{\ell}$ for $H^\bullet\oplus P_{\ell}^\bullet$ . The vertices of the path $P_{\ell}^\bullet$ are denoted by $v_0,\ldots,v_{\ell-1}$ in a way that $v_0$ is the root; the two internal vertices of the 3-edge path attached to G when constructing $H^\bullet$ will be denoted by $v_{-2}$ and $v_{-1}$ in a way that $v_{-1}$ is the neighbor of $v_0$ . The notation is illustrated in Figure 3.

Figure 3.

The graph $H_\ell=H^\bullet\oplus P_{\ell}^\bullet$ from the statement of Theorem 3.1 and notation concerning the vertices $v_{-2},v_{-1},\ldots,v_{\ell-1}$ used in its proof.

Let $U=W-p$ and observe that $t(K_2,U)=0$ (as the density of W is p) and $\|U\|_\infty\le 1$ . Since a path $P_{m}$ has the Sidorenko property for every $m\ge 1$ , we obtain that

(21) \begin{equation}t(P_{m},p+U)=t(P_{m},W)\ge p^{m-1}\end{equation}

for every $m\ge 1$ . The density of $H_{\ell}$ can be expressed (see [Reference LovászLov11] and [Reference LovászLov12, Proof of Proposition 16.27]) as

(22) \begin{equation}t(H_{\ell},W)=t(H_{\ell},p+U)= p^{e\left(H\right)+\ell-1}+\sum_{\substack{F_0\subseteq E(H_{\ell})\\F_0\not=\emptyset}}p^{e\left(H\right)+\ell-1-\lvert F_0\rvert}t(\langle F_0\rangle,U).\end{equation}

Hence, in order to establish the statement of the theorem, it is enough to show the following (note that the sum from (22) is divided by $p^{e\left(H\right)}$ ):

(23) \begin{equation}\sum_{\substack{F_0\subseteq E(H_{\ell})\\F_0\not=\emptyset}}p^{\ell-1-\lvert F_0\rvert}t(\langle F_0\rangle,U)\ge 0.\end{equation}

We split the non-empty $2^{e\left(H\right)+\ell-1}-1$ subsets $F_0$ of $E(H_{\ell})$ into eight groups given below, which we analyze separately. We say that a component of $\langle F_0\rangle$ is a core component if it contains an edge of $H^\bullet$ .

1. (a) The graph $\langle F_0\rangle$ has no core component.

2. (b) The graph $\langle F_0\rangle$ has a single core component and this component is $C_4$ .

3. (c) The graph $\langle F_0\rangle$ has a single core component and this component is a star.

4. (d) The graph $\langle F_0\rangle$ has a core component containing the vertex $v_8$ .

5. (e) The graph $\langle F_0\rangle$ has no core component containing $v_8$ and there is a core component containing a cycle of G.

6. (f) The graph $\langle F_0\rangle$ has no core component containing $v_8$ and the only cycle in $\langle F_0\rangle$ is $C_4$ but the core component containing $C_4$ is not just $C_4$ .

7. (g). The graph $\langle F_0\rangle$ has no core component containing $v_8$ , all core components are acyclic or $C_4$ , and at least one of the acyclic core components is not a star.

8. (h). The graph $\langle F_0\rangle$ has no core component containing $v_8$ , all core components are stars or $C_4$ , and there are at least two core components.

We briefly verify that each subset $F_0$ belongs to exactly one of the groups (a)–(h). Since any core component containing the vertex $v_8$ can be neither $C_4$ nor a star, group (d) is disjoint from the remaining seven groups. If $F_0$ is not covered by group (a) or (d), then $\langle F_0\rangle$ has at least one core component and no core component of $\langle F_0\rangle$ contains $v_8$ . We restrict our attention to such subsets $F_0$ in the rest of this paragraph. If $\langle F_0\rangle$ has a core component containing a cycle of G (note that the length of this cycle is at least 50), then $F_0$ belongs to group (e) and it cannot belong to any other group. If $\langle F_0\rangle$ has no core component containing a cycle of G but it has a core component that contains the cycle $C_4$ and this core component is not solely this cycle, then $F_0$ belongs to group (f) and it cannot belong to any other group. Hence, we can further restrict our attention to only those subsets $F_0$ such that no core component of $\langle F_0\rangle$ contains $v_8$ and each core component of $\langle F_0\rangle$ is either acyclic or solely the cycle $C_4$ . If one of core components is not a star, then $F_0$ belongs to group (g) and it cannot belong to any other group. Otherwise, all core components of $\langle F_0\rangle$ are stars or solely the cycle $C_4$ . If $F_0$ has a single core component, then it belongs to group (b) or group (c); otherwise, i.e. when $F_0$ has at least two core components, it belongs group (h). We conclude that each subset $F_0$ belongs to exactly one of the groups (a)–(h).

We next analyze the contribution of the terms for $F_0$ based on the groups (a)–(h) in Claims 3.2–3.8. Claims 3.2 and 3.8 will readily yield that the left-hand side of (23) is at least

\begin{align*}& t(P_{\ell},p+U)(t(P_3,U)+t(C_4,U))-t(P_{\ell},p+U)\bigg(\frac{t(P_3,U)}{2}+\frac{3t(C_4,U)}{8}\bigg)\\&\quad\ge t(P_{\ell},p+U)\bigg(\frac{t(P_3,U)}{2}+\frac{5t(C_4,U)}{8}\bigg)\ge 0,\end{align*}

which establishes that (23) holds. In particular, when Claims 3.2 and 3.8 are established, the proof of the theorem will be completed. We remark that Claims 3.3–3.7 describe auxiliary results used to prove Claim 3.8.

Claim 3.2 The sum of the terms in the left-hand side of (23) that involve $F_0$ from one of the groups (a)–(c) is at least

\[t(P_{\ell},p+U)(t(P_3,U)+t(C_4,U)).\]

Proof of Claim 3.2. The sum of the terms that involve a set $F_0$ from group (a) is equal to

(24) \begin{equation}\sum_{\substack{F\subseteq E(P_{\ell})\\F\not=\emptyset}}p^{\ell-1-\lvert F\rvert}t(\langle F\rangle,U)=\sum_{F\subseteq E(P_{\ell})}p^{\ell-1-\lvert F\rvert}t(\langle F\rangle,U)-p^{\ell-1}=t(P_{\ell},p+U)-p^{\ell-1}\ge 0,\end{equation}

where the last inequality follows from the fact that $P_{\ell}$ has the Sidorenko property and $p+U=W$ .

Along the same lines, we derive that the sum of the terms that involve a set $F_0$ from group (b) (note that such $F_0$ contain all the edges of $C_4$ and some edges of $P_{\ell}^\bullet$ , and $F_0$ can consist of the four edges of $C_4$ only) is equal to

(25) \begin{equation}\sum_{F\subseteq E(P_{\ell})}p^{\ell-1-\lvert F\rvert-4}t(\langle F\rangle,U)t(C_4,U)=t(P_{\ell},p+U)\frac{t(C_4,U)}{p^4}\ge t(P_{\ell},p+U)t(C_4,U).\end{equation}

It remains to analyze the sum of terms that involve a set $F_0$ from group (c). For any edge e of $H^\bullet$ , the sum of the terms that involve a set $F_0$ from group (c) such that the core component of $\langle F_0\rangle$ is formed by the edge e only is equal to zero as $t(K_2,U)=0$ . Hence, the sum of the terms that involve a set $F_0$ from group (c) is equal to:

• • the sum of the terms that involve such $F_0$ with $\{v_{-2}v_{-1},v_{-1}v_0\}\subseteq F_0$ ;

• • the sum of the terms that involve such $F_0$ with $\{v_{-1}v_0,v_0v_1\}\subseteq F_0$ ; and

• • the sum of the terms that involve such $F_0$ that the core component of $F_0$ has at least two edges but does not contain $v_0$ .

The sum of the terms that involve such $F_0$ with $\{v_{-2}v_{-1},v_{-1}v_0\}\subseteq F_0$ is equal to (note that $t(K_{1,2},U)\ge 0$ by Lemma 2.5)

(26) \begin{equation}\sum_{F\subseteq E(P_{\ell-1})}p^{\ell-2-\lvert F\rvert-1}t(\langle F\rangle,U)t(K_{1,2},U)= t(P_{\ell-1},p+U)\frac{t(K_{1,2},U)}{p}\ge 0.\end{equation}

Similarly, the sum of the terms that involve such $F_0$ with $\{v_{-1}v_0,v_0v_1\}\subseteq F_0$ is equal to

(27) \begin{equation}\sum_{F\subseteq E(P_{\ell-2})}p^{\ell-3-\lvert F\rvert}t(\langle F\rangle,U)t(K_{1,2},U)= t(P_{\ell-2},p+U)t(K_{1,2},U)\ge 0.\end{equation}

Finally, sum of the terms that involve such $F_0$ from group (c) such that the core component of $F_0$ has at least two edges but does not contain $v_0$ is equal to the following:

(28) \begin{align}& \sum_{F\subseteq E(P_{\ell})}\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\sum_{d=2}^{\deg_H(v)}\binom{\deg_H(v)}{d}p^{\ell-1-\lvert F\rvert-d}t(\langle F\rangle,U)t(K_{1,d},U) \nonumber \\&\quad = \bigg(\sum_{F\subseteq E(P_{\ell})}p^{\ell-1-\lvert F\rvert}t(\langle F\rangle,U)\bigg)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\sum_{d=2}^{\deg_H(v)}\binom{\deg_H(v)}{d}p^{-d}t(K_{1,d},U) \nonumber \\&\quad= t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\sum_{d=2}^{\deg_H(v)}\binom{\deg_H(v)}{d}p^{-d}t(K_{1,d},U). \end{align}

Since it holds that $t(K_{1,1},U)=t(K_2,U)=0$ , we obtain that (28) is equal to

(29) \begin{align}& t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\sum_{d=1}^{\deg_H(v)}\binom{\deg_H(v)}{d}p^{-d}t(K_{1,d},U) \nonumber \\&\quad = t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\sum_{d=1}^{\deg_H(v)}\binom{\deg_H(v)}{d}\int_{[0,1]}\bigg(\frac{t_x(K_2^\bullet,U)}{p}\bigg)^d\,\textit{d} x \nonumber \\&\quad = t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\int_{[0,1]}\bigg(1+\frac{t_x(K_2^\bullet,U)}{p}\bigg)^{\deg_H v}-1\,\textit{d} x. \end{align}

Recall that Pascal’s inequality asserts $(1+x)^n\ge 1+nx$ for all integers $n\ge 0$ and reals $x\ge -1$ . As $U\ge -p$ , it holds that $t_x(K_2^\bullet,U)\ge -p\ge -1$ and so (29) is at least

(30) \begin{align}& t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\int_{[0,1]}\bigg(1+\frac{(\deg_H v-1)t_x(K_2^\bullet,U)}{p}\bigg)\bigg(1+\frac{t_x(K_2^\bullet,U)}{p}\bigg)-1\,\textit{d} x \nonumber \\&\quad = t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\int_{[0,1]}\frac{\deg_H v\cdot t_x(K_2^\bullet,U)}{p}+\frac{(\deg_H v-1)t_x(K_2^\bullet,U)^2}{p^2}\,\textit{d} x \nonumber \\&\quad = t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}\deg_H v\,\frac{t(K_2,U)}{p}+(\deg_H v-1)\frac{t(K_{1,2},U)}{p^2} \nonumber \\&\quad = t(P_{\ell},p+U)\sum_{v\in V(H)\setminus\{v_0,v_{-1}\}}(\deg_H v-1)\frac{t(K_{1,2},U)}{p^2}\ge t(P_{\ell},p+U)t(K_{1,2},U),\end{align}

where the last inequality follows since $p\le 1$ and the degree of at least one vertex of H different from $v_0$ and $v_{-1}$ is at least two.

Since the quantities estimated in (24), (26) and (27) are non-negative, the sum of the terms that involve a set $F_0$ from one of the groups (a)–(c) is at least the sum of the final estimates given in (25) and (30), i.e. at least $t(P_{\ell},p+U)(t(K_{1,2},U)+t(C_4,U))$ . This yields the bound stated in the claim.

Before we proceed with proving Claims 3.3–3.7, we recall an estimate on the density of $P_{\ell}$ in $W=p+U$ from § 2.3 and provide more refined estimates that are needed in the proofs of some of the claims. Let $\lambda_1$ be the largest eigenvalue of W viewed as a Hilbert–Schmidt operator on $L_2[0,1]$ , let $\gamma=t(C_4,W)-p^4$ and let $\delta$ be defined as in § 2.3. Recall that $\gamma\le 4\varepsilon_0$ by (3), $p\le\lambda_1\le p+\varepsilon_0/p^3$ by (9), and $\delta\le 4\varepsilon_0/p^4$ by (13). By (12), it holds that

\[\lambda_1^{m}(1-\delta)^2-\gamma^{m/4}\le t(P_{m+1},p+U)\le\lambda_1^{m}(1-\delta)^2+\gamma^{m/4}\]

for every integer $m\ge 0$ . Next, the choice of $\varepsilon_0$ implies that $\gamma^{1/4}\le (4p_0^4/10^{12})^{1/4}\le p_0/700$ and $\delta\le 4\varepsilon_0/p^4\le 10^{-11}$ , and so we obtain that

(31) \begin{align}\frac{t(P_m,p+U)}{t(P_{m+1},p+U)}& \le\frac{\lambda_1^{m-1}(1-\delta)^2+\gamma^{(m-1)/4}}{\lambda_1^{m}(1-\delta)^2-\gamma^{m/4}} \nonumber \\& \le\frac{\lambda_1^{m-1}(1-10^{-11})^2+(p_0/700)^{m-1}}{\lambda_1^{m}(1-10^{-11})^2-(p_0/700)^m} \nonumber \\& \le\frac{\lambda_1^{m-1}(1-10^{-11})^2+(\lambda_1/700)^{m-1}}{\lambda_1^{m}(1-10^{-11})^2-(\lambda_1/700)^m} \nonumber \\& \le\frac{(1-10^{-11})^2+1/700}{(1-10^{-11})^2-1/700^2}\cdot\frac{1}{\lambda_1}\le \frac{101}{100\lambda_1} \le \frac{101}{100p}\end{align}

for every integer $m\ge 2$ ; since $t(P_1,p+U)=1$ and $t(P_2,p+U)=p$ , the estimate (31) also holds for $m=1$ . Hence, the following holds for every $i=0,\ldots,8$ :

(32) \begin{equation}t(P_{\ell-i},p+U)\le \bigg(\frac{101}{100p}\bigg)^i t(P_{\ell},p+U)\le \frac{2}{p^8}t(P_{\ell},p+U)\le \frac{2}{p_0^{8}}t(P_{\ell},p+U).\end{equation}

Similarly to (31), the choice of $\varepsilon_0$ implies that the following holds for every integer $m=2,\ldots,\ell$ :

(33) \begin{equation}\frac{t(P_{m},p+U)}{t(P_{\ell},p+U)^{(m-1)/(\ell-1)}}\le\frac{\lambda_1^{m-1}(1-\delta)^2+\gamma^{(m-1)/4}}{\big(\lambda_1^{\ell-1}(1-\delta)^2-\gamma^{(\ell-1)/4}\big)^{\frac{m-1}{\ell-1}}}\le\frac{101}{100}.\end{equation}

If $m=1$ , the left-hand side of (33) is 1, and so the estimate (33) also holds for $m=1$ .

Claim 3.3 The absolute value of the sum of the terms on the left-hand side of (23) that involve $F_0$ from group (d) is at most

\[\frac{1}{8}t(P_{\ell},p+U)t(C_4,U).\]

Proof of Claim 3.3. Consider a set $F_0$ from group (d). Let $F_c$ be the edges of $F_0$ contained in the core components of $\langle F_0\rangle$ , and let k be the largest index such that $v_k$ is contained in a core component of $F_0$ . Note $k\ge 8$ by the definition of group (d). Let $S^\bullet$ be the rooted graph obtained from $\langle F'\rangle$ by removing the path $v_0\cdots v_k$ and choosing the vertex $v_0$ to be the root. Observe that

\begin{align*}\lvert t(\langle F_c\rangle,U)\rvert& = \bigg\lvert\int_{[0,1]}t_x(P_{k+1}^\bullet,U)t_x(S^\bullet,U)\,\textit{d} x\bigg\rvert \\& \le \bigg(\int_{[0,1]}t_x(P_{k+1}^\bullet,U)^2\,\textit{d} x\bigg)^{1/2}\bigg(\int_{[0,1]}t_x(S^\bullet,U)^2\,\textit{d} x\bigg)^{1/2} \\& \le \bigg(\int_{[0,1]}t_x(P_{k+1}^\bullet,U)^2\,\textit{d} x\bigg)^{1/2}\,\textit{d} x=t(P_{2k+1},U)^{1/2}\le t(C_4,U)^{k/4},\end{align*}

where the last inequality follows from Lemma 2.9. As there are at most $2^{e\left(H\right)}$ choices of a set $F_c$ such that a core component of $F_0$ contains $v_k$ but not $v_{k+1}$ , the absolute value of the sum of the terms that involve $F_0$ from group (d) is at most

(34) \begin{equation}2^{e\left(H\right)}\bigg(t(C_4,U)^{\ell/4}+\sum_{k=8}^{\ell-1}t(P_{\ell-k},p+U)t(C_4,U)^{k/4}\bigg).\end{equation}

Using (33), we estimate the sum in (34) as follows:

\begin{align*}&t(C_4,U)^{\ell/4}+\sum_{k=8}^{\ell-1}t(P_{\ell-k},p+U)t(C_4,U)^{k/4}\\&\quad \le t(C_4,U)^{\ell/4}+\frac{101}{100}\sum_{k=8}^{\ell-1}t(P_{\ell},p+U)^{\frac{\ell-k-1}{\ell-1}}t(C_4,U)^{k/4} \\&\quad \le \frac{101}{100}\sum_{k=8}^{\ell}t(P_{\ell},p+U)^{\frac{\ell-k-1}{\ell-1}}t(C_4,U)^{k/4}.\end{align*}

We next estimate the last sum using that $t(P_{\ell},p+U)\ge p^{\ell-1}$ :

\begin{align*}\frac{101}{100} \sum_{k=8}^{\ell}t(P_{\ell},p+U)^{\frac{\ell-k-1}{\ell-1}}t(C_4,U)^{k/4}& \le \frac{101}{100}t(P_{\ell},p+U)\sum_{k=8}^{\ell}\bigg(\frac{t(C_4,U)^{1/4}}{t(P_{\ell},p+U)^{\frac{1}{\ell-1}}}\bigg)^k \\& \le \frac{101}{100}t(P_{\ell},p+U)\sum_{k=8}^{\ell}\bigg(\frac{t(C_4,U)^{1/4}}{p}\bigg)^k \\& = \frac{101}{100}t(P_{\ell},p+U)\frac{t(C_4,U)^2}{p^8}\sum_{m=0}^{\ell-8}\bigg(\frac{t(C_4,U)^{1/4}}{p}\bigg)^m \\& \le \frac{101}{100}t(P_{\ell},p+U)\frac{t(C_4,U)^2}{p^8}\sum_{m=0}^{\ell-8}\bigg(\frac{(4\varepsilon_0)^{1/4}}{p}\bigg)^m,\end{align*}

which we further estimate using $\varepsilon_0\le p_0^4/10^{12}$ to be at most

\begin{align*}\frac{101}{100}t(P_{\ell},p+U)\frac{t(C_4,U)^2}{p^8}\sum_{m=0}^{\ell-8}\bigg(\frac{p_0}{100p}\bigg)^m& \le \frac{101}{100}t(P_{\ell},p+U)\frac{t(C_4,U)^2}{p^8}\sum_{m=0}^{\infty}\bigg(\frac{1}{100}\bigg)^m\\& \le 2t(P_{\ell},p+U)\frac{t(C_4,U)^2}{p^8}.\end{align*}

We now plug in this estimate to (34) and derive using (3) and the choice of $\varepsilon_0$ that the absolute value of the sum of the terms that involve $F_0$ from group (d) is at most

\[2^{e\left(H\right)+1}\cdot\frac{t(P_{\ell},p+U)t(C_4,U)^2}{p^8}\le 2^{e\left(H\right)+1}\cdot\frac{4\varepsilon_0 t(P_{\ell},p+U)t(C_4,U)}{p^8}\le\frac{1}{8}t(P_{\ell},p+U)t(C_4,U).\]

The proof of the claim is now completed.

Claim 3.4. The absolute value of the sum of the terms on the left-hand side of (23) that involve $F_0$ from group (e) is at most

\[\tfrac{1}{8}t(P_{\ell},p+U)\big(t(P_3,U)+t(C_4,U)\big).\]

Proof of Claim 3.4. Consider a set $F_0$ such that a core component of $\langle F_0\rangle$ contains a cycle of G. Let $F_c$ be the edges of $F_0$ contained in the core components of $\langle F_0\rangle$ , let C be the shortest cycle of G contained in $\langle F_c\rangle$ , let $L\ge 50$ be the length of C, and let q be the number of vertices of degree at least three in $\langle F_c\rangle$ that are contained in C. If $q\le 7$ , a part of the cycle C is an 8-edge path whose all internal vertices have degree two in $\langle F_c\rangle$ . Let $S^{\bullet\bullet}$ be the rooted graph obtained from $\langle F_c\rangle$ by removing the edges of such an 8-edge path and choosing the end vertices of the removed path to be two roots of $S^{\bullet\bullet}$ . We obtain using the Cauchy–Schwarz inequality and Lemma 2.8 that

(35) \begin{align}\lvert t(\langle F_c\rangle,U)\rvert& = \bigg\lvert\int_{[0,1]^2}t_{x,x'}(P_9^{\bullet\bullet},U)t_{x,x'}(S^{\bullet\bullet},U)\,\textit{d} x\,\textit{d} x'\bigg\rvert \nonumber \\& \le \bigg(\int_{[0,1]}t_{x,x'}(P_9^{\bullet\bullet},U)^2\,\textit{d} x\,\textit{d} x'\bigg)^{1/2}\bigg(\int_{[0,1]}t_{x,x'}(S^{\bullet\bullet},U)^2\,\textit{d} x\,\textit{d} x'\bigg)^{1/2} \nonumber \\& \le t(C_{16},U)^{1/2}\le t(C_4,U)^2. \end{align}

We next assume that $q\ge 8$ . Let $v_1,\ldots,v_4$ be any four vertices of C with degree at least three in $\langle F_c\rangle$ such that no two of them are consecutive on the cycle C; the choice of C as the shortest cycle contained in G implies that the vertices $v_1,\ldots,v_4$ form an independent set. Let $V_i$ for $i\in [4]$ be the set consisting of the vertex $v_i$ and the vertices at distance at most two from $v_i$ in $\langle F_c\rangle$ that are not contained in the cycle C; see Figure 4. Observe that the sets $V_1,\ldots,V_4$ are disjoint and there is no edge joining a vertex of $V_i$ and $V_j$ for $i\not=j$ ; otherwise, $\langle F_c\rangle$ would contain a cycle shorter than C, which would be formed by a path from $v_i$ through $V_i$ and then $V_j$ back to $v_j$ and the shorter of the two parts of C delimited by $v_i$ and $v_j$ . For $i=1,\ldots,4$ , let $T_i^{\bullet\cdots\bullet}$ be the rooted graph obtained from the subgraph of $\langle F_c\rangle$ induced by $V_i$ by choosing the vertex $v_i$ and all vertices at distance exactly two from $v_i$ to be the roots. Furthermore, let $S^{\bullet\cdots\bullet}$ be the graph obtained from $\langle F_c\rangle$ by deleting the non-root vertices of $T_1^{\bullet\cdots\bullet},\ldots,T_4^{\bullet\cdots\bullet}$ and choosing the other vertices shared with $T_1^{\bullet\cdots\bullet},\ldots,T_4^{\bullet\cdots\bullet}$ as roots. Let m be the number of roots of $S^{\bullet\cdots\bullet}$ . Observe that it holds that (we omit the exact subscripts at the functions t for clarity)

\[\lvert t(\langle F_c\rangle,U)\rvert=\bigg\lvert\int_{[0,1]^m}t_{\cdots}(S^{\bullet\cdots\bullet},U)\prod_{i=1}^4 t_{\cdots}(T_i^{\bullet\cdots\bullet},U)\,\textit{d} x_1\cdots dx_m\bigg\rvert.\]

For $i=1,\ldots,4$ , we write $T_i^2$ for the graph obtained by taking two copies of $T_i^{\bullet\cdots\bullet}$ and identifying the pairs of corresponding roots; see Figure 5. By Lemma 2.7, we obtain using that $\|U\|_{\infty}\le 1$ that

(36) \begin{align}\lvert t(\langle F_c\rangle,U)\rvert& \le \bigg(\int_{[0,1]^m}t_{\cdots}(S^{\bullet\cdots\bullet},U)^2\,\textit{d} x_1\cdots dx_m\bigg)^{1/2}\prod_{i=1}^4\bigg(\int_{[0,1]^m}t_{\cdots}(T_i^{\bullet\cdots\bullet},U)^2\,\textit{d} x_1\cdots d x_m\bigg)^{1/2}\nonumber\\& \le\prod_{i=1}^4\bigg(\int_{[0,1]^m}t_{\cdots}(T_i^{\bullet\cdots\bullet},U)^2\,\textit{d} x_1\cdots dx_m\bigg)^{1/2}=\prod_{i=1}^4 t(T_i^2,U)^{1/2}.\end{align}

Consider $i\in [4]$ . If the vertex $v_i$ has degree one in $T_i^{\bullet\cdots\bullet}$ , then $T_i^2$ is the complete bipartite graph $K_{2,d}$ where d is the number of roots of $T_i^{\bullet\cdots\bullet}$ . If $d=1$ , then $t(T_i^2,U)=t(P_3,U)$ . If $d\ge 2$ , we obtain using Lemma 2.6 that $t(T_i^2,U)\le t(C_4,U)$ . If the vertex $v_i$ has a neighbor of degree one in $T_i^{\bullet\cdots\bullet}$ , it holds that $t_{x_1,\ldots,x_r}(T_i^{\bullet\cdots\bullet},U)^2\le t_{x_1}(P_2^\bullet,U)^2$ (assuming that $x_1$ corresponds to the root vertex $v_i$ ) and so $t(T_i^2,U)\le t(P_3,U)$ . Otherwise, $T_i^2$ satisfies the assumptions of Lemma 2.10 and we obtain that

\[t(T_i^2,U)\le t(C_4,U)^{5/4}\le t(C_4,U).\]

In all three cases, it holds that

\[t(T_i^2,U)\le\max\{t(P_3,U),t(C_4,U)\}=t(P_3,U)+t(C_4,U).\]

Hence, we obtain from (36) that

(37) \begin{equation}\lvert t(\langle F_c\rangle,U)\rvert\le\big(t(P_3,U)+t(C_4,U)\big)^2.\end{equation}

As there are at most $2^{e\left(H\right)+7}$ possible sets $F_c$ such that an associated set $F_0$ can be contained in group (e), we conclude using (32), (35) and (37) that the absolute value of the sum of the terms that involve $F_0$ from group (e) is at most

(38) \begin{equation}\frac{2}{p_0^{8}}t(P_{\ell},p+U)2^{e\left(H\right)+7}\big(t(P_3,U)+t(C_4,U)\big)^2.\end{equation}

The choice of $\varepsilon_0$ implies using (3) that

(39) \begin{equation}t(C_4,U)\le 4p_0^{64}/2^{8e(H)+90}\end{equation}

and so

(40) \begin{equation}t(P_3,U)\le t(C_4,U)^{1/2}\le 2p_0^{32}/2^{4e(H)+45},\end{equation}

which yields that (38) does not exceed $\frac{1}{8}t(P_{\ell},p+U)\big(t(P_3,U)+t(C_4,U)\big)$ .

Figure 4.

Illustration of the definition of $v_i$ , $V_i$ and $T_i^{\bullet\cdots\bullet}$ in the proof of Claim 3.4; roots are the vertices depicted in the figure.

Figure 5.

Examples of rooted trees $T_i^{\bullet\cdots\bullet}$ and the associated trees $T_i^2$ in the proof of Claim 3.4.

Claim 3.5. The absolute value of the sum of the terms on the left-hand side of (23) that involve $F_0$ from group (f) is at most

\[\tfrac{1}{8}t(P_{\ell},p+U)\big(t(P_3,U)+t(C_4,U)\big).\]

Proof of Claim 3.5. Consider a set $F_0$ from group (f) and let $F_c$ be the edges of $F_0$ contained in the core components of $\langle F_0\rangle$ . Let m be the number of edges of the 12-edge path from $C_4$ to the graph G in H that are contained in the component of $\langle F_0\rangle$ that contains $C_4$ . Note that $m\ge 1$ by the definition of group (f). If $m\le 7$ , we obtain using $\|U\|_{\infty}\le 1$ and Lemma 2.12 that

(41) \begin{equation}t(\langle F_c\rangle,U)\le\tfrac{1}{2}\big(t(C_4,U)+t(P_3,U)\big)t(C_4,U)^{1/8}.\end{equation}

If $m\ge 8$ , let $S^{\bullet\bullet}$ be the rooted graph obtained from $\langle F_c\rangle$ by removing the edges of an 8-edge subpath of the m-edge path starting at $C_4$ and choosing the end vertices of the path to be two roots of $S^{\bullet\bullet}$ . As in (35), we obtain that

(42) \begin{equation}\lvert t(\langle F_c\rangle,U)\rvert\le t(C_4,U)^2. \end{equation}

The estimates (41) and (42) imply that the following holds in either of the cases:

\[\lvert t(\langle F_c\rangle,U)\rvert\le\big(t(C_4,U)+t(P_3,U)\big)t(C_4,U)^{1/8}.\]

As there are at most $2^{e\left(H\right)+7}$ possible sets $F_c$ such that an associated $F_0$ can be contained in group (f), we conclude using (32) and the choice of $\varepsilon_0$ , which implies that (39) holds, that the absolute value of the sum of the terms that involve $F_0$ from group (f) is at most

\[\frac{2}{p_0^{8}}t(P_{\ell},p+U)2^{e\left(H\right)+7}\big(t(P_3,U)+t(C_4,U)\big)t(C_4,U)^{1/8}\le \frac{1}{8}t(P_{\ell},p+U)\big(t(P_3,U)+t(C_4,U)\big).\]

This completes the proof of the claim.

Claim 3.6. The absolute value of the sum of the terms on the left-hand side of (23) that involve $F_0$ from group (g) is at most

\[\tfrac{1}{8}t(P_{\ell},p+U)t(P_3,U).\]

Proof of Claim 3.6. Consider a set $F_0$ from group (g) and let $F_c$ be the edges of $F_0$ contained in the core components of $\langle F_0\rangle$ . We obtain using Lemma 2.11 that

\[\lvert t(\langle F_c\rangle,U)\rvert\le t(P_3,U)t(C_4,U)^{1/4}.\]

As there are at most $2^{e\left(H\right)+7}$ possible sets $F_c$ such that an associated set $F_0$ can be contained in group (g), we conclude using (32) and the choice of $\varepsilon_0$ , which implies that (39) holds, that the absolute value of the sum of the terms that involve $F_0$ from group (g) is at most

\[\frac{2}{p_0^{8}}t(P_{\ell},p+U)2^{e\left(H\right)+7}t(P_3,U)t(C_4,U)^{1/4}\le\frac{1}{8}t(P_{\ell},p+U)t(P_3,U).\]

The proof of the claim is now completed.

Claim 3.7. The absolute value of the sum of the terms on the left-hand side of (23) that involve $F_0$ from group (h) is at most

\[\tfrac{1}{8}t(P_{\ell},p+U)t(P_3,U).\]

Proof of Claim 3.7. Consider a set $F_0$ from group (h) and let $F_c$ be the edges of $F_0$ contained in the core components of $\langle F_0\rangle$ , and let $S_1$ and $S_2$ be any two core components of $\langle F\rangle$ . If $S_i$ is a single edge, then $t(S_i,U)=0$ , and if $S_i$ is $C_4$ , then $t(S_i,U)=t(C_4,U)$ . Finally, if $S_i$ is a star with at least two leaves, we obtain using Lemma 2.6 that

\[\lvert t(S_i,U)\rvert\le t(K_1,U)=t(P_3,U).\]

Hence, we obtain that

\[\lvert t(\langle F_c\rangle,U)\rvert\le \lvert t(S_1,U)t(S_2,U)\rvert\le t(P_3,U)\big(t(P_3,U)+t(C_4,U)\big).\]

As there are at most $2^{e\left(H\right)+7}$ possible sets $F_c$ such that an associated set $F_0$ can be contained in group (h), we conclude using (32) and the choice of $\varepsilon_0$ , which implies that (40) holds, that the absolute value of the sum of the terms that involve $F_0$ from group (h) is at most

\[\frac{2}{p_0^{8}}t(P_{\ell},p+U)2^{e\left(H\right)+7}t(P_3,U)\big(t(P_3,U)+t(C_4,U)\big)\le\frac{1}{8}t(P_{\ell},p+U)t(P_3,U),\]

which completes the proof of the claim.

Summing the bounds obtained in Claims 3.3–3.7 yields the following.

Claim 3.8. The absolute value of the sum of the terms on the left-hand side of (23) that involve a set $F_0$ from one of the groups (d)–(h) is at most

\[t(P_{\ell},p+U)\bigg(\frac{t(P_3,U)}{2}+\frac{3t(C_4,U)}{8}\bigg).\]

Since we have proven both Claims 3.2 and 3.8, the proof of the theorem is now complete.

4. Local regime

In this section, we prove that the graph $H^\bullet\oplus K_{m|\ell,n}$ is locally Sidorenko (assuming W has density bounded away from zero), where the bound on locality does not depend on the parameters $\ell$ , m and n, under the assumption that all three parameters are sufficiently large. Similarly to the proof of Theorem 3.1, the proof of Theorem 4.1 is split into several separate claims, which are stated and proven inside the proof of the theorem since they rely on the notation introduced at the beginning of the proof of the theorem.

Theorem 4.1. For every graph G with girth at least 50 and every real number $p_0 \in (0,1)$ , there exist a real $\gamma_0>0$ , a positive integer $n_0$ and a connected rooted graph $H^\bullet$ that contains G as an induced subgraph such that the following holds for graphon W with density $p\ge p_0$ such that $t(C_4, W) - p^4 \leq \gamma_0$ :

(43) \begin{equation}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)\ge p^{e\left(H\right)+mn+\ell}\end{equation}

for all even integers $m,n,\ell\ge n_0$ such that m is divisible by 5 and $\ell\ge n + e\left(H\right)$ .

Proof. We first apply Theorem 3.1 with G and $p_0$ to get a connected rooted graph $H^\bullet$ that contains G as an induced subgraph and a real $\varepsilon_H>0$ . We prove that the statement of the theorem holds with

\[\gamma_0=\min\bigg\{\frac{\varepsilon_H^4}{8},\frac{p_0^{160}}{2^{200}}\bigg\}\quad\mbox{and}\quad n_0=64.\]

Note that Theorem 3.1 implies that

(44) \begin{equation}t(H^\bullet\oplus P_{\ell+1}^\bullet,W)\ge p^{e\left(H\right)+\ell}\end{equation}

for every graphon W with density $p\ge p_0$ such that $t(C_4, W) - p^4\leq\gamma_0$ , and for every integer $\ell\ge 8$ ; note that $\|W-p\|_{\square}\leq\varepsilon_H$ indeed holds for any such graphon by Lemma 2.1.

Fix even integers $m,n,\ell\ge n_0$ such that m is divisible by 5 and $\ell\ge n + e\left(H\right)\ge n_0\ge 64$ . Assume that (43) fails for $H^\bullet$ , m, n, $\ell$ and $\gamma_0$ , and let q be the supremum over all $p\in [p_0,1]$ such that there exists a graphon W with density p and $t(C_4, W) - p^4 \leq \gamma_0$ such that

(45) \begin{equation}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)<p^{e\left(H\right)+mn+\ell}.\end{equation}

Fix such a graphon W with density $p>q/(1+p_0^{mn}/4)$ for the rest of the proof. Observe that the choices of q and p implies that every graphon W’ with density $p'\ge p(1+p_0^{mn}/4)$ and $t(C_4, W) - (p')^4\leq\gamma_0$ satisfies (43).

We next analyze spectral properties of the operator associated with the graphon W using results presented in § 2.3. Let $\lambda_i$ be the non-zero eigenvalues of W listed in the non-increasing order of the absolute value (with multiplicities), and let $f_i$ be the corresponding orthonormal eigenfunctions. Furthermore, let $\alpha_i\in [0,\pi/2]$ be the real such that $\langle {\mathfrak{j}},f_i\rangle=\cos\alpha_i$ , and set $\delta=1-\cos\alpha_1$ . Finally, let $\gamma=t(C_4,W)-p^4$ . Note that $\gamma\le\gamma_0$ .

We start with giving a lower bound on $\lambda_1$ in terms of p and $\delta$ . We obtain using (16) and $\gamma\le p_0^4/2^{20}$ that

(46) \begin{equation}\lambda_1\ge p(1+2\delta) - 8\delta \gamma^{1/4}\ge p(1+2\delta) - \delta p_0/4\ge p(1+7\delta/4).\end{equation}

On the other hand, it holds that $\lambda_1\le p+\gamma/(4p^3)$ by (9). Hence, we obtain using (46) and $\gamma\le p_0^5/2^{20}$ that

(47) \begin{equation}\delta \le \frac{4}{7}\cdot \frac{\lambda_1-p}{p}\le\frac{\gamma}{7p^3} \le \frac{p_0^2}{2^{20}} \le \frac{1}{2^{20}}.\end{equation}

Let $g_H:[0,1]\to [0,1]$ be defined as $g_H(x)=t_x(H^\bullet,W)$ and let $g_K:[0,1]\to [0,1]$ be defined as $g_K(x)=t_x(K_{m,n}^\bullet,W)$ . Note that it holds that $g_K(x)=t_x(K_{m,n}^\bullet,W)\le t(K_{m-1,n},W)$ for every $x\in [0,1]$ , which implies that

(48) \begin{equation}\|g_K\|_2 \leq \| g_K\|_\infty \leq t(K_{m-1,n},W).\end{equation}

Set $\sigma_i=\langle g_H, f_i\rangle$ and $\kappa_i=\langle g_K, f_i\rangle$ . Since $\|g_H\|_2\le\|g_H\|_\infty\le 1$ and $\|g_K\|_2\le\|g_K\|_\infty\le 1$ , we obtain that $\lvert\sigma_i\rvert\le 1$ and $\lvert\kappa_i\rvert\le 1$ for every i. Next observe that

(49) \begin{equation}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)=\langle g_H, W^{\ell} g_K\rangle=\sigma_1\kappa_1\lambda_1^{\ell}+\sum_{i\ge 2}\sigma_i\kappa_i\lambda_i^{\ell}.\end{equation}

In the next two claims, we give lower bounds on the product $\sigma_1\lambda_1^{\ell}$ and $\kappa_1$ .

Claim 4.2. For every $\ell'\ge 8$ , it holds that

\[\sigma_1 \lambda_1^{\ell'}\ge p^{e\left(H\right)+\ell'}-2\gamma^{\ell'/4}\delta^{1/2}.\]

Proof of claim 4.2. Consider a positive integer $\ell'\ge 8$ . The estimate (44) implies that

(50) \begin{equation}p^{e\left(H\right)+\ell'} \le t(H^\bullet\oplus P_{\ell'+1}^\bullet,W) =\sigma_1 \lambda_1^{\ell'}(1-\delta)+\sum_{i\ge 2}\sigma_i \lambda_i^{\ell'}\cos\alpha_i.\end{equation}

We combine (50) with (11) and (15) to obtain that

\begin{align*} p^{e\left(H\right)+\ell'}\le \sigma_1 \lambda_1^{\ell'}(1-\delta)+\sum_{i\ge 2}\sigma_i \lambda_i^{\ell'}\cos\alpha_i& \le \sigma_1 \lambda_1^{\ell'}+\sum_{i\ge 2}\lvert\lambda_i\rvert^{\ell'}\cdot\lvert\cos\alpha_i\rvert \\& \le \sigma_1 \lambda_1^{\ell'}+\bigg(\sum_{i\geq 2} \lambda_i^{2\ell'}\bigg)^{1/2}\bigg(\sum_{i\ge 2}\cos^2\alpha_i\bigg)^{1/2}\\& \le \sigma_1 \lambda_1^{\ell'}+2\gamma^{\ell'/4}\delta^{1/2}.\end{align*}

Hence, we can conclude that

(51) \begin{equation}\sigma_1 \lambda_1^{\ell'}\ge p^{e\left(H\right)+\ell'}-2\gamma^{\ell'/4}\delta^{1/2}\end{equation}

holds for every $\ell'\ge 8$ . The estimate given in the statement of the claim now follows.

Claim 4.3. It holds that

\[\kappa_1 \geq t(K_{m-1,n},W)((p^4+\gamma)^{n/4}-2\delta^{1/2}).\]

Proof of Claim 4.3. We first obtain using the Cauchy–Schwarz inequality that

\[t(K_{m,n}, W)=\langle g_K,{\mathfrak{j}}\rangle=\sum_{i\ge 1}\kappa_i\cos\alpha_i\le\kappa_1\cos\alpha_1+\big(1-\cos^2\alpha_1\big)^{1/2}\|g_K\|_2,\]

which implies using the definition of $\delta$ and (48) that

\[ t(K_{m,n}, W)\le\kappa_1\cos\alpha_1+2\delta^{1/2}t(K_{m-1,n},W).\]

Hence, it follows using Lemma 2.3 that

\[\kappa_1 \ge t(K_{m,n}, W)-2\delta^{1/2}t(K_{m-1,n},W)\ge t(K_{m-1,n},W)(t(K_{{m-1},n},W)^{1/(m-1)}-2\delta^{1/2}).\]

Since Lemma 2.4 implies that

\[t(K_{{m-1},n},W)^{1/(m-1)}\ge t(C_4,W)^{n/4}=(p^4+\gamma)^{n/4},\]

the statement of the claim now follows.

We next distinguish the following three cases, which are covered in Claims 4.4, 4.6 and 4.7, respectively. In each of the cases, we show that the fixed graphon W satisfies (43), which would contradict the choice of W and so complete the proof of the theorem.

1. (i) It holds that $\delta\le\frac{\gamma^2 n^2 p^{2n}}{1600p^8}$ .

2. (ii) It holds that $\delta>\frac{\gamma^2 n^2 p^{2n}}{1600p^8}$ and $\|g_K\|_2\le\frac{\kappa_1}{\gamma^{\ell/8}}$ .

3. (iii) It holds that $\delta>\frac{\gamma^2 n^2 p^{2n}}{1600p^8}$ and $\|g_K\|_2>\frac{\kappa_1}{\gamma^{\ell/8}}$ .

Intuitively speaking, case (i) corresponds to the situation when the degrees of almost all vertices of W are the same, which is equivalent to that $\delta$ is small. Case (ii) corresponds to the situation when the sum in (49) is small compared with the leading term, i.e. the term $\sigma_1\kappa_1\lambda_1^{\ell}$ controls the expression in (49). In case (iii), which covers the cases not covered in cases (i) and (ii), we show that the reason for the sum in (49) being large comparatively to the leading term is that the graphon W contains a part denser than q where we identify sufficiently many copies of $H^\bullet\oplus K_{m|\ell,n}^\bullet$ ; here, we use the choice of q as the supremum among the densities of graphons violating (43) for fixed m, n and $\ell$ .

Proof of Claim 4.4. We start with refining the bound given in Claim 4.3 using the assumption that $\delta\le\frac{\gamma^2 n^2 p^{2n}}{1600p^8}$ , which is equivalent to $\frac{40\delta^{1/2}p^4}{np^n}\le\gamma$ , and Pascal’s inequality:

(52) \begin{align}\kappa_1 & \ge t(K_{m-1,n},W)\big((p^4+\gamma)^{n/4}-2\delta^{1/2}\big) \nonumber \\& \ge t(K_{m-1,n},W)\bigg(p^n\bigg(1+\frac{n\gamma}{4p^4}\bigg)-2\delta^{1/2}\bigg) \nonumber \\& \ge t(K_{m-1,n},W)\bigg(p^n\bigg(1+\frac{10\delta^{1/2}}{p^n}\bigg)-2\delta^{1/2}\bigg) \nonumber \\& = t(K_{m-1,n},W)\big(p^n+8\delta^{1/2}\big)\ge t(K_{m-1,n},W)p^n(1+8\delta^{1/2}). \end{align}

Hence, we conclude using Claim 4.2, the bound $\gamma\le p^8/2^{20}$ , (52) and $\ell\ge e\left(H\right)$ that the first term in (49) can be bounded from below as follows:

(53) \begin{align}\sigma_1\kappa_1\lambda_1^{\ell}& \ge \big(p^{e\left(H\right)+\ell}-2\gamma^{\ell/4}\delta^{1/2}\big)t(K_{m-1,n},W)p^n(1+8\delta^{1/2})\nonumber\\& \ge \big(p^{e\left(H\right)+\ell}-p^{2\ell}\delta^{1/2}/16\big)t(K_{m-1,n},W)p^n(1+8\delta^{1/2})\nonumber\\& = t(K_{m-1,n},W)p^n\big(p^{e\left(H\right)+\ell}+8p^{e\left(H\right)+\ell}\delta^{1/2}-p^{2\ell}\delta^{1/2}/16-p^{2\ell}\delta/2\big)\nonumber\\& \ge t(K_{m-1,n},W)p^n\big(p^{e\left(H\right)+\ell}+8p^{e\left(H\right)+\ell}\delta^{1/2}-p^{2\ell}\delta^{1/2}\big)\nonumber\\& \ge t(K_{m-1,n},W)p^n\big(p^{e\left(H\right)+\ell}+8p^{2\ell}\delta^{1/2}-p^{2\ell}\delta^{1/2}\big)\ge t(K_{m-1,n},W)p^{e\left(H\right)+\ell+n}.\end{align}

On the other hand, the absolute value of the sum in (49) can be bounded from above using Cauchy–Schwarz inequality, (11) and (48) as follows:

(54) \begin{align}\bigg\lvert \sum_{i\ge 2}\sigma_i\kappa_i\lambda_i^{\ell}\bigg\rvert& \le \bigg(\sum_{i\ge 2} \kappa_i^2 \sigma_i^2 \bigg)^{1/2} \bigg(\sum_{i\ge 2} \lambda_i^{2\ell}\bigg)^{1/2} \nonumber\\& \le \bigg(\sum_{i\ge 1} \kappa_i^2 \sigma_i^2 \bigg)^{1/2} \bigg(\sum_{i\ge 1} \lambda_i^{2\ell}\bigg)^{1/2} \nonumber\\& = \|g_K\|_2 \cdot \gamma^{\ell/4}\le t(K_{m-1, n}, W) \gamma^{\ell/4}. \end{align}

Hence, we conclude using (49), (53), (54), Lemma 2.4, Pascal’s inequality, $\gamma\le p^{16}/2^{32}$ and $\ell\ge n + e\left(H\right) \ge 8$ that

\begin{align*}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)& \ge t(K_{m-1,n},W)\big(p^{e\left(H\right)+\ell+n}-\gamma^{\ell/4}\big)\\& \ge (p^4+\gamma)^{(m-1)n/4}\big(p^{e\left(H\right)+\ell+n}-\gamma^{1+\ell/8}\big)\\& \ge p^{(m-1)n}\bigg(1+\frac{\gamma}{p^4}\bigg)^{(m-1)n/4}\big(p^{e\left(H\right)+\ell+n}-\gamma^{1+\frac{\ell+n + e\left(H\right)}{16}}\big)\\& \ge p^{(m-1)n}\bigg(1+\frac{(m-1)n\gamma}{4p^4}\bigg)\bigg(p^{e\left(H\right)+\ell+n}-\frac{\gamma p^{e\left(H\right)+\ell+n}}{4}\bigg)\\& \ge p^{e\left(H\right)+\ell+mn}\bigg(1+\frac{\gamma}{2}\bigg)\bigg(1-\frac{\gamma}{4}\bigg)\ge p^{e\left(H\right)+\ell+mn},\end{align*}

which completes the proof of the claim.

Before stating and proving Claims 4.6 and 4.7, we show that if $\delta$ is large, then $\kappa_1$ is also large as stated in the next claim.

Proof of Claim 4.5. We start with a bound on the density of $K_{1,2}$ :

\[t(K_{1,2},W) = \langle {\mathfrak{j}}, W^2{\mathfrak{j}} \rangle= \sum_{i\ge 1} \lambda_i^2\cos^2 \alpha_i\geq \lambda_1^2 \cos^2 \alpha_1= \lambda_1^2 (1-\delta)^2.\]

Since $mn/10$ is an even integer, which follows from the facts that m and n are even integers and m is divisible by 5, Lemma 2.13 implies that

\[t(K_{m|mn/10,n},W)\ge\lambda_1^{11mn/10}(1-\delta)^{11mn/10}.\]

On the other hand, we obtain using (11) that

\begin{align*}t(K_{m|mn/10,n},W) = \langle {\mathfrak{j}}, W^{mn/10}g_K\rangle& = \kappa_1(1-\delta)\lambda_1^{mn/10}+\sum_{i\ge 2}\kappa_i\cos\alpha_i\lambda_i^{mn/10} \\& \le \kappa_1\lambda_1^{mn/10}+\sum_{i\ge 2}\lvert\lambda_i\rvert^{mn/10} \\& \le \kappa_1\lambda_1^{mn/10}+\gamma^{mn/40}.\end{align*}

We obtain by combining the just obtained lower and upper bounds on $t(K_{m|mn/10,n},W)$ that

(55) \begin{equation}\kappa_1 \ge \lambda_1^{mn}(1-\delta)^{11mn/10}-\gamma^{mn/40}/\lambda_1^{mn/10}.\end{equation}

We next plug the estimate (46) to (55) and we derive using $\gamma\le p^{160}$ , Pascal’s inequality, and $n_0\ge 20$ that

\begin{align*}\kappa_1& \ge p^{mn}(1+7\delta/4)^{mn}(1-\delta)^{11mn/10}-\gamma^{mn/40}/p^{mn/10}\\& \ge p^{mn}\big((1+7\delta/4)^{10}(1-\delta)^{11}\big)^{mn/10}-\gamma^{mn/160}p^{2mn}\\& \ge p^{mn}\big((1+70\delta/4)(1-11\delta)\big)^{mn/10}-\gamma^2 p^{2n+mn}\\& \ge p^{mn}\big(1+70\delta/4-11\delta-770\delta^2/4\big)^{mn/10}-\gamma^2p^{2n+mn},\end{align*}

which yields using $\delta\le 2^{-20}$ given by (47) that

\[\kappa_1 \ge p^{mn}\big(1+4\delta\big)^{mn/10}-\gamma^2p^{2n+mn}\ge p^{mn}\bigg(1+\frac{2\delta mn}{5}-\gamma^2p^{2n}\bigg).\]

We now use the assumption from the statement of the claim that $\delta>\gamma^2 n^2 p^{2n}/1600$ , and the fact that $n_0\ge 20$ to derive that

(56) \begin{equation}\kappa_1 \ge p^{mn}\bigg(1+\frac{\gamma^2 mn^3 p^{2n}}{4000}-\gamma^2p^{2n}\bigg)\ge p^{mn},\end{equation}

which completes the proof of the claim.

We are now ready to analyze cases (ii) and (iii), which are covered in the next two claims.

Proof of Claim 4.6. We first plug the assumption $\|g_K\|_2\le\frac{\kappa_1}{\gamma^{\ell/8}}$ to (49) and obtain using (11) and Cauchy–Schwarz inequality that

(57) \begin{align} t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)& = \sigma_1\kappa_1\lambda_1^{\ell}+\sum_{i\ge 2}\sigma_i\kappa_i\lambda_i^{\ell} \nonumber \\& \ge \sigma_1\kappa_1\lambda_1^{\ell}-\sum_{i\ge 2}\lvert\kappa_i\rvert\cdot\lvert\lambda_i\rvert^{\ell} \nonumber \\& \ge \sigma_1\kappa_1\lambda_1^{\ell}-\|g_K\|_2\gamma^{\ell/4} \ge \kappa_1\big(\sigma_1\lambda_1^{\ell}-\gamma^{\ell/8}\big).\end{align}

We next estimate $\sigma_1\lambda_1^{\ell}$ using Claim 4.1 with $\ell'=\ell-1$ , (46) and $\ell\ge 10$ , as follows:

(58) \begin{align}\sigma_1\lambda_1^{\ell}=\sigma_1\lambda_1^{\ell-1}\lambda_1& \ge \big(p^{e\left(H\right)+\ell-1}-2\gamma^{(\ell-1)/4}\delta^{1/2}\big)p(1+7\delta/4) \nonumber \\& \ge p^{e\left(H\right)+\ell}\bigg(1-\frac{2\gamma^{(\ell-1)/4}\delta^{1/2}}{p^{e\left(H\right)+\ell-1}}\bigg)(1+7\delta/4) \nonumber \\& \ge p^{e\left(H\right)+\ell}\big(1-2\gamma^{\ell/8}\delta^{1/2}\big)(1+7\delta/4).\end{align}

We obtain using Claim 4.5, (57), (58), $\gamma\le p^{64}$ and $\ell\ge n+e\left(H\right)$ that

(59) \begin{align} t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)& \ge p^{mn}\big(\sigma_1\lambda_1^{\ell}-\gamma^{\ell/8}\big)\nonumber\\& \ge p^{mn}\big(p^{e\left(H\right)+\ell}\big(1-2\gamma^{\ell/8}\delta^{1/2}\big)(1+7\delta/4)-\gamma^{\ell/8}\big)\nonumber\\& \ge p^{e\left(H\right)+\ell+mn}\big(\big(1-\gamma^{\ell/16}\delta^{1/2}/2^{10}\big)(1+7\delta/4)-\gamma^{\ell/16}\big).\end{align}

We next estimate $\gamma^{\ell/16}$ using that the assumption that $\frac{\gamma^2 n^2 p^{2n}}{1600p^8}<\delta$ , $n\ge 64$ and $\ell\ge n$ (and $\ell\ge 64$ ) as follows:

\[\gamma^{\ell/16}\le \gamma^2 \gamma^{\ell/32}\le \frac{1600\delta}{n^2 p^{2n}} p^{160\ell/32}\le \frac{\delta}{p^{2n}} p^{160n/32}\le \delta.\]

Hence, we obtain from (59) that

\begin{align*} t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)& \ge p^{e\left(H\right)+\ell+mn}\big(\big(1-\delta^{3/2}/2^{10}\big)(1+7\delta/4)-\delta\big) \\& \ge p^{e\left(H\right)+\ell+mn}\big(1+7\delta/4-\delta^{3/2}/2^{10}-7\delta^{5/2}/2^{12}-\delta\big) \ge p^{e\left(H\right)+\ell+mn},\end{align*}

which yields the statement of the claim.

Proof of Claim 4.7. Our aim is to show that W contains a significantly denser part and use this part to obtain a contradiction with the choice of q at the beginning of the proof. Observe that we can assume the eigenfunction $f_1$ is non-negative since the graphon W is non-negative (if needed, change $f_1$ on a set of measure zero). We define subsets S and S’ of [0,1] (also see Figure 6) as follows:

\begin{align*}S & = \{x\in [0,1]\mbox{ such that }f_1(x)\le\gamma^{\ell/100}\},\\S' & = \{x\in [0,1]\mbox{ such that }f_1(x)\le 1-\delta^{1/4}\}.\end{align*}

Note that $\gamma^{\ell/100}\le\gamma_0^{n_0/100}\le 2^{-128}$ by the choice of $n_0$ and $\gamma_0$ and $\delta^{1/4}\le 1/32$ by (47), and so it holds that $S\subseteq S'$ .

Figure 6.

Illustration of the definition of the sets S, S’ and T from the proof of Claim 4.7.

We start with bounding the measures of the sets S and S’ from above. Since $\|f_1\|_1=\langle f_1,{\mathfrak{j}}\rangle=1-\delta$ and $0\le f_1(x)\le 1$ for all $x\in [0,1]$ , we obtain that $\mu(S)\gamma^{\ell/100}+1-\mu(S)\ge 1-\delta$ , which implies using (47) that

(60) \begin{equation}\mu(S) \leq \frac{\delta}{1-\gamma^{\ell/100}}\le \frac{p_0}{2^{20}(1-\gamma^{\ell/100})}\le \frac{p}{2^{16}}.\end{equation}

Similarly, it holds that $\mu(S')(1-\delta^{1/4})+1-\mu(S')\ge 1-\delta$ , which implies that

(61) \begin{equation}\mu(S') \leq \delta^{3/4}.\end{equation}

Our next step is proving the following lower bound on the measure of the set S:

(62) \begin{equation}\mu(S) \geq \big(1-{\gamma^{\ell/20}}\big)p^{mn} \geq \frac{p^{mn}}{2}.\end{equation}

Suppose that (62) does not hold, i.e. $\mu(S)<\big(1-{\gamma^{\ell/20}}\big)p^{mn}$ . We first bound $\kappa_1$ as follows (we use the Sidorenko property of $K_{m,n}$ , i.e. $t(K_{m,n},W)\ge p^{mn}$ , in the penultimate inequality):

(63) \begin{align}\kappa_1& = \int_{[0,1]}f_1(x)g_K(x)\,\textit{d} x \nonumber \\& \ge \int_{[0,1]}\gamma^{\ell/100}g_K(x)\,\textit{d} x+\int_{S}\big(f_1(x)-\gamma^{\ell/100}\big)g_K(x)\,\textit{d} x \nonumber \\& \ge \gamma^{\ell/100}\int_{[0,1]}g_K(x)\,\textit{d} x-\gamma^{\ell/100}\mu(S) \nonumber \\& > \gamma^{\ell/100}\big(t(K_{m,n},W)-\big(1-\gamma^{\ell/20}\big)p^{mn}\big) \nonumber \\& \ge \gamma^{\ell/100} t(K_{m,n},W) \big(1-1+\gamma^{\ell/20}\big) \ge \gamma^{\ell/16} t(K_{m,n},W).\end{align}

On the other hand, we obtain using the assumption $\|g_K\|_2>\frac{\kappa_1}{\gamma^{\ell/8}}$ that

\begin{align*}\kappa_1& < \gamma^{\ell/8}\|g_K\|_2 = \gamma^{\ell/8}\bigg(\int_{[0,1]}g_K(x)^2\,\textit{d} x\bigg)^{1/2} \\& \le \gamma^{\ell/8}\|g_K\|_1^{1/2}\|g_K\|_\infty^{1/2} \\& \le \gamma^{\ell/8}t(K_{m,n},W)^{1/2}t(K_{m-1,n},W)^{1/2},\end{align*}

which implies using Lemma 2.3, the Sidorenko property of $K_{m,n}$ , $\gamma\le p^{16}$ and $\ell\ge n+e\left(H\right)$ that

(64) \begin{align}\kappa_1& < \gamma^{\ell/8}t(K_{m,n},W)^{1/2}t(K_{m,n},W)^{(m-1)/2m} \nonumber \\& \le \gamma^{\ell/16} p^n t(K_{m,n},W)^{(2m-1)/2m} \le \gamma^{\ell/16}t(K_{m,n},W).\end{align}

However, the estimates (63) and (64) contradict each other. Hence, we conclude that (62) holds.

We next analyze the graphon W[T] where $T=[0,1]\setminus S$ and start with estimating the density of W[T]; we refer to Figure 6 for the illustration of the relation of the sets S, S’ and T. As the first step to estimate the density of W[T], we bound the density of W between the sets S and $[0,1]\setminus S'$ (we refer to Figure 6 and recall that $\lambda_1\in [p_0,1]$ ):

\begin{align*}\mu(S)\gamma^{\ell/100} & \ge \int_S f_1(x)\,\textit{d} x= \int_S \frac{1}{\lambda_1}\bigg(\int_{[0,1]}W(x,y)f_1(y)\,\textit{d} y\bigg)\,\textit{d} x\ge \int_{S\times [0,1]}W(x,y)f_1(y)\,\textit{d} x\,\textit{d} y\\& \ge \int_{S\times([0,1]\setminus S')}W(x,y)f_1(y)\,\textit{d} x\,\textit{d} y\ge (1-\delta^{1/4})\int_{S\times([0,1]\setminus S')}W(x,y)\,\textit{d} x\,\textit{d} y,\end{align*}

which yields that

(65) \begin{equation}\int_{S\times([0,1]\setminus S')}W(x,y)\,\textit{d} x\,\textit{d} y\le\frac{\gamma^{\ell/100}\mu(S)}{1-\delta^{1/4}}\le 2\gamma^{\ell/100}\mu(S).\end{equation}

Hence, we can estimate the density of W on $T^2$ using (65) as follows (we again refer to Figure 6):

\begin{align*}\int_{T^2}W(x,y)\,\textit{d} x\,\textit{d} y& = \int_{[0,1]^2}W(x,y)\,\textit{d} x\,\textit{d} y-\int_{S^2}W(x,y)\,\textit{d} x\,\textit{d} y-2\int_{S\times ([0,1]\setminus S)}W(x,y)\,\textit{d} x\,\textit{d} y \\& \ge p - \mu(S)^2 - 2\mu(S)\cdot\mu(S'\setminus S) - \int_{S\times([0,1]\setminus S')}W(x,y)\,\textit{d} x\,\textit{d} y\\& \ge p - \mu(S)^2 - 2\mu(S)\cdot\mu(S'\setminus S) - 4\gamma^{\ell/100}\lambda_1\mu(S) \\& \ge p - \mu(S)^2 - 2\mu(S)\cdot\mu(S') - 4\gamma^{\ell/100}\lambda_1\mu(S),\end{align*}

which combines with estimates (60), (61), $\delta\le p^2/2^{20}$ by (47), and $\gamma^{\ell/100}\le\gamma_0^{n_0/100}\le p^{100}/2^{128}$ by the choice of $n_0$ and $\gamma_0$ to

\begin{align*}\int_{T^2}W(x,y)\,\textit{d} x\,\textit{d} y& \ge p - \frac{p\mu(S)}{2^{16}} - 2\mu(S)\delta^{3/4} - 4\gamma^{\ell/100}\mu(S) \\& \ge p - \frac{p\mu(S)}{2^{16}} - \frac{p\mu(S)}{2^{14}} - \frac{p\mu(S)}{2^{126}}\ge p\bigg(1-\frac{\mu(S)}{2^{10}}\bigg).\end{align*}

Hence, the density $p_T$ of the graphon W[T] is at least

(66) \begin{equation}p_T \ge \frac{\int_{T^2}W(x,y)\,\textit{d} x\,\textit{d} y}{(1-\mu(S))^2}\ge p \bigg(1-\frac{\mu(S)}{2^{10}}\bigg)(1+2\mu(S)) \ge p\bigg(1+\frac{511\mu(S)}{256}\bigg),\end{equation}

which combines with (62) to

(67) \begin{equation}p_T \ge p\bigg(1+\frac{511\mu(S)}{512}\bigg) > p\big(1+p^{mn}/4\big).\end{equation}

Note that if q were equal to 1, then (67) would imply that $p_T>1$ (recall that $q\le p(1+p_0^{mn}/4)$ ), which is impossible, and so it holds that $q<1$ . Finally, we estimate $\gamma_T=t(C_4,W[T])-p_T^4$ as follows:

(68) \begin{align}\gamma_T = t(C_4,W[T])-p_T^4& \le \frac{t(C_4,W)}{(1-\mu(S))^4}-p^4\bigg(1+\frac{511\mu(S)}{256}\bigg)^4\nonumber \\& \le (p^4+\gamma)(1+5\mu(S))-p^4\bigg(1+\frac{511\mu(S)}{256}\bigg)^4\nonumber \\& \le \gamma+5\gamma\mu(S)+5p^4\mu(S)-\frac{511p^4\mu(S)}{64}\nonumber \\& \le \gamma+\frac{5p^4\mu(S)}{2^{200}}+5p^4\mu(S)-\frac{511p^4\mu(S)}{64}\le\gamma.\end{align}

Since the density $p_T$ of W[T] is larger than q by (67) (again recall that $q\le p(1+p_0^{mn}/4)$ ) and $\gamma_T\le\gamma_0$ by (68), the choice of q implies that

\[t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W[T]) \ge p_T^{e\left(H\right)+\ell+mn}.\]

Hence, we obtain using (4), (60) and (66) that

\begin{align*}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)& \ge (1-\mu(S))^{v(H)+\ell+m+n-2}p_T^{e\left(H\right)+\ell+mn} \\& \ge p^{e\left(H\right)+\ell+mn}(1-\mu(S))^{v(H)+\ell+m+n-2}\bigg(1+\frac{511\mu(S)}{256}\bigg)^{e\left(H\right)+\ell+mn} \\& \ge p^{e\left(H\right)+\ell+mn}\bigg(\big(1-\mu(S)\big)\bigg(1+\frac{511\mu(S)}{256}\bigg)\bigg)^{v(H)+\ell+m+n-2} \\& = p^{e\left(H\right)+\ell+mn}\bigg(1-\mu(S)+\frac{511\mu(S)}{256}-\frac{511\mu(S)^2}{256}\bigg)^{v(H)+\ell+m+n-2} \\& \ge p^{e\left(H\right)+\ell+mn}\bigg(1-\mu(S)+\frac{511\mu(S)}{256}-\frac{511\mu(S)}{2^{24}}\bigg)^{v(H)+\ell+m+n-2} \\&\ge p^{e\left(H\right)+\ell+mn},\end{align*}

which implies that W satisfies (45) under the assumptions made in the statement of the claim.

Claims 4.4, 4.6 and 4.7 imply that W satisfies (45), which contradicts the choice of W as violating (45), and so completes the proof of the theorem.

Theorem 4.1 together with the counting lemma (Lemma 2.2) applied for $C_4$ yields the following.

Corollary 4.8. For every graph G with girth at least 50 and every real number $p_0 \in (0,1)$ , there exist a real $\varepsilon_0>0$ , a positive integer $n_0$ and a connected rooted graph $H^\bullet$ that contains G as an induced subgraph such that the following holds for every graphon W with density $p \geq p_0$ such that $\|W-p\|_{\square} \leq \varepsilon_0$ :

\[t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)\ge p^{e\left(H\right)+mn+\ell}\]

for all even integers $m,n,\ell\ge n_0$ such that m is divisible by 5 and $\ell\ge n + e\left(H\right)$ .

5. Non-local regime

In this section, we present the result covering the non-local regime, i.e. the regime when one of the k color classes is far from being quasirandom with density $1/k$ . We start with the lemma that informally says that if the density of a graph H in a given graphon is small, then the graphon contains a large sparse part. Since it is folklore that complete graphs satisfy the Kohayakawa–Nagle–Rödl–Schacht conjecture (Conjecture 7.1 in § 7), a simple proof of this fact can be found in [Reference LeeLee21, Theorem 4.2], the next lemma holds for H being a complete graph and so it holds for all graphs H. We include a self-contained proof in Appendix A for completeness.

• – $t(H, W) \geq \omega_0$ ; or

• – $\alpha_{\delta}(W)\ge\alpha_0$ .

The next theorem is the main result of this section. The theorem asserts that if a graphon W is far from the quasirandom graphon and does not contain a sparse part, then the density of $H^\bullet\oplus K_{m|\ell,n}^\bullet$ in W is at least the density of $H^\bullet\oplus K_{m|\ell,n}^\bullet$ in the quasirandom graphon with the same density.

• • $\alpha_{\delta}(W)\ge\alpha_0$ ; or

• • it holds for all integers $m,n\ge n_0$ and $\ell\le mn/4$ that

  \[t\big(H^\bullet\oplus K_{m|\ell,n}^\bullet,W\big)\ge p^{e\left(H\right)+mn+\ell}.\]

Proof. Fix the reals $p_0$ , $\delta$ and $\varepsilon_0$ and the rooted graph $H^{\bullet}$ . Let $\omega_0$ and $\alpha'_0$ be the reals obtained by applying Lemma 5.1 with $\delta$ and H, and let $d_0=\omega_0(p_0\varepsilon_0/10)^{16v(H)}$ . Choose $n_0\ge 2$ such that

\[d_0\big(1+10^{-11}\varepsilon_0^{16}\big)^{n_0^2/4}\ge 1.\]

We show that the statement of the theorem holds for this choice of $n_0$ and for $\alpha_0=\alpha'_0 p_0 (\varepsilon_0/10)^{16}$ .

Fix a graphon W and let A be the set of $x\in [0,1]$ such that $t_x(H^{\bullet},W)\le d_0$ . First suppose that $\mu(A)>p_0(\varepsilon_0/10)^{16}$ and note that $t(H,W[A])\le d_0/\mu(A)^{v(H)}<\omega_0$ . Hence, the graphon W[A] does not satisfy the first conclusion of Lemma 5.1 and so it satisfies the second conclusion, i.e. $\alpha_{\delta}(W[A])\ge\alpha'_0$ . It follows that $\alpha_{\delta}(W)\ge\alpha'_0\mu(A)\ge\alpha_0$ . Therefore, we can assume in the rest of the proof of the theorem that $\mu(A)\le p_0(\varepsilon_0/10)^{16}$ .

Let Wʹ be the graphon obtained from the graphon W by setting

\[W'(x,y)=\begin{cases}0 & \mbox{if $x\in A$ or $y\in A $, and}\\W(x,y) & \mbox{otherwise.}\end{cases}\]

Note that the density p’ of W’ is at least $p-3\mu(A)\ge p(1-3(\varepsilon_0/10)^{16})$ and

\[\|W-p'\|_{\square}\ge\|W-p\|_{\square}-\lvert p-p'\rvert\ge\|W-p\|_{\square}-3(\varepsilon_0/10)^{16}.\]

As $\|W-p\|_{\square}\ge\varepsilon_0$ , we obtain using Lemma 2.14 (note that we need that $\ell\le mn/4$ to apply the lemma) that

(69) \begin{align} t(K_{m|\ell,n},W')& \ge p^{mn+\ell}\big(1-3(\varepsilon_0/10)^{16}\big)^{mn+\ell}\big(1+10^{-9}\big(1-3\varepsilon_0^{15}/10^{16}\big)^{16}\varepsilon_0^{16}\big)^{mn/4+\ell/4} \nonumber\\& \ge p^{mn+\ell}\big(1-12(\varepsilon_0/10)^{16}\big)^{mn/4+\ell/4}\big(1+10^{-10}\varepsilon_0^{16}\big)^{mn/4+\ell/4} \nonumber\\& \ge p^{mn+\ell}\big(\big(1-10^{-14}\varepsilon_0^{16}\big)\big(1+10^{-10}\varepsilon_0^{16}\big)\big)^{mn/4+\ell/4} \nonumber\\& \ge p^{mn+\ell}\big(1+10^{-11}\varepsilon_0^{16}\big)^{mn/4+\ell/4}. \end{align}

We next estimate the density of $H^\bullet\oplus K_{m|\ell,n}^\bullet$ in the graphon W as follows:

\begin{align*}t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W) & = \int_{[0,1]} t_x(H^\bullet, W) t_x(K_{m|\ell,n}^\bullet, W)\,\textit{d} x \\& \ge d_0 \int_{[0,1]\setminus A} t_x(K_{m|\ell,n}^\bullet,W) \,\textit{d} x\ge d_0 \int_{[0,1]\setminus A} t_x(K_{m|\ell,n}^\bullet,W') \,\textit{d} x\\&= d_0 t(K_{m|\ell,n},W').\end{align*}

Hence, we obtain using (69) and the choice of $n_0$ that

\[ t(H^\bullet\oplus K_{m|\ell,n}^\bullet,W)\ge d_0 p^{mn+\ell}\big(1+10^{-11}\varepsilon_0^{16}\big)^{mn/4}\ge p^{mn+\ell}\ge p^{e\left(H\right)+mn+\ell}.\]

The statement of the theorem now follows.

6. Main result

We are now ready to prove our main results: Theorem 1.1. and the more general Theorem 1.2. Since there are graphs with arbitrarily large chromatic number and girth at least 50 by a classical result of Erdős [Reference ErdősErd59] (see also [Reference Alon and SpencerAS16]), the former is an immediate corollary of the next theorem, which is a special case of Theorem 6.2 proven later in this section. However, we include a short proof of the next theorem to highlight the main steps of the argument in the case of two colors.

Theorem 6.1. For every graph G with girth at least 50, there exist a positive integer $N_0$ and a connected rooted graph $H^\bullet$ that contains G as an induced subgraph such that the following holds for any graphon W:

\[ t\big(H^\bullet \oplus K_{m|n+e\left(H\right), n}^\bullet,W\big)+t\big(H^\bullet \oplus K_{m|n+e\left(H\right), n}^\bullet,1-W\big) \geq2^{1-e\left(H^\bullet \oplus K_{m|n+e\left(H\right), n}^\bullet\right)} = 2^{1-2e\left(H\right)-(m+1)n}\]

for all even integers $m,n\ge N_0$ such that m is divisible by 5.

Proof. Fix a graph G and an integer k as in the statement. We apply Corollary 4.8 with $p_0=1/4$ to obtain a positive real $\varepsilon_0$ , a positive integer $n_0$ and a connected rooted graph $H^\bullet$ containing G as an induced subgraph such that every graphon W with density $p \geq 1/4$ and with $\|W-p\|_{\square} \leq \varepsilon_0$ satisfies that

\[t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,W\big)\ge p^{2e\left(H\right)+(m+1)n}\]

for all even integers $m,n\ge n_0$ such that m is divisible by 5. We next apply Theorem 5.2 with $p_0=1/4$ , $\delta=\min\{\varepsilon_0/2,1/16\}$ , $\varepsilon_0$ and $H^\bullet$ to obtain a positive real $\alpha_0$ and an integer $n_0$ with the properties given in Theorem 5.2. We now set $N_0$ in a way that $N_0$ is at least $\max\{8,n_0,e\left(H\right)\}$ and the following holds for all $m,n\ge N_0$ :

(70) \begin{equation}\alpha_0^{v(H)+e\left(H\right)+m+2n-1} \ge 1.5^{1-2e\left(H\right)-(m+1)n}.\end{equation}

We now show that the statement of theorem holds for any graphon W and all even integers $m,n\ge N_0$ such that m is divisible by 5. To do so, fix a graphon W. By symmetry, we can assume that the density p of W is at least $1/2$ (otherwise, we consider the graphon $1-W$ instead of W).

Suppose that $\alpha_\delta(1-W)\ge\alpha_0$ , and let $h:[0,1]\to [0,1]$ be such that $\lvert h\rvert_1\ge\alpha_0$ and the density of $(1-W)[h]=1-W[h]$ is at most $\delta$ . Let q be the density of W[h]; note that $q\ge 1-\delta$ . The triangle inequality implies that $\|W[h]-q\|_{\square}\le\|1-W[h]\|_{\square}+(1-q)\le 2\delta\le\varepsilon_0$ . Hence, Corollary 4.8, (4) and (70) yield that

\begin{align*} t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,W\big)& \ge \alpha_0^{v(H)+e\left(H\right)+m+2n-1}t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,W[h]\big)\\& \ge \alpha_0^{v(H)+e\left(H\right)+m+2n-1}q^{2e\left(H\right)+(m+1)n} \\& \ge 1.5^{1-2e\left(H\right)-(m+1)n}(1-\delta)^{2e\left(H\right)+(m+1)n}\ge 2^{1-2e\left(H\right)-(m+1)n}.\end{align*}

We conclude that if $\alpha_\delta(1-W)\ge\alpha_0$ or (symmetrically) $\alpha_\delta(W)\ge\alpha_0$ , then the statement of the theorem holds. In the rest of the proof, we assume that both $\alpha_\delta(W)$ and $\alpha_\delta(1-W)$ are at most $\alpha_0$ .

We now derive from Corollary 4.8 if $\|W-p\|_{\square}\le\varepsilon_0$ or from Theorem 5.2 if $\|W-p\|_{\square}>\varepsilon_0$ that

(71) \begin{equation}t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,W\big)\ge p^{2e\left(H\right)+(m+1)n}.\end{equation}

In particular, if $p\ge 3/4$ , it follows that

\[ t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,W\big)\ge 1.5^{2e\left(H\right)+(m+1)n}\cdot 2^{-2e\left(H\right)-(m+1)n}\ge 2^{1-2e\left(H\right)-(m+1)n},\]

and so the statement of the theorem holds. On the other hand, if $p<3/4$ , then the density of $1-W$ is at least $p_0=1/4$ , and we can derive from Corollary 4.8 or from Theorem 5.2, depending whether the cut distance between $1-W$ and $1-p$ is at most $\varepsilon_0$ or larger, that

(72) \begin{equation}t\big(H^\bullet\oplus K_{m|n+e\left(H\right),n}^\bullet,1-W\big)\ge (1-p)^{2e\left(H\right)+(m+1)n}.\end{equation}

We combine (71) and (72) to obtain that

\[t\big(H^\bullet \oplus K_{m|n+e\left(H\right), n}^\bullet,W\big)+t\big(H^\bullet \oplus K_{m|n+e\left(H\right), n}^\bullet,1-W\big)\ge p^{2e\left(H\right)+(m+1)n}+(1-p)^{2e\left(H\right)+(m+1)n},\]

which is at least $2^{1-2e\left(H\right)-(m+1)n}$ by convexity of the function $x^{2e\left(H\right)+(m+1)n}$ . This completes the proof of the theorem.

We are now ready to prove the more general result, which implies Theorem 1.2. To display the dependance on the length of the path between $H^\bullet$ and $K_{m,n}^\bullet$ , we decided to use $\ell$ throughout the proof to denote the length of this path.

Theorem 6.2. For every graph G with girth at least 50 and every integer $k\ge 2$ , there exist a positive integer $N_k$ and a connected rooted graph $H^\bullet$ that contains G as an induced subgraph such that the following holds for any k graphons $W_1, \ldots, W_k$ such that $W_1+\cdots+W_k=1$ :

\[\sum_{i=1}^k t\big(H^\bullet \oplus K_{m|\ell, n}^\bullet, W_i\big) \geq k^{1-e\left(H\right)-mn-\ell}\]

for all even integers $m,n\ge N_k$ and $\ell=n+e\left(H\right)$ such that m is divisible by 5.

Proof. Fix the graph G and the integer k. Apply Corollary 4.8 with $p_0=1/2k$ to obtain a positive real $\varepsilon_0$ , a positive integer $n_0$ and a connected rooted graph $H^\bullet$ containing G as an induced subgraph such that every graphon W with density $p \geq 1/2k$ and with $\|W-p\|_{\square} \leq \varepsilon_0$ satisfies that

(73) \begin{equation}t\big(H^\bullet\oplus K_{m|\ell,n}^\bullet,W\big)\ge p^{e\left(H\right)+mn+\ell}\end{equation}

for all even integers $m,n,\ell\ge n_0$ such that m is divisible by 5 and $\ell\ge n + e\left(H\right)$ . Without loss of generality, we may assume that $\varepsilon_0\le 1/(4k)$ .

We next repeatedly apply Theorem 5.2. Set $\delta_1=\varepsilon_0/2\le 1/8$ . For $k'=2,\ldots,k$ , apply Theorem 5.2 with $p_0=1/2k$ , $\delta=\delta_{k'-1}/2$ , $\varepsilon_0$ and $H^\bullet$ to obtain a positive real $\alpha_{k'}$ and an integer $n_{k'}$ , and set $\delta_{k'}=\min\{\delta_{k'-1}\alpha_{k'}^2/2,1/4k'\}$ . Finally, set $N_k$ in a way that $N_k$ is at least $n_0$ and the following holds for all $m,n\ge N_k$ :

(74) \begin{align}n + e\left(H\right) & \le mn/4,\end{align}

(75) \begin{align} \\\big(1+1/4k\big)^{2e\left(H\right)+(m+1)n} & \ge k, \end{align}

and

(76) \begin{equation}\alpha_{k'}^{v(H)+e\left(H\right)+m+2n-1}\bigg(\frac{1-\delta_{k'-1}}{k'-1}\bigg)^{2e\left(H\right)+(m+1)n}\ge\bigg(\frac{1}{k'}\bigg)^{2e\left(H\right)+(m+1)n-1}\end{equation}

for $k'=2,\ldots,k$ . Note that such $N_k$ exists since it holds $\frac{1-\delta_{k'-1}}{k'-1}\ge\\frac{4k'-1}{4(k'-1)k'}>\frac{1}{k'}$ for $k'=2,\ldots,k$ .

We now prove the following claim, which implies that the statement of the theorem.

Claim 6.3. Let $k'\in [k]$ . Any k’ graphons $W_1, \dots, W_{k'}$ such that $\|W_1 + \cdots +W_{k'}\|_\infty\le 1$ and $t\big(K_2, W_1 + \cdots +W_{k'}\big) \geq 1-\delta_{k'}$ satisfy that

(77) \begin{equation}\sum_{i=1}^{k'} t\big(H^\bullet \oplus K_{m|\ell, n}^\bullet, W_i\big) \geq k'\cdot\bigg(\frac{t\big(K_2, W_1 + \dots +W_{k'}\big)}{k'}\bigg)^{e\left(H\right)+mn+\ell}\end{equation}

for all even integers $m,n\ge N_k$ and $\ell=n+e\left(H\right)$ such that m is divisible by 5.

We now present the induction step. Consider $k'\in\{2,\ldots,k\}$ and assume that the claim holds for $k'-1$ . Consider graphons $W_1,\ldots,W_{k'}$ and let $p_1,\ldots,p_{k'}$ be their respective densities; note that $p_1+\cdots+p_{k'}\geq 1-\delta_{k'}$ . First suppose that there exists i such that $\alpha_{\delta_{k'-1}/2}(W_i)\ge\alpha_{k'}$ . By symmetry, we may assume that $i=k'$ . Hence, there exists $h:[0,1]\to [0,1]$ with $\|h\|_1\ge\alpha_{k'}$ such that the density of $W_{k'}[h]$ is at most $\delta_{k'-1}/2$ . It follows that the density of $(W_1+\cdots+W_{k'-1})[h]$ is at least

\[1-\frac{\delta_{k'}}{\|h\|_1^2}-\frac{\delta_{k'-1}}{2}\ge1-\frac{\delta_{k'}}{\alpha_{k'}^2}-\frac{\delta_{k'-1}}{2}\ge1-\frac{\delta_{k'-1}}{2}-\frac{\delta_{k'-1}}{2}=1-\delta_{k'-1}.\]

By the induction hypothesis, it holds that

\[\sum_{i=1}^{k'-1} t(H^\bullet \oplus K_{m|\ell, n}^\bullet, W_i[h]) \geq\frac{(1-\delta_{k'-1})^{e\left(H\right)+mn+\ell}}{(k'-1)^{e\left(H\right)+mn+\ell-1}}.\]

It follows using (76) and $\|h\|_1\ge\alpha_{k'}$ that

\[\sum_{i=1}^{k'-1} t(H^\bullet \oplus K_{m|\ell, n}^\bullet, W_i) \geq\|h\|_1^{v(H)+m+n+\ell-1}\frac{(1-\delta_{k'-1})^{e\left(H\right)+mn+\ell}}{(k'-1)^{e\left(H\right)+mn+\ell-1}} \geq\bigg(\frac{1}{k'}\bigg)^{e\left(H\right)+mn+\ell-1},\]

which implies that (77) holds. In the rest of the proof, we assume that $\alpha_{\delta_{k'-1}/2}(W_i)<\alpha_{k'}$ for every $i\in[k']$ .

Next suppose that there exists $i\in[k']$ such that the density $p_i$ of $W_i$ is less than $1/2k$ ; by symmetry, we may assume that $i=k'$ . It follows that the density of one of the graphons $W_1,\ldots,W_{k'-1}$ , say the graphon $W_1$ , is at least

\[\frac{1-1/2k-\delta_{k'}}{k'-1}\ge\frac{1-1/2k'-1/4k'}{k'-1}=\frac{4k'-3}{4(k'-1)k'}\ge\frac{1+1/4k}{k'}.\]

We obtain using Corollary 4.8 (if $\|W_1-p_1\|_{\square}\le\varepsilon_0$ ) or Theorem 5.2 (if $\|W_1-p_1\|_{\square}>\varepsilon_0$ ) that

\[t(H^\bullet \oplus K_{m|\ell, n}^\bullet,W_1)\geq\bigg(\frac{1+1/4k}{k'}\bigg)^{e\left(H\right)+mn+\ell}\geq k\bigg(\frac{1}{k'}\bigg)^{e\left(H\right)+mn+\ell}\geq k'\bigg(\frac{1}{k'}\bigg)^{e\left(H\right)+mn+\ell},\]

which implies that (77) (the middle inequality above follows from (75)).

It remains to consider the case that $p_i\ge 1/2k$ and $\alpha_{\delta_{k'-1}/2}(W_i)\le\alpha_{k'}$ for every $i\in [k']$ . In this case, we apply to each $W_i$ , $i\in [k']$ , either Corollary 4.1 (if $\|W_i-p_i\|_{\square}\le\varepsilon_0$ ) or Theorem 5.1 (if $\|W_i-p_i\|_{\square}>\varepsilon_0$ ) to get that

\[t(H^\bullet \oplus K_{m|\ell, n}^\bullet,W_i)\geq p_i^{e\left(H\right)+mn+\ell}.\]

Hence, we conclude that

\[\sum_{i=1}^{k'}t(H^\bullet \oplus K_{m|\ell, n}^\bullet,W_i)\geq\sum_{i=1}^{k'}p_i^{e\left(H\right)+mn+\ell}\geq k'\bigg(\frac{p_1+\cdots+p_{k'}}{k'}\bigg)^{e\left(H\right)+mn+\ell},\]

where the last inequality follows from Jensen’s inequality. It follows that (77) holds, which completes the proof of the claim.

Since the statement of Claim 6.3 for $k'=k$ is actually stronger than the statement of the theorem, the proof of theorem is now completed.