Proof. We actually prove a stronger statement: if $\mathbb {P}\left (\mathbf {H}^{*}=H^*\right )>0$ then $H^*$ is strictly balanced.

Consider a possible value of $\left (H_{r},H_{h},H_{b}\right )$ of $\left (\mathbf {H}_{r},\mathbf {H}_{h},\mathbf {H}_{b}\right )$ and let $H^*=H_{r}+H_{h}+H_{b}$ . We shall prove that $H^*$ is strictly balanced. That is, we show that every proper sub-multigraph $H_{0}\subset H^*$ satisfies

$$\begin{align*}\frac{e(H_{0})}{v(H_{0})}<\frac{m}{n}=\frac{q}{2}+\frac{r}{n}. \end{align*}$$

We now follow a sequence of reductions.

First, we claim that it suffices to prove strict balancedness of $H'=H_{h}+H_{b}$ . Indeed, suppose that $H'$ is strictly balanced. Consider a set $V_{0}\subset [n]$ and denote $v_{0}=\left |V_{0}\right |$ , $H_{0}=H[V_{0}]$ , and $H_{0}'=H'[V_{0}]$ . Since $H'$ is strictly balanced,

$$\begin{align*}\frac{e\left(H_{0}'\right)}{v_{0}}<\frac{e(H')}{n}=\frac{m-(q-2)n/2}{n}=1+\frac{r}{n}. \end{align*}$$

Now, $H_{0}$ is obtained from $H_{0}'$ by adding some edges of the $(q-2)$ -regular graph $H_{r}$ , which increases the degree of each vertex by at most $q-2$ . Therefore at most $\left (\frac {q}{2}-1\right )v_{0}$ edges are added. Overall,

$$\begin{align*}\frac{e(H_{0})}{v_{0}}\leq\frac{\left(\frac{q}{2}-1\right)v_{0}+e\left(H_{0}'\right)}{v_{0}}<\frac{q}{2}+\frac{r}{n} \end{align*}$$

which proves strict balancedness of $H^*$ .

Second, we claim that it suffices to prove strict balancedness of $H"$ , which is obtained from $H'$ by replacing its balancing edges with loops: each edge $\{x,y[x]\}$ is replaced with a loop at x. Indeed, suppose that $H"$ is strictly balanced. Consider a set $V_{0}\subset [n]$ and denote $v_{0}=\left |V_{0}\right |$ , $H_{0}'=H'[V_{0}]$ , and $H_{0}"=H"[V_{0}]$ . It is easy to see that $e\left (H_{0}'\right )\leq e\left (H_{0}"\right )$ . From strict balancedness of $H"$ and that $e(H')=e(H")$ ,

$$\begin{align*}\frac{e\left(H_{0}'\right)}{v_{0}}\leq\frac{e\left(H_{0}"\right)}{v_{0}}<1+\frac{r}{n}, \end{align*}$$

which proves strict balancedness of $H'$ .

Third, we claim that to prove strict balancedness of $H"$ , it suffices to check only $V_{0}$ which are segments of the Hamiltonian component $H_{h}$ ; that is, sequences of consecutive vertices on the cycle. Indeed, assume that we have verified strict balancedness for segments. Consider a set $V_{0}\subset [n]$ and denote $v_{0}=\left |V_{0}\right |$ and $e_{0}=e\left (H_{0}"\right )$ . Notice that $V_{0}$ can be written as the union of mutually disjoint segments $\tau _{1}\sqcup \tau _{2}\sqcup \dots \sqcup \tau _{t}$ with no Hamiltonian edge between them. Let $v_{i},e_{i}$ denote the number of vertices and edges in $H"[\tau _{i}]$ . From the assumption, $e_{i}<\left (1+\frac {r}{n}\right )v_{i}$ for every i. Then

$$\begin{align*}e_{0}=\sum_{i=1}^{t}e_{i}<\left(1+\frac{r}{n}\right)\sum_{i=1}^{t}v_{i}=\left(1+\frac{r}{n}\right)v_{0}, \end{align*}$$

which proves strict balancedness.

Finally, it remains to check strict balancedness of $H"$ for segments. Take any segment $\tau $ with $v_{0}<n$ vertices. The subgraph $H"[\tau ]$ contains $v_{0}-1$ Hamiltonian edges and less than $v_{0}\cdot \frac {r}{n}+1$ loops (since the loops are almost equidistributed). Therefore,

$$\begin{align*}e_{0}<v_{0}-1+v_{0}\cdot\frac{r}{n}+1=\left(1+\frac{r}{n}\right)v_{0}. \end{align*}$$

That finishes the proof.

Proof of Proposition 2.10.

Let A be the event that $\mathbf {H}^{*}$ is simple. Then $A=A_{1}\cap A_{2}$ , where

1. 1. $A_{1}$ is the event that $\mathbf {H}_{r}$ and $\mathbf {H}_{h}$ do not share common edges.

2. 2. $A_{2}$ is the event that $\mathbf {H}_{b}$ does not contain loops or edges with multiplicity $2$ and does not share edges with $\mathbf {H}_{r}$ or with $\mathbf {H}_{h}$ .

We write $\mathbb {P}(A)=\mathbb {P}(A_{1})\mathbb {P}\left (A_{2}\bigm |A_{1}\right )$ and prove that there are positive constants $p_{1},p_{2}$ such that $\mathbb {P}\left (A_{1}\right )\geq p_{1}$ , $\mathbb {P}\left (A_{2}\big |A_{1}\right )\geq p_{2}$ .

$\mathbb {P}(A_{1})$ is equal to the probability that the random $(q-2)$ -regular graph $\mathbf {H}_{r}$ does not contain any edges of a given Hamilton cycle. When $q=2$ it is clearly $1$ , so assume $q\geq 3$ . We apply [Reference McKay16, Theorem 1.1], which bounds the probability that a random graph with specified degrees does not contain any edges of a given subgraph. For the special case of regular graphs it yields the following statement.

Theorem 2.12 (B. McKay [Reference McKay16]).

Let $1\leq d=d(n)\ll n$ be an integer and let $X=X(n)$ be a graph on vertex set $[n]$ and maximum degree $\Delta :=\Delta (X)=o(n)$ . For every even n let $G_{d,X}(n)$ denote the number of labelled d-regular graphs on $[n]$ that do not contain any edge of X. Then

$$ \begin{align*} G_{d,X}(n) & = \frac{(2E)!}{E!2^{E}(d!)^{n}}\exp\left(-\frac{nd(d-1)}{4E}-\left(\frac{nd(d-1)}{4E}\right)^{2}\right)\\ & \quad \times\exp\left(-\frac{d^2 e(X)}{2E}+O\left(\frac{d^2(d+\Delta)^2}{E}\right)\right). \end{align*} $$

Here $E=\frac {nd}{2}$ is the number of edges in a d-regular graph on n vertices.

In our case, let $d=q-2$ (which is a constant) and let X be a Hamiltonian cycle, so $e(X)=n$ and $\Delta =2$ . Also let $\emptyset $ denote the empty graph (on n vertices), so $G_{d,\emptyset }(n)$ is the number of labelled d-regular graphs. Then

$$ \begin{align*} \mathbb{P}\left(A_{1}\right)=\frac{G_{d,X}(n)}{G_{d,\emptyset}(n)}=\exp\left(-\frac{nd^2}{nd}+O\left(\frac{1}{nd}\right)\right)\sim e^{-d}=\mathrm{e}^{-(q-2)}. \end{align*} $$

Hence $\mathbb {P}\left (A_{1}\right )$ is bounded from below by a positive constant.

Now let us bound $\mathbb {P}\left (A_{2}\bigm |A_{1}\right )$ . We fix values $\mathbf {H}_{r}=H_{r}$ and $\mathbf {H}_{h}=H_{h}$ such that $A_{1}$ holds, and prove the existence of a constant $p_{2}$ (independent of $H_{r},H_{h}$ ) such that

$$\begin{align*}\mathbb{P}\left(A_{2}\mid\mathbf{H}_{r}=H_{r},\;\mathbf{H}_{h}=H_{h}\right)\geq p_{2}. \end{align*}$$

Let $R=\{x_{1},x_{2},\dots ,x_{r}\}$ (the labeling may be chosen arbitrarily) be the set of r equidistributed vertices around $H_{h}$ . Since $A_{1}$ holds, $H_{r}+H_{h}$ is a simple q-regular graph. The sequence of values $\mathbf {y}[x_{1}],\mathbf {y}[x_{2}]\dots ,\mathbf {y}[x_{r}]$ is drawn uniformly from all the $(n)_{r}$ sequences of r distinct vertices. We provide a lower bound on the number of choices which satisfy $A_{2}$ .

Let us sequentially choose the values $y[x_{1}],y[x_{2}]\dots ,y[x_{r}]$ , making sure that $A_{2}$ is satisfied at every step. When we get to $y[x_{j}]$ , there are at least $n-q-j$ possible choices which assure that $A_{2}$ is still satisfied. We deduce

$$ \begin{align*} \mathbb{P}\left(A_{2}\mid\mathbf{H}_{r}=H_{r},\;\mathbf{H}_{h}=H_{h}\right) & \geq \frac{(n-q-1)_{r}}{(n)_{r}} \overset{(*)}{\geq} \frac{(n-2c-1)_{r}}{(n)_{r}}\\ & \overset{(**)}{\geq} \frac{(n-2c-1)_{\frac{n}{2}}}{(n)_{\frac{n}{2}}} \overset{(***)}{\geq} \left(\frac{\frac{n}{2}-2c-1}{\frac{n}{2}}\right)^{\frac{n}{2}} \sim \mathrm{ e}^{-(2c+1)}. \end{align*} $$

Here $(*)$ follows from $q\leq \frac {2m}{n}\leq 2c$ , $(**)$ follows from $r<\frac {n}{2}$ , and $(***)$ holds since $\frac {n-2c-i-1}{n-i}$ decreases as a function of i.

Proof. The idea is to partition $E_{0}$ into three disjoint sets and separately bound the probability that they are subsets of $\mathbf {E}_{r},\mathbf {E}_{h},\mathbf {E}_{b}$ . It will be simpler to work with $\mathbf {H}^{*}$ , and for that we will rely on Proposition 2.10.

Formally, fix $E_{0}\subseteq \binom {[n]}{2}$ and let $\mathcal {P}$ be the set of triplets $(E_{r},E_{h},E_{b})$ which form a partition of $E_{0}$ . Note that $\left |\mathcal {P}\right |=3^{\left |E_{0}\right |}$ . For every $P=\left (E_{r},E_{h},E_{b}\right )\in \mathcal {P}$ let $A_{P}$ denote the event that in $\mathbf {H}^{*}$ we have $E_{r}\subseteq \mathbf {E}_{r}$ , $E_{h}\subseteq \mathbf { E}_{h}$ , and $E_{b}\subseteq \mathbf {E}_{b}$ . Then, from Proposition 2.10,

$$ \begin{align*} \mathbb{P}\left(E_{0}\subseteq E\left(\mathbf{H}\right)\right) \leq \frac{1}{p_{0}}\mathbb{P}\left(E_{0}\subseteq E\left(\mathbf{H}^{*}\right)\right) \leq \frac{1}{p_{0}}\sum_{P\in\mathcal{P}}\mathbb{P}(A_{P}). \end{align*} $$

We will now prove that there exists a constant $c_{1}$ such that $\mathbb {P}\left (A_{P}\right )\leq \left (c_1/n\right )^{\left |E_{0}\right |}$ for every $P\in \mathcal {P}$ . Then, taking $c_{0}=\frac {1}{p_{0}}\cdot 3c_{1}$ finishes the proof.

So, let us fix a partition $P=\left (E_{r},E_{h},E_{b}\right )$ of $E_{0}$ . Let $\ell _{0}=\left |E_{0}\right |$ and similarly define $\ell _{r},\ell _{h},\ell _{b}$ .

Step 1. We apply the following proposition from [Reference Bollobás5].

In our case, it follows that there exists a positive constant $c_r$ such that $\mathbb {P}\left (E_{r}\subseteq \mathbf {E}_{r}\right )\leq \left (\frac {c_{r}}{n}\right )^{\ell _{r}}$ .

Step 2. Let us bound $\mathbb {P}\left (E_{h}\subseteq \mathbf {E}_{h}\right )$ . Recall that $\mathbf {E}_{h}$ is the set of edges of a random Hamilton cycle. If $E_{h}$ is not contained in any Hamilton cycle, this probability is trivially $0$ , so assume that it is not the case.

If $\ell _{h}=n$ , then $E_{h}$ is already the set of edges of a Hamilton cycle, and then $\mathbb {P}\left (E_{h}\subseteq \mathbf {E}_{h}\right )=\frac {2}{(n-1)!}$ .

If $\ell _{h}<n$ , then the graph $([n],E_{h})$ has exactly $n-\ell _{h}$ connected components, all of them are either paths or isolated vertices (which are not considered as paths for now). Let s be the number of paths. Then the number of Hamilton cycles containing $E_{h}$ equals $2^{s-1}(n-\ell _{h}-1)!$ . Therefore,

$$ \begin{align*} \mathbb{P}\left(E_{h}\subseteq\mathbf{E}_{h}\right) &= 2^{s}\cdot\frac{(n-\ell_{h}-1)!\cdot n}{n!} \leq \frac{2^{\ell_{h}}}{(n-1)_{\ell_{h}}}\\ &\leq\left(\frac{2\mathrm{e}}{n-1}\right)^{\ell_{h}} = \left(\frac{n}{n-1}\right)^{\ell_{h}}\left(\frac{2\mathrm{e}}{n}\right)^{\ell_{h}} \lesssim \mathrm{e}\left(\frac{2\mathrm{e}}{n}\right)^{\ell_{h}}. \end{align*} $$

Note that the last bound also holds when $\ell _{h}=n$ .

Step 3. Finally, let us bound $\mathbb {P}\left (E_{b}\subseteq \mathbf {E}_{b}\right )$ . We shall prove that for every possible value $H_{h}$ of $\mathbf {H}_{h}$

$$\begin{align*}\mathbb{P}\left(E_{b}\subseteq\mathbf{E}_{b}\bigm|\mathbf{H}_{h}=H_{h}\right)\leq\left(\frac{2\mathrm{ e}}{n}\right)^{\ell_{b}}. \end{align*}$$

That will prove $\mathbb {P}\left (E_{b}\subseteq \mathbf {E}_{b}\right )\leq \left (\frac {2\mathrm { e}}{n}\right )^{\ell _{b}}.$

Fix a value $\mathbf {H}_{h}=H_{h}$ . It determines the set of equidistributed vertices $R=R(H_{h},r)$ . Again, we arbitrarily enumerate it: $R=\{x_{1},x_{2},\dots ,x_{r}\}$ . Recall that $\mathbf {E}_{b}$ is defined as the (multi)set of edges of the form $\{x_{j},\mathbf {y}[x_{j}]\}$ , where $\mathbf {y}[x_{1}],\dots ,\mathbf {y}[x_{r}]$ are drawn uniformly from all possible sequences of r distinct vertices. The number of ways to choose the vertices $y[x]$ such that $E_{b}\subseteq \mathbf {E}_{b}$ holds is at most $2^{\ell _{b}}(n-\ell _{b})_{r-\ell _{b}}$ . Indeed, there are at most $2^{\ell _{b}}$ ways to choose a direction $x_{j}\rightarrow y[x_{j}]$ for every edge of $E_{b}$ and at most $(n-\ell _{b})_{r-\ell _{b}}$ ways to choose the remaining $y[x_{j}]$ . Overall,

$$ \begin{align*} \mathbb{P}\left(E_{b}\subseteq\mathbf{E}_{b}\bigm|\mathbf{H}_{h}=H_{h}\right) \leq 2^{\ell_{b}}\frac{(n-\ell_{b})_{r-\ell_{b}}}{(n)_{r}} = 2^{\ell_{b}}\frac{1}{(n)_{\ell_{b}}}{\leq}\left(\frac{2\mathrm{e}}{n}\right)^{\ell_{b}}. \end{align*} $$

In conclusion, the three steps and the independence between the different components of $\mathbf {H}^{*}$ show that indeed there exists a constant $c_{1}$ such that $\mathbb {P}\left (A_{P}\right )\leq \left (\frac {c_{1}}{n}\right )^{\ell _{0}}$ . That finishes the proof.

Proof. We consider two separate cases $m\geq \frac {3}{2}n$ and $m<\frac {3}{2}n$ .

Dense case: $m\geq \frac {3}{2}n$ . In this case we follow an argument due to Bollobás [Reference Bollobás5], which proves asymmetry of the random regular graph $G(n,r)$ with $r\geq 3$ fixed. This argument directly generalizes to the following result.

For the sake of completeness, we give the full proof of Theorem 2.16 in Appendix A.

Equation (2) and Proposition 2.13 show that the random balanced graph $\mathbf {H}$ satisfies the last two properties—that the maximum degree is bounded and that the probability that the given set of edges $E_0$ belongs to the random graph is at most $(c_0/n)^{|E_0|}$ . When $m\geq \frac {3}{2}n$ it also satisfies the first property that the minimum degree is at least 3, and therefore it is asymmetric w.h.p.

Sparse case: $m<\frac {3}{2}n$ . In this case $\delta (\mathbf {G}_n)=2$ and Bollobás’s argument does not apply. Instead, we develop an entirely different approach for proving asymmetry, generally applicable to randomly perturbed cycles. Indeed, in the sparse case, the regular component vanishes and $\mathbf {H}=\mathbf {H}_{h}+\mathbf {H}_{b}$ . That is, $\mathbf {H}$ is a Hamilton cycle with additional $2\leq r<\frac {n}{2}$ randomly scattered edges. Our approach is based on the observation that non-trivial automorphisms give rise to certain configurations which are very rare in the sparse case. A key concept in the proof is that of an alternating cycle: a cycle which alternates between Hamiltonian edges and balancing edges. Since this proof may be of its own interest and since it is long enough to interrupt the flow of the article, we present it in the separate Section 6.

Claim 2.17. There is a function $B(n)=\exp \left (O(n)\right )$ such that, for every graph $H\in \mathcal {H}(n,m)$ , the number of possible values $(H_{r},H_{h},H_{b})$ of $(\mathbf {H}_{r},\mathbf {H}_{h},\mathbf {H}_{b})$ such that $H=H_{r}+H_{h}+H_{b}$ is at most $B(n)$ .

Proof. From (2) we know that $\Delta (H)\leq q+2$ . Therefore $(q+2)^{n}$ is a trivial (and very coarse) bound on the number of Hamilton cycles in H. The Hamiltonian component $H_{h}$ must be one of them.

Now fix $H_{h}$ , which also fixes the set R. For every $x\in R$ , $y[x]$ must be its neighbor in H and can therefore be chosen in at most $q+2$ ways. So the number of choices for $H_{b}$ is at most $(q+2)^{r}$ .

The values $H_{h},H_{b}$ uniquely determine $H_{r}$ (as the graph with all the remaining edges). Overall, the number of choices is at most

$$\begin{align*}(q+2)^{n+r}\leq\left(2c+2\right)^{\frac{3}{2}n}=:B(n), \end{align*}$$

where we used the inequalities $q\leq 2c$ and $r<\frac {n}{2}$ . That finishes the proof.

Claim 3.2. $ \left |\mathcal {F}\right |=\exp (-O(v) )\left |\mathcal {H}\right |=\exp (-O(v) )v^{e}. $

Proof. The second equality follows directly from the lower bound on $\left |{\cal H}\right |$ from Theorem 2.1, so it remains to prove the first equality. Let N be the number of possible values $(H_{r},H_{h},H_{b})$ such that $H_{r}+H_{h}+H_{b}$ is simple, and let $N_{{\cal F}}$ be the number of possible values $(H_{r},H_{h},H_{b})$ such that $H_{r}+H_{h}+H_{b}\in {\cal F}$ . Proposition 3.1 implies $\frac {N_{{\cal F}}}{N}=1-o(1)$ . Claim 2.17 implies $N_{{\cal F}}=\exp \left (O(v)\right )\left |{\cal F}\right |$ . Therefore $\left |{\cal F}\right |=\exp (-O(v))N_{{\cal F}}=\exp (-O(v))N$ , implying $\left |{\cal F}\right |=\exp (-O(v) )\left |{\cal H}\right |.$ The last equality follows from the fact that $|\mathcal {H}|=\exp (O(v))N$ and $|\mathcal {F}|\leq |\mathcal {H}|$ . Note that the equality $\left |\mathcal {F}\right |=\exp (-O(v) )\left |\mathcal {H}\right |$ does not exclude the possibility that $|\mathcal {F}|=\exp (-o(v))\left |\mathcal {H}\right |$ .

Proof. Fix $H\in \mathcal {F}$ and let $\mathbf {X}_{H}$ be the number of induced copies of H in $\mathbf {G}_{2}$ . Then

$$\begin{align*}\mathbb{E}\left(\mathbf{X}_{H}\right)=(n)_{v} p^{e}\left(1-p\right)^{\binom{v}{2}-e}\sim n^{v}p^{e}=n^{v-\alpha e}, \end{align*}$$

since $v,e=O(\ln n)$ and $p=n^{-\alpha }$ . From the definition of e we have $v-\alpha e\leq -\alpha $ , so overall $\mathbb {E}\left (\mathbf {X}_{H}\right )=O\left (n^{-\alpha }\right )$ . From Markov’s inequality, $\mathbb {P}\left (X_{H}\geq 1\right )=o(1)$ .

Proof. Let $\mathbf {X}_{\mathcal {F}}$ count the number of induced subgraphs $H\subseteq \mathbf {G}_{n}^{1}$ with $H\in \mathcal {F}$ . We need to prove $\mathbb {P}(\mathbf {X}_{\mathcal {F}}=0)=o(1)$ . From Chebyshev’s inequality, it suffices to prove $\frac {\mathrm { Var}(\mathbf {X}_{\mathcal {F}})}{\left [\mathbb {E}\left (\mathbf {X}_{\mathcal {F}}\right )\right ]^{2}}=o(1).$ Write $\mathbf {X}_{\mathcal {F}}=\sum _{H}\mathbb {1}_{H\subseteq \mathbf {G}_1}$ , where the sum is over all subgraphs H of the complete graph $K_{n}$ with $H\in \mathcal {F}$ . The expected value is

$$ \begin{align*} \mathbb{E}\left(\mathbf{X}_{\mathcal{F}}\right) =\sum_{H}\mathbb{P}\left(H\subseteq\mathbf{ G}_{n}^{1}\right)=\binom{n}{v}\left|\mathcal{F}\right| p^{e}\left(1-p\right)^{\binom{v}{2}-e}\sim n^{v-\alpha e}\frac{\left|\mathcal{F}\right|}{v!}. \end{align*} $$

The variance is

(3) $$ \begin{align} \mathrm{ Var}(\mathbf{X}_{\mathcal{F}})=\sum_{H,H'}\left[\mathbb{E}\left(\mathbb{1}_{H\subseteq\mathbf{G}_1,H'\subseteq\mathbf{G}_1}\right)-\mathbb{E}\left(\mathbb{1}_{H\subseteq\mathbf{G}_1}\right)\mathbb{E}\left(\mathbb{1}_{H'\subseteq\mathbf{G}_1}\right)\right]. \end{align} $$

We decompose the sum in (3) by considering different possible intersection patterns of $H,H'$ . For every non-negative integers $v_{0},e_{0}$ let $S_{v_{0},e_{0}}$ denote the sum in (3), but only over the pairs $H,H'$ which share exactly $v_{0}$ common vertices and $e_{0}$ common edges. Then $\mathrm { Var}(\mathbf {X}_{\mathcal {F}})=\sum _{v_{0},e_{0}}S_{v_{0},e_{0}}$ . When $v_{0}\leq 1$ , the indicators $\mathbb {1}_{H},\mathbb {1}_{H'}$ are independent and the corresponding summand is $0$ . Taking enhanced balancedness into account, we may therefore sum over the set $\mathcal {I}$ of pairs $(v_{0},e_{0})$ such that $v_0\geq 2$ , $e_0\leq \frac {e}{v}v_0$ and, moreover, $e_0\leq \frac {1}{\alpha }v_0-\beta _0$ whenever $v_{0}\leq \delta _{0}v$ . Each $S_{v_{0},e_{0}}$ can be written as follows:

$$ \begin{align*} S_{v_{0},e_{0}} &= \binom{n}{v}\binom{v}{v_{0}}\binom{n-v}{v-v_{0}}\cdot T_{v_{0},e_{0}}\\ &\quad \times\left[p^{2e-e_{0}}(1-p)^{2\left(\binom{v}{2}-e\right)-\left(\binom{v_{0}}{2}-e_{0}\right)}-p^{2e}(1-p)^{2\left(\binom{v}{2}-e\right)}\right]. \end{align*} $$

Here $T_{v_{0},e_{0}}$ denotes the number of possible choices of a pair of induced subgraphs $H,H'$ on two given sets of v vertices with $v_{0}$ common vertices, such that $H,H'\in \mathcal {F}$ and they share exactly $e_{0}$ edges. Simple estimations yield

(4) $$ \begin{align} \frac{S_{v_{0},e_{0}}}{[\mathbb{E}\left(\mathbf{X}_{\mathcal{F}}\right)]^{2}}\lesssim\frac{(v!)^{2}}{v_{0}!\left((v-v_{0})!\right)^{2}}\cdot\frac{T_{v_{0},e_{0}}}{\left|\mathcal{F}\right|{}^{2}}\cdot\frac{1}{n^{v_{0}-\alpha e_{0}}}. \end{align} $$

The following claim bounds the term $T_{v_{0},e_{0}}/\left |\mathcal {F}\right |{}^{2}$ .

Proof. Let us fix two sets of vertices $V_{1},V_{2}$ with $\left |V_{1}\right |=\left |V_{2}\right |=v$ and $V_{0}=V_{1}\cap V_{2}$ having $\left |V_{0}\right |=v_{0}$ . We need to bound $T_{v_{0},e_{0}}$ , the number of pairs $H_{1},H_{2}$ such that each $H_{i}$ is a graph on $V_{i}$ with $H_{i}\in \mathcal {F}$ , $H_{1}[V_{0}]=H_{2}[V_{0}]$ , and the common induced subgraph contains exactly $e_{0}$ edges.

First choose $H_{1}\in \mathcal {F}$ on $V_{1}$ such that $H_{1}\left [V_{0}\right ]$ contains exactly $e_{0}$ edges. The number of choices is trivially bounded by $\left |\mathcal {F}\right |$ . Now, given $H_{1}$ , we must choose $H_{2}\in \mathcal {F}$ on $V_{2}$ which contains a given set of $e_{0}$ edges. The number of choices is bounded by the number of graphs from $\mathcal {H}$ that contain the same set of edges which is, due to Proposition 2.13, at most $\left (\frac {c_{0}}{v}\right )^{e_{0}}N$ , where $N=N(v,e)$ is again the number of possible values $(H_{r},H_{h},H_{b})$ such that $H_{r}+H_{h}+H_{b}$ is simple. By Claim 3.2, $\left |\mathcal {F}\right |=\exp (-O(v))N$ . Therefore,

$$\begin{align*}T_{v_{0},e_{0}}\leq\left|\mathcal{F}\right|\cdot\left(\frac{c_{0}}{v}\right)^{e_{0}}\cdot\exp\left(O(v)\right)\left|\mathcal{F}\right|=\exp\left(O(v)\right)\left(\frac{c_{0}}{v}\right)^{e_{0}}\left|\mathcal{F}\right|{}^{2}. \end{align*}$$

We now return to the proof of Lemma 3.4. It suffices to prove that the right-hand side in (4) is $o\left (v^{-2}\right )$ (uniformly), since the number of summands is $\Theta \left (v^{2}\right )$ . We have

$$ \begin{align*} \frac{S_{v_{0},e_{0}}}{[\mathbb{E}\left(\mathbf{X}_{\mathcal{F}}\right)]^{2}} & = \frac{(v!)^{2}}{v_{0}!\left((v-v_{0})!\right)^{2}}\cdot\exp\left(O(v)\right)\left(\frac{c_{0}}{v}\right)^{e_{0}}\cdot\frac{1}{n^{v_{0}-\alpha e_{0}}}\\ & \leq \frac{\left(\left(v\right)_{v_{0}}\right)^{2}}{\left(\frac{v_{0}}{\mathrm{ e}}\right)^{v_{0}}}\cdot\exp\left(O(v)\right)\left(\frac{c_{0}}{v}\right)^{e_{0}}\cdot\frac{1}{n^{v_{0}-\alpha e_{0}}}\\ & \leq \frac{v^{2v_{0}}}{v_{0}^{v_{0}}}\exp\left(O(v)\right)\cdot\left(\frac{c_{0}}{v}\right)^{e_{0}}\cdot\frac{1}{n^{v_{0}-\alpha e_{0}}}. \end{align*} $$

Notice that the last expression is monotonically increasing with respect to $e_{0}$ . Therefore we may bound it for every $2\leq v_{0}\leq v$ only with $e_{0}^{*}$ , defined as the maximal $e_{0}$ such that $(v_{0},e_{0})\in \mathcal {I}$ . Note that $e_{0}^{*}=\frac {1}{\alpha }v_{0}+O(1)$ , so

(5) $$ \begin{align} \frac{S_{v_{0},e_{0}}}{[\mathbb{E}\left(\mathbf{X}_{\mathcal{F}}\right)]^{2}}=\underset{(*)}{\underbrace{\left(\frac{v^{2-\frac{1}{\alpha}}}{v_{0}}\right)^{v_{0}}\exp\left(O(v)\right)}}\cdot\underset{(**)}{\underbrace{\frac{1}{n^{v_{0}-\alpha e_{0}^{*}}}}}. \end{align} $$

We bound (5) separately for small $v_{0}$ and for large $v_{0}$ . Intuitively, for small subgraphs the enhanced balancedness property promises that $(**)$ is sufficiently small, while for large subgraphs it is $(*)$ which becomes small.

Small subgraphs. In this case we assume $v_{0}\leq \frac {c}{\omega }v$ where $c=\frac {\alpha \beta _{0}}{2}$ . By definition of v,

$$\begin{align*}v_{0}\leq\frac{c}{\omega}\left\lfloor \omega\frac{\ln n}{\ln\ln n}\right\rfloor \leq c\frac{\ln n}{\ln\ln n}. \end{align*}$$

Of course, this implies $v_{0}\leq \delta _{0}v$ , so enhanced balancedness applies: $e_{0}^{*}\leq \frac {1}{\alpha }v_{0}-\beta _{0}$ and therefore $\frac {1}{n^{v_{0}-\alpha e_{0}^{*}}}\leq n^{-\alpha \beta _{0}}$ .

As for $(*)$ , we use the simple bound

$$\begin{align*}(*)\leq v^{v_{0}}\left[\left(\frac{v}{v_{0}}\right)^{\frac{v_{0}}{v}}\right]^{v}\exp\left(O(v)\right)\leq \exp\left(v_{0}\ln v+O(v)\right). \end{align*}$$

Without loss of generality, we may assume $\omega =o(\ln \ln n)$ , so $v=o(\ln n)$ and

$$ \begin{align*} \exp\left(v_{0}\ln v+O(v)\right) \leq \exp\left(c\frac{\ln n}{\ln\ln n}\ln\ln n+o(\ln n)\right)=n^{\frac{\alpha\beta_{0}}{2}+o(1)}. \end{align*} $$

Overall, $S_{v_{0},e_{0}}/\mathbb {E}[\left (\mathbf {X}_{\mathcal {F}}\right )]^{2}\leq n^{-\frac {\alpha \beta _{0}}{2}+o(1)}$ uniformly. In particular it is $o\left (v^{-2}\right )$ .

Large subgraphs. Now assume $v_{0}\geq \frac {c}{\omega }v$ . In this case we only know $e_{0}^{*}\leq \frac {e}{v}v_{0}\leq \left (\frac {1}{\alpha }+\frac {2}{v}\right )v_{0}$ , so

$$\begin{align*}(**)=\frac{1}{n^{v_{0}-\alpha e_{0}^{*}}}\leq n^{2\alpha\frac{v_{0}}{v}}. \end{align*}$$

As for $(*)$ , we have

$$\begin{align*}\left(\frac{v^{2-\frac{1}{\alpha}}}{v_{0}}\right)^{v_{0}}\leq\left(\frac{\omega}{c}v^{1-\frac{1}{\alpha}}\right)^{v_{0}}=\left(\frac{\omega}{c}v^{-\xi}\right)^{v_{0}}, \end{align*}$$

where $\xi =\frac {1}{\alpha }-1$ is a positive constant. Combining both bounds,

$$\begin{align*}\frac{S_{v_{0},e_{0}}}{\mathbb{E}[\left(\mathbf{X}_{\mathcal{F}}\right)]^{2}}\leq\left(\omega v^{-\xi}\cdot C^{\frac{v}{v_{0}}}n^{\frac{2\alpha}{v}}\right)^{v_{0}} \end{align*}$$

for some constant $C>1$ . Note that

$$ \begin{align*}\omega C^{\frac{v}{v_{0}}}n^{\frac{2\alpha}{v}} \leq\exp\left(O(\omega)+O\left(\frac{\ln n}{v}\right)\right)\leq \exp\left(O(\omega)+O\left(\frac{\ln\ln n}{\omega}\right)\right). \end{align*} $$

Again, without loss of generality we may assume $\omega =o(\ln \ln n)$ , so

$$\begin{align*}\omega C^{\frac{v}{v_{0}}}n^{\frac{2\alpha}{v}}=\exp\left(o(\ln\ln n)\right)=v^{o(1)}. \end{align*}$$

Overall, $S_{v_{0},e_{0}}/\mathbb {E}[\left (\mathbf {X}_{\mathcal {F}}\right )]^{2}\leq \left (v^{-\xi +o(1)}\right )^{v_{0}}$ which is again $o(v^{-2})$ . We have therefore completed the proof of Lemma 3.4.

Claim 3.8. For every positive integer M there exists a positive constant $\beta $ such that the following holds. Let $V_{0}\subseteq [v]$ be a set of $v_{0}$ vertices and let $H_{0}"=\mathbf {H}"[V_{0}]$ . If the segment decomposition of $V_{0}$ contains a segment of length at most M, then

$$\begin{align*}e(H_{0}")\leq\left(1+\xi\right)v_{0}+\frac{2v_{0}}{v}-\beta. \end{align*}$$

Proof. Fix a positive integer M. Define

$$\begin{align*}\beta=\min_{v_{0},e_{0}}\left((1+\xi)v_{0}-e_{0}\right), \end{align*}$$

where the minimum is over all integers $v_{0},e_{0}$ with $1\leq v_{0}\leq M$ and $1\leq e_{0}<\left (1+\xi \right )v_{0}$ . This is a minimum over a finite, fixed set, and thus $\beta $ is a positive constant. Note that $\beta <1$ by definition.

First let $V_{0}=\tau \subseteq [v]$ be a segment with $v_{0}\leq M$ vertices. Let $e_{0}$ be the number of edges in the induced subgraph $\mathbf {H}"[\tau ]$ . Recall that $\mathbf {H}"$ is strictly balanced and its density is $1+\frac {r}{v}$ (see the proof of Proposition 2.9). Also recall that $r=\left \lceil \xi v\right \rceil +1$ , therefore,

$$\begin{align*}1+\frac{r}{v}\in\left[(1+\xi)+\frac{1}{v},(1+\xi)+\frac{2}{v}\right]. \end{align*}$$

Since M is a constant, for a sufficiently large v, the inequality $e_{0}<\left (1+\frac {r}{v}\right )v_{0}$ implies $e_{0}<(1+\xi )v_{0}$ (whenever $1\leq v_{0}\leq M$ ). In turn, $e_{0}<(1+\xi )v_{0}$ implies $e_{0}\leq (1+\xi )v_{0}-\beta $ by the definition of $\beta $ .

Now let $\tau $ be a segment of any length. Again, let $v_{0}$ be its number of vertices and let $e_{0}$ be the number of edges in $\mathbf {H}"[\tau ]$ . In this case we can only use strict balancedness to claim that

$$\begin{align*}e_{0}<\left(1+\frac{r}{v}\right)v_{0}<\left(1+\xi\right)v_{0}+\frac{2v_{0}}{v}. \end{align*}$$

Finally, let $V_{0}\subseteq [v]$ be an arbitrary set of vertices. Let $V_{0}=\tau _{1}\cup \dots \cup \tau _{t}$ be the segment decomposition. By definition, $\mathbf {H}"$ contains no edges between any pair $\tau _{i},\tau _{j}$ . Let $v_{0},e_{0}$ denote the number of vertices and edges in $\mathbf {H}"[V_{0}]$ and let $v_{i},e_{i}$ denote the number of vertices and edges in $\mathbf {H}"[\tau _{i}]$ . If at least one of the segments is of length $\leq M$ ,

$$\begin{align*}e_{0}=\sum_{i=1}^{t}e_{i}<\sum_{i=1}^{t}\left[(1+\xi)v_{i}+\frac{2v_{i}}{v}\right]-\beta=\left(1+\xi\right)v_{0}+\frac{2v_{0}}{v}-\beta. \end{align*}$$

That finishes the proof of the claim.

Proof. First notice that if $\varphi ,\psi :\mathbb {N}\rightarrow (0,\infty )$ satisfy $\varphi \leq \psi $ and x is $\varphi $ -approximable, then x is also $\psi $ -approximable. Therefore, without loss of generality, we may assume $\varphi <1$ . Recursively define a sequence of natural numbers as follows: $U_{1} = 1$ , $U_{t+1} = \left \lceil -\log _{2}\varphi \left (2^{U_{t}}\right )\right \rceil +1$ . Now define $x=\sum _{i=1}^{\infty }2^{-U_{i}}$ . Without loss of generality, we may assume that $\varphi $ is decreasing sufficiently fast such that $U_{t+1}-U_{t}$ is a strictly increasing sequence. In that case, x is an irrational number because its binary expansion is aperiodic. For every $t\in \mathbb {N}$ , consider the rational approximation $\sum _{i=1}^{t}2^{-U_{i}}$ of x, which can be written as $\frac {p_{t}}{q_{t}}$ for $q_{t}=2^{U_{t}}$ and $p_{t}=\sum _{i=1}^{t}2^{U_{t}-U_{i}}$ . Then

$$\begin{align*}0<x-\frac{p_{t}}{q_{t}}=\sum_{i=t+1}^{\infty}\frac{1}{2^{U_{i}}}\leq\sum_{i=U_{t+1}}^{\infty}\frac{1}{2^{i}}=\frac{1}{2^{U_{t+1}-1}}\leq\varphi\left(2^{U_{t}}\right)=\varphi(q_{t}). \end{align*}$$

Proof. Let us denote $(\vec {\mathbf {X}})_{\vec {m}}=(\mathbf {X}^{(1)}){}_{m_{1}}\ldots (\mathbf {X}^{(k)})_{m_{k}}$ and $m=m_{1}+\dots +m_{k}$ . Then, by decomposing $(\vec {\mathbf {X}})_{\vec {m}}$ into a sum of indicator random variables, we can write

(7) $$ \begin{align} \mathbb{E}(\vec{\mathbf{X}})_{\vec{m}}=\sum_{\vec{H}}\mathbb{P}\left(H_{1}^{(1)},\dots,H_{m_{1}}^{(1)},\dots,H_{1}^{(k)},\dots,H_{m_{k}}^{(k)}\subseteq\mathbf{ G}_{1}\right), \end{align} $$

where the sum is over all m-tuples

(8) $$ \begin{align} \vec{H}=\left(H_{1}^{(1)},\dots,H_{m_{1}}^{(1)},\dots,H_{1}^{(k)},\dots,H_{m_{k}}^{(k)}\right) \end{align} $$

such that $H_{1}^{(i)},\dots ,H_{m_{i}}^{(i)}$ are distinct copies of $H^{(i)}$ in the complete graph $K_{n}$ for every $1\leq i\leq k$ . Let us divide the sum in the right-hand side of (7) into two parts: $\mathbb {E}(\vec {\mathbf {X}})_{\vec {m}}=S_{1}+S_{2}$ where $S_{1}$ is the sum over the m-tuples $\vec {H}$ which do not share any vertices with each other, and $S_{2}$ is the remaining part of the sum.

We first estimate $S_{1}$ . Since $H^{(1)},\dots ,H^{(k)}$ are asymmetric, it is easy to see that

$$\begin{align*}S_{1}=(n)_{mv}p^{me}\sim n^{mv}p^{me}=(n^{v-\alpha e})^{m}. \end{align*}$$

By the definition of $v,e$ , we have $\left |\alpha -v/e\right |\leq 1/g(e)$ , which can also be written as $\left |v-\alpha e\right |\leq e/g(e)$ . Since $n/g(n)$ decreases and $v<e$ , we get $\left |v-\alpha e\right |\leq v/g(v)=f(n)/n$ . Since $f=o(\sqrt {\ln n}/\ln \ln n)$ ,

$$\begin{align*}S_{1}\sim\exp\left(\ln n\cdot O\left(\frac{f(n)}{n}\right)\right)=\exp(o(1))=1+o(1). \end{align*}$$

It remains to prove $S_{2}=o(1)$ . Let $\mathcal {F}^*$ be the family of all graphs (up to isomorphism) which are the result of a union of $m_{i}$ distinct copies of $H^{(i)}$ for every $1\leq i\leq m$ , with at least one shared vertex. For every $F\in \mathcal {F}^*$ , let $S_{F}$ be the sum from (7) but only over the m-tuples $\vec {H}$ whose union is isomorphic to F. Then $S_{2}=\sum _{F\in \mathcal {F}^*}S_{F}$ .

Fix $F\in \mathcal {F}^*$ . Let $C_{F}$ denote the number of m-tuples $\vec {H}$ as in (8) such that $H_{1}^{(i)},\dots ,H_{m_{i}}^{(i)}$ are distinct copies of $H^{(i)}$ and $H_{1}^{(1)}\cup \dots \cup H_{m_{k}}^{(k)}=F$ . Then

$$\begin{align*}S_{F}=\binom{n}{v(F)}C_{F}p^{e(F)}\leq C_{F}n^{v(F)}p^{e(F)}=C_{F}n^{v(F)-\alpha e(F)}. \end{align*}$$

Since $v(H^{(i)})-\alpha e(H^{(i)})<0$ for all $i\in [k]$ , then following the usual argument that is used to prove that the union of intersecting strictly balanced graphs with the same density has higher density, we derive the following claim.

Proof. For a graph F we define $\xi (F)=v(F)-\alpha e(F)$ . We begin with a few simple observations.

Observation 1. If H is isomorphic to one of $H^{(1)},\dots ,H^{(k)}$ , we have $\xi \left (H\right )=v-\alpha e<0$ . This is because $\frac {v}{e}<\alpha $ by definition.

Observation 2.For every two graphs $F_{1},F_{2}$ ,

$$\begin{align*}\xi(F_{1}\cup F_{2})=\xi(F_{1})+\xi(F_{2})-\xi(F_{1}\cap F_{2}). \end{align*}$$

Observation 3. Suppose H is isomorphic to one of $H^{(1)},\dots ,H^{(k)}$ and let $H_{0}\subset H$ be a proper subgraph with $v_{0}$ vertices and $e_{0}$ edges. Since H is strictly balanced, we have $\frac {e_{0}}{v_{0}}<\frac {e}{v}.$ Furthermore,

$$\begin{align*}\frac{e}{v}-\frac{e_{0}}{v_{0}}=\frac{ev_{0}-e_{0}v}{v_{0}v}\geq\frac{1}{v_{0}v}. \end{align*}$$

Denote $\varepsilon =\frac {e}{v}-\frac {1}{\alpha }$ (which is positive). Then

$$ \begin{align*} \frac{1}{\alpha}+\varepsilon-\frac{e_{0}}{v_{0}} & \geq \frac{1}{v_{0}v},\\ v_{0}+\alpha\varepsilon v_{0}-\alpha e_{0} & \geq \frac{\alpha}{v},\\ \xi(H_{0})=v_{0}-\alpha e_{0} & \geq \frac{\alpha}{v}-\alpha\varepsilon v_{0}. \end{align*} $$

Since $\varepsilon =O\left (\frac {1}{g(v)}\right )$ , we get that $\xi (H_{0})\geq \frac {c}{v}$ for any constant $c<\alpha $ (of course, this becomes true when the underlying t is sufficiently large).

With these observations, we now prove Claim 4.5 by induction on $m\geq 2$ .

We start with the induction base $m=2$ . Suppose $F=H_{1}\cup H_{2}$ where $H_{1},H_{2}$ are both from $\mathcal {H}$ and share a vertex. Then

$$\begin{align*}\xi(F)=\xi(H_{1})+\xi(H_{2})-\xi(H_{1}\cap H_{2})<-\xi(H_{1}\cap H_{2}). \end{align*}$$

$H_{1}\cap H_{2}$ is isomorphic to some proper subgraph $H_{0}$ of $H_{1}$ , therefore,

$$\begin{align*}\xi(F)<-\xi(H_{0})\leq-\frac{c}{v}. \end{align*}$$

Now, suppose the statement is true for $m\geq 2$ and prove it for $m+1$ . Let $F=\bigcup _{i=1}^{m+1}H_{i}$ be the union of certain copies of graphs from $\mathcal {H}$ such that, without loss of generality, $H_{1},H_{2}$ share a vertex. Let $F'=\bigcup _{i=1}^{m}H_{i}$ . Then

$$ \begin{align*} \xi(F) = \xi(F')+\xi(H_{m+1})-\xi(F'\cap H_{m+1}). \end{align*} $$

$F'\cap H_{m+1}$ is isomorphic to a subgraph $H_{0}$ of $H_{m+1}$ (not necessarily proper this time). If $H_{0}=H_{m+1}$ then $\xi (F)=\xi (F')$ . If $H_{0}\subset H_{m+1}$ then the third observation shows that $\xi (H_{0})>0$ , but $\xi (H_{m+1})<0$ and therefore $\xi (F)<\xi (F')$ . From the inductive assumption, in both cases $\xi (F)\leq \xi (F')<-\frac {c}{v}$ and that finishes the proof.

From Claim 4.5, we can write $S_{F}\leq C_{F}n^{-\frac {c}{v}}$ for any constant $c<\alpha $ . Finally, $\sum _{F\in \mathcal {F}^*}C_{F}$ is trivially bounded by $\left ((mv)_{v}\right )^{m}$ . Overall,

$$\begin{align*}S_{2}\leq(mv)^{mv}n^{-\frac{c}{v}}=\exp\left(\Theta\left(v\ln v\right)-\Theta\left(\frac{\ln n}{v}\right)\right)=o(1), \end{align*}$$

where the last estimation follows from the assumption $v=f(n)=o\left (\frac {\sqrt {\ln n}}{\ln \ln n}\right )$ . That finishes the proof.

Proof of Proposition 4.3.

Let $\vec {\mathbf {I}}=(\mathbb {1}_{\mathbf {X}^{(1)}\geq 1},\dots ,\mathbb {1}_{\mathbf {X}^{(\ell )}\geq 1})$ and $\vec {\mathbf {J}}=(\mathbb {1}_{\mathbf {Y}^{(1)}\geq 1},\dots ,$ $\mathbb {1}_{\mathbf {Y}^{(\ell )}\geq 1})$ . We need to prove $\mathbb {P}(\vec {\mathbf {I}}=\vec {\mathbf {J}})=o(1)$ . For every fixed $k\in \mathbb {N}$ , let $\vec {\mathbf {I}}_{k}$ and $\vec {\mathbf {J}}_{k}$ consist of the first k coordinates of $\vec {\mathbf {I}}$ and $\vec {\mathbf {J}}$ , respectively. Then $\mathbb {P}(\vec {\mathbf {I}}=\vec {\mathbf {J}})\leq \mathbb {P}(\vec {\mathbf {I}}_{k}=\vec {\mathbf {J}}_{k})$ . From Corollary 4.6, $\mathbb {P}(\vec {\mathbf {I}}_{k}=\vec {\mathbf {J}}_{k})\rightarrow \lambda ^{k}$ , where

$$\begin{align*}\lambda=\mathbb{P}\left(\mathrm{Pois}(1)=0\right)^{2}+\mathbb{P}\left(\mathrm{Pois}(1)\geq1\right)^{2}=\mathrm{ e}^{-2}+\left(1-\mathrm{e}^{-1}\right)^{2}. \end{align*}$$

Since this is true for every $k\in \mathbb {N}$ , we deduce $\mathbb {P}(\vec {\mathbf {I}}=\vec {\mathbf {J}})=o(1)$ and that finishes the proof.

Proof of Theorem 1.4.

Let $\mathbf {G}_{n}^{1},\mathbf {G}_{n}^{2}\sim G(n,n^{-\alpha })$ be independent and set $k=\frac {1}{\ln d_0}\ln \ln \ln n$ . Let $\mathcal {A}$ be the event that the conclusions of Bounded Closure Lemma and Lemma 5.8 hold in both $\mathbf {G}_{n}^{1}$ and $\mathbf {G}_{n}^{2}$ . Then $\mathbb {P}\left (\mathcal {A}\right )=1-o(1)$ . We show that, given the event $\mathcal {A}$ , Duplicator has a winning strategy in $\mathrm {EF}(\mathbf {G}_{n}^{1},\mathbf {G}_{n}^{2},k)$ .

Construct a sequence $t_{0}\leq t_{1}\leq \dots \leq t_{k-1}$ inductively as follows: $t_{0}=0$ , and given $t_{i}$ , we take $t_{i+1}\geq t_i$ such that the $t_{i}$ -closure of any $(k-i)$ -tuple in both $\mathbf {G}_{n}^{1}$ and $\mathbf {G}_{n}^{2}$ has at most $t_{i+1}-1$ non-roots. Note that these are the conditions from Lemma 5.11 with $t=t_{i}$ , $\ell =k-i-1$ and $u=t_{i+1}$ . From the Bounded Closure Lemma, a suitable $t_{i+1}$ exists, and can be taken to be $t_{i+1}=C(k-i)t_{i}^{d}+1$ where $C=C_{\alpha }$ is a constant (note that it also promises $t_{i+1}\geq t_{i}$ as long as we take $C\geq 1$ ). From Theorem 5.8 (with M replaced by $2M$ ), for every rooted graph $(R,H)$ with $r\leq 2M$ roots and $v\leq 2M$ non-roots and for every $t\leq 2M$ , we have that in both $\mathbf {G}_{n}^{1}$ and $\mathbf {G}_{n}^{2}$ , every r-tuple has a t-generic $(R,H)$ -extension.

Note that if $t_{i+1}\leq M$ then the assumptions of Lemma 5.11 apply with $t,\ell ,u$ as above. Indeed, we have $\ell \leq k$ and $k=o(M)$ , so $\ell +u\leq 2M$ and $u\leq M$ , and so for every rooted graph $(R,H)$ with $r\leq \ell +u$ roots and $v\leq \ell +u$ non-roots, every r-tuple has a u-generic $(R,H)$ -extension. We deduce that Duplicator can follow a look-ahead $(t_{0},t_{1},\dots ,t_{k-1})$ -strategy, provided that $t_{k-1}\leq M$ . To show that $t_{k-1}\leq M$ we consider the recurrence relation defining $t_{i}$ . We have $t_{0}=0$ , $t_{1}=1$ , and for every $1\leq i\leq k-1$ ,

$$\begin{align*}t_{i+1}=C(k-i)t_{i}^{d}+1\leq Ckt_{i}^{d}+1\leq\tilde{C}kt_{i}^{d}, \end{align*}$$

where $\tilde {C}=2C$ . We deduce $t_{i}\leq (\tilde {C}k)^{n_{i}}$ where $n_{1}=0$ and $n_{i+1}=1+dn_{i}$ , implying $n_{i}\leq d^{i}$ . Overall we have

$$ \begin{align*} t_{k-1} & \leq \left(\tilde{C}k\right)^{d^{k}}=\exp\left(d^{k}\ln\left(\tilde{C}k\right)\right)\\ & = \exp\left(\exp\left(\frac{\ln d}{\ln d_{0}}\ln\ln\ln n\right)\cdot(1+o(1))\ln\ln\ln\ln n\right)\\ & = \exp\left(o(\ln\ln n)\right)=o(M), \end{align*} $$

where we used the assumption $d<d_0$ . That finishes the proof.

Proof of Proposition 6.2.

Let us first assume that $0\leq r\leq \xi n$ for a positive constant $\xi <\frac {1}{2}$ and prove an even stronger statement: either $r=o(n)$ , and then w.h.p. $\mathbf {H}$ contains no alternating cycles, or $r=\Theta (n)$ , and then w.h.p. $\mathbf {H}$ contains no alternating cycles of length greater than $\ln n$ .

We apply Markov’s inequality. Let $\mathbf {X}_{\ell }$ be the number of alternating cycles of length $\ell $ in $\mathbf {H}$ . Write it as the sum of indicators: $\mathbf {X}_{\ell }=\sum _{C}\mathbb {1}_{\left \{ C\subseteq \mathbf {H}\right \} }$ where the sum is over all possible alternating cycles of length $\ell $ .

First, assume that $\ell \geq 4$ is even. An alternating cycle C of length $\ell $ must consist of $\frac {\ell }{2}$ black edges and $\frac {\ell }{2}$ gray edges. From Remark 6.3 it follows that C contains exactly $\frac {\ell }{2}$ vertices from R. Every edge in C has exactly one endpoint from R. It can be therefore written as

(9)

where $u_{i}\in R$ and $w_{i}\in R^{c}$ .

Given a possible alternating cycle C, the probability of $C\subseteq \mathbf {H}$ is the probability that given $\frac {\ell }{2}$ edges, each with exactly one endpoint from R, appear as gray edges in $\mathbf {H}$ . This event can be interpreted as determining the values of $\frac {\ell }{2}$ out of the r random vertices $\left \{ \mathbf {y}[x]:x\in R\right \} $ . In $\mathbf {H}^{*}$ , the probability of this event is $\frac {1}{(n)_{\frac {\ell }{2}}}$ . Therefore, by Proposition 2.10, in $\mathbf {H}$ the probability of this event is at most $\frac {p_{0}}{(n)_{\frac {\ell }{2}}}$ where $p_{0}$ is a constant. Overall,

(10) $$ \begin{align} \mathbb{E}\left(\mathbf{X}_{\ell}\right)\leq p_{0}2^{\frac{\ell}{2}}\frac{(r)_{\frac{\ell}{2}}}{(n)_{\frac{\ell}{2}}}\leq p_{0}\left(\frac{2r}{n}\right)^{\frac{\ell}{2}}. \end{align} $$

Now assume that $\ell \geq 3$ is odd. Write $\mathbf {X}_{\ell }=\mathbf {X}_{\ell }^{[b]}+\mathbf {X}_{\ell }^{[r]}$ where $\mathbf {X}_{\ell }^{[b]}$ is the number of alternating cycles with $\frac {\ell +1}{2}$ gray edges (g-cycles) and $\mathbf {X}_{\ell }^{[r]}$ is the number of alternating cycles with $\frac {\ell +1}{2}$ black edges (b-cycles).

We start with $\mathbf {X}_{\ell }^{[b]}$ . Let C be a possible g-cycle of length $\ell $ . It has a single vertex $u_{0}$ incident to two (potentially) gray edges. From Remark 6.3 it follows that C contains exactly $\frac {\ell +1}{2}$ vertices from R. Without loss of generality, we can express any g-cycle of length $\ell $ as

where $u_{i}\in R$ , $w_{i}\in R^{c}$ . Indeed, since all $y[x]$ have to be distinct, the only common vertex $u_{0}$ of two gray edges have to be in R. Then, exactly one of the two gray edges adjacent to $u_{0}$ must have both endpoints from R. Now we can similarly claim that the number of possible g-cycles of length $\ell $ is at most $2^{\frac {\ell -1}{2}}(r)_{\frac {\ell +1}{2}}$ . Moreover, the event $C\subseteq \mathbf {H}$ now determines the values of $\frac {\ell +1}{2}$ random vertices $\mathbf {y}[x]$ , therefore its probability in $\mathbf {H}$ is $\leq \frac {p_{0}}{(n)_{\frac {\ell +1}{2}}}$ . Overall,

$$\begin{align*}\mathbb{E}\left(\mathbf{X}_{\ell}^{[b]}\right)\leq p_{0}2^{\frac{\ell-1}{2}}\frac{(r)_{\frac{\ell+1}{2}}}{(n)_{\frac{\ell+1}{2}}}\leq\frac{p_{0}}{2}\left(\frac{2r}{n}\right)^{\frac{\ell+1}{2}}. \end{align*}$$

It remains to estimate the expectation of $\mathbf {X}_{\ell }^{[r]}$ . Let C be a possible b-cycle of length $\ell $ . From Remark 6.3 it follows that the number of R-vertices in C is either $\frac {\ell -1}{2}$ or $\frac {\ell +1}{2}$ . Moreover, C contains a black $2$ -path, and at least one of its endpoints must be from R (otherwise there cannot be at least $\frac {\ell -1}{2} R$ -vertices in C). Let $xyz$ be the black $2$ -path, where $x\in R$ . It is possible that $z\in R$ as well. If $z\not \in R$ then necessarily C contains exactly $\frac {\ell -1}{2} R$ -vertices. Overall we have three different types of possible b-cycles; we bound the expected number of cycles of each type separately. The three types are demonstrated in Figure 2.

Figure 2

Three types of b-cycles, $\ell =9$ . In types 2 and 3, an arrow points at the “special edge” whose choice adds a factor of $\Theta (\ell )$ to the bound. The cycles are drawn such the black edges are fixed, thus emphasizing the process of choosing the gray edges.

Figure 2 Long description

The diagram consists of three circular graphs labeled (a) Type 1, (b) Type 2, and (c) Type 3.

* Panel (a) Type 1: A circle of alternating black and gray edges. Nodes are labeled clockwise starting from the top as w sub 1, w sub 0, u sub 1, w sub 4, u sub 4, w sub 3, u sub 3, w sub 2, and u sub 2. Black edges connect w sub 1 to w sub 0, u sub 1 to w sub 4, u sub 4 to w sub 3, and u sub 3 to w sub 2.

* Panel (b) Type 2: The circular structure is modified. A black edge connects u sub 2 to w sub 2. A gray edge curves from u sub 2 to w sub 3. A black edge connects w sub 3 to a new node w prime sub 3. An arrow points to this black edge, identifying it as the special edge. Other nodes u sub 1, w sub 1, u sub 0, w sub 4, and u sub 4 maintain their relative positions with black edges between u sub 1 and w sub 1, and u sub 0 and w sub 4.

* Panel (c) Type 3: Similar to Type 2, but the gray edge from u sub 2 curves inward to connect to the edge between u sub 3 and w sub 3. An arrow points to this curved gray edge, identifying it as the special edge. The nodes u sub 1, w sub 1, u sub 0, w sub 4, u sub 4, w sub 3, u sub 3, w sub 2, and u sub 2 are present, with black edges connecting u sub 1 to w sub 1, u sub 0 to w sub 4, and u sub 3 to w sub 3.