Proof. Let $G=(V,E)$ , and consider the following auxiliary bipartite graph $H$ . The bipartition of $H$ consists of the two sets $V \times [a]$ and $E\times [b]$ , and there exists an edge between vertices $(v,i)\in V\times [a]$ and $(e,j) \in E\times [b]$ if $v$ and $e$ are incident in $G$ . We now claim that $H$ admits a matching that covers $E\times [b]$ , and to prove this we use Hall’s theorem. So consider any subset $X\subseteq E\times [b]$ . Let $F \subseteq E$ be the projection of $X$ to the first coordinate, and let $A\subseteq V$ be the set of vertices in $G$ that touch at least one edge in $F$ . Since $\textrm{mad}(G)\le \frac{2a}{b}$ , we have $|F|\le \frac{a}{b}\cdot |A|$ . Furthermore, it follows directly by definition of $H$ that $N_H(X)=A\times [a]$ . Thus, we have $|N_H(X)|=|A|\cdot a\ge b \cdot |F|\ge |X|$ , where we used that $X\subseteq F \times [b]$ in the last inequality. Thus, Hall’s condition is satisfied and we indeed find a matching $M$ in $H$ that covers every vertex in $E\times [b]$ . For $i=1,\ldots, a$ , define $E_i \,:\!=\,\{(u,v)\:|\:\exists t\in [b]\,:\, (u,i)\text{ is matched to }(uv,t)\text{ in }M\}$ . It is readily verified that $D_i \,:\!=\,(V,E_i)$ is a digraph of maximum out-degree at most $1$ , and its underlying graph $G_i$ is a subgraph of $G$ . The fact that $M$ covers every vertex in $E\times [b]$ now directly implies that every edge $e$ of $G$ belongs to exactly $b$ of the graphs $G_1,\ldots, G_a$ , as desired.

Proof. It suffices to prove the lemma for connected graphs $G$ . Indeed, if $G$ is a union of two vertex disjoint graphs non-null graphs $G_1$ and $G_2$ , we may inductively assume that for $i=1,2$ there exist homomorhisms $\phi _i \,:\, V(G_i) \to \Gamma _*(S_i,r)$ satisfying the conditions of the lemma for $G_i$ . Further, we may assume without loss of generality that $S_1 \cap S_2 = \emptyset$ . If $\phi \,:\, V(G) \to \Gamma _*(S_1 \cup S_2,r)$ is defined so that $\phi |_{V(G_i)}=\phi _i$ for $i=1,2$ , then $\phi$ is as desired.

Hence we assume that $G$ is connected and that the edges of $G$ are directed so that every vertex has at most one outneighbour. Then $G$ contains a unique directed cycle $C$ or exactly one vertex with no outneighbours.

Let $S=V(G)\cup \{s_1,\ldots, s_r\}$ , where $\{s_1,\ldots, s_r\}$ is an arbitrary set disjoint from $V(G)$ . For each vertex $v$ , let $v=v_1, v_2,\ldots, v_t$ be the vertices of the unique longest directed path starting at $v$ , and let $f(v)=\min (t, r)$ . Now set $\phi (v) \,:\!=\,(v_1,\ldots, v_{f(v)},s_1,\ldots, s_{r-f(v)})$ . Observe that if $(v,w)$ is a directed edge, then the substring obtained by deleting $v_1$ from $\phi (v)$ can be obtained from $\phi (w)$ either by deleting the final element of $\phi (w)$ or by deleting $v$ from $\phi (w)$ . Additionally, if $v$ and $w$ share an element then they share an element in $V(G)$ , and so the distance between them is at most $2r-2$ . Thus $\phi$ is a homorphism satisfying the lemma.

Proof. It suffices to show that there exists a $m\Delta (G)$ -contraction sequence from $G$ to a subgraph of $H$ , as we can then extend it to a $\max \{\textrm{stww}(H), m\Delta (G)\}$ -contraction sequence for $G$ using the $\textrm{stww}(H)$ -contraction sequence for $H$ . We obtain such a sequence by repeatedly identifying the vertices in $\phi ^{-1}(v)$ into a single vertex for every $v$ in $V(H)$ . At any step of this process each vertex of the intermediate graph $G_i$ has been obtained by identification of at most $m$ vertices of $G$ and so has degree at most $m\Delta (G)$ .

Proof. Let $\Pi =\Pi (r_1,r_2,\ldots, r_a;\,b,q)$ . First, we bound $\Delta (\Pi )$ . Given $\boldsymbol{u}=(u_1,u_2,\ldots, u_a) \in V(\Pi )$ we can enumerate its neighbours as follows. There are $\binom{a}{b} \lt a^b$ ways of choosing a set $I \subseteq [a]$ with $|I|=b$ such that the components with indices in $I$ in the neighbour are close to the corresponding components of $\boldsymbol{u}$ . For each $i \in I$ there are at most $q r^2$ ways of choosing the entries of this row in the neighbour, as there are at most $r^2$ ways of choosing the shared subsequences, and at most $q$ ways of choosing the remaining entry. Finally, there are at most $q^r$ ways of choosing entries of each remaining row, yielding an upper bound $a^b \times (qr^2)^b \times (q^r)^{a-b}$ on the number of neighbours of $\boldsymbol{u}$ . Thus

(8) \begin{align} \Delta (\Pi ) \leq r^{2b} a^b q^{ar-b(r-1)} \end{align}

We now prove the lemma by induction on $\sum _{i=1}^a r_i$ using (8) and Lemma2.3. The base case, when $r_i=1$ for every $i \in [a]$ , is trivial, as $\textrm{stww}(\Pi )\le{\textsf{v}}(\Pi )=q^a\lt r^{2b}a^bq^{ar-b(r-1)+1}$ in this case.

For the induction step assume without loss of generality that $r_1 \geq 2$ . Let $\psi \,:\, [q]^{r_1} \to [q]^{r_1-1}$ be a map erasing the last component, i.e. $\psi ((x_1,\ldots, x_{r_1-1},x_{r_1})) = (x_1,\ldots, x_{r_1-1})$ .

Note that $\psi$ maps pairs of close sequences to close ones. Indeed, if deleting the $i$ -th component of $(x_1,\ldots, x_{r_1-1},x_{r_1})$ and $j$ -th component of $(y_1,\ldots, y_{r_1-1},y_{r_1})$ yields the same sequence, then deleting $i^{\prime}$ -th component of $(x_1,\ldots, x_{r_1-1})$ and $j^{\prime}$ -th component of $(y_1,\ldots, y_{r_1-1})$ yields the same sequence, where $i^{\prime}= \min (i, r-1)$ and $j^{\prime}=\min (j, r-1)$ . Equivalently, $\psi$ is a homomorphism from $\Gamma ([q],r_1)$ to $\Gamma ([q],r_1-1).$

Let $\Pi ^{\prime} = \Pi (r_1-1,r_2,\ldots, r_a;\,b,q)$ and let $\phi \,:\, V(\Pi ) \to V(\Pi ^{\prime})$ be defined by $ \phi ((u_1,u_2,\ldots, u_a))=(\psi (u_1),u_2,\ldots, u_a)$ , i.e. $\phi$ erases the last entry of the first component of each vertex of $\Pi$ . It is easily seen from the definitions that $\phi$ is a homomorphism from $\Pi$ to $\Pi ^{\prime}$ and $|\phi ^{-1}(\boldsymbol{v})|=q$ for every $\boldsymbol{v} \in V(\Pi ^{\prime})$ . Thus by (8), Lemma2.3 applied to $\phi$ , and the induction hypothesis applied to $\Pi ^{\prime}$ we have

\begin{align*} \textrm{stww}(\Pi ) \leq \max \!\left\{\textrm{stww}(\Pi ^{\prime}), q \Delta (\Pi ) \right\} \leq r^{2b} a^b q^{ar-b(r-1)+1}, \end{align*}

and (7) holds.

Proof. Let $G_*$ be the graph with $V(G_*)=V(G)$ such that two vertices of $G_*$ are adjacent if the distance between them in $G$ is at most $\ell$ . Then $\Delta (G_*) \leq (\Delta (G))^{\ell }$ , and so the corollary follows from Theorem2.5 applied to $G_*$ .

Proof. By Lemma2.1 there exist spanning subgraphs $G_1,\ldots, G_a$ of $G$ , each of which admits an orientation with maximum outdegree one, such that each edge of $G$ belongs to at least $b$ of them. By Lemma2.2 for each $i \in [a]$ there exists a set $S_i$ and a homomorphism $\psi _i$ from $G_i$ to $\Gamma _*(S_i,r)$ such that for every pair of vertices $u,v$ , if the sequences $\psi _i(u)$ and $\psi _i(v)$ share a common element, then the distance between $u$ and $v$ in $G$ is at most $2r-2$ .

Let $\Pi = \Pi (r_1, r_2, \dots, r_a ; b,q)$ , where $r_i=r$ for all $i\in [a]$ . We define a random map $\phi \,:\, V(G) \to V(\Pi )$ as follows. For each $i \in [a]$ , we independently choose a random map $\pi _i\,:\, S_i \to [q]$ , with the values of each individual $\pi _i$ chosen uniformly and independently at random. Then, let

\begin{align*}\phi (v) \,:\!=\, \left(\pi _1(\psi _1(v)),\pi _2(\psi _2(v)), \ldots, \pi _a(\psi _a(v))\right)\end{align*}

for every $v\in V(G)$ , where we are abusing notation by denoting by $\pi _i(\psi _i(v))$ the element of $[q]^r$ obtained from $\psi _i(v)$ by applying $\pi _i$ component-wise. Note that given that $\psi _i$ is a homomorphism and by definition of $\Gamma _*(S_i,r)$ , if $uv \in E(G_i)$ then $\psi _i(u)$ and $\psi _i(v)$ are close, and so $\pi _i(\psi _i(v))$ and $\pi _i(\psi _i(u))$ are also close. As each edge of $G$ belongs to at least $b$ subgraphs $G_i$ it follows that $\phi$ is a homomorphism from $G$ to $\Pi$ , since adjacency in $\Pi$ is defined by having at least $b$ components which are close. As the components of $\psi _i(v)$ are distinct, $\pi _i(\psi _i(v))$ is uniformly distributed on $[q]^r$ . Indeed, by definition of $\pi _i$ for every $(s_1,\ldots, s_r) \in S_i^r$ such that $s_1,\ldots, s_r$ are pairwise-distinct and every $q_1,\ldots, q_r \in [q]^r$ we have

\begin{align*} \mathbb {P}\!\left[\wedge _{i=1}^r(\pi _i(s_i)=q_i)\right] = \prod _{i=1}^r\mathbb {P}\!\left[\pi _i(s_i)=q_i\right] = \frac {1}{q^r} .\end{align*}

As the maps $\pi _i$ are chosen independently, for each $v \in V(G)$ its image $\phi (v)$ is uniformly distributed on $[q]^r \times [q]^r \times \ldots [q]^{r}=V(\Pi )$ .

Note that if $\Delta (G) \leq 1$ then $\textrm{stww}(G) \leq \Delta (G)$ and the lemma trivially holds. Thus we assume $\Delta (G) \geq 2$ .

Let $k=(\Delta (G))^{2r-2}+1 \leq \Delta (G)^{2r-1}$ . By Corollary2.6, the vertex set of $G$ can be partitioned into sets $V_1,\ldots, V_k$ such that for every $i\in [k]$ , $|V_i| \leq \frac{{\textsf{v}}(G)}{k}+1$ and the distance between any pair of distinct vertices of $V_i$ in $G$ is at least $2r-1$ in $G$ . Thus for any pair of distinct vertices $u,v \in V_i$ , the sequences $\psi _j(u)$ and $\psi _j(v)$ are disjoint for every $j\in [a]$ . It follows that for each $i \in [k]$ the random variables $\{\phi (v)\}_{v \in V_i}$ are mutually independent.

We will bound $\textrm{stww}(G)$ by applying Lemma2.3 to $\phi$ chosen so that

\begin{align*}m(\phi ) \,:\!=\, \max _{\boldsymbol {u} \in V(\Pi )}|\phi ^{-1}(\boldsymbol {u})|\end{align*}

is as small as possible. Let

\begin{align*}c = \frac {3}{{\textsf {v}}(\Pi )}\left (\frac {{\textsf {v}}(G)}{k}+1\right ) .\end{align*}

Recalling that $\phi (v)$ is uniformly distributed on $V(\Pi )$ for every $v\in V(G)$ , we have that $\mathbb{E}[|\phi ^{-1}(\boldsymbol{u}) \cap V_i|] = \frac{|V_i|}{{\textsf{v}}(\Pi )} \leq c/3$ for every $\boldsymbol{u} \in V(\Pi )$ and $i \in [k]$ . Thus

\begin{align*} \mathbb {P}[|\phi ^{-1}(\boldsymbol {u}) \cap V_i| \gt c] \leq e^{-c/3} \end{align*}

by the Chernoff bound (9). It follows from the union bound that $ \mathbb{P}[|\psi ^{-1}(\boldsymbol{u}) | \gt kc] \leq ke^{-c/3}$ for every $\boldsymbol{u} \in V(\Pi )$ , and so $ \mathbb{P}[m(\phi ) \leq kc] \geq 1-{\textsf{v}}(\Pi ) ke^{-c/3}.$ Using (11) we have

\begin{align*} \log \left (k{\textsf{v}}(\Pi ) e^{-c/3} \right ) & = \log k + ar\log q - \frac{1}{{\textsf{v}}(\Pi )}\left (\frac{{\textsf{v}}(G)}{k}+1\right ) \\ &\leq 3r \Delta (G) + q ar -\frac{{\textsf{v}}(G)}{ q^{ar}\Delta (G)^{2r-1}} \\ &\leq 3r \Delta (G) + q ar -4qar\Delta (G) \\ &\lt 0. \end{align*}

Thus with positive probability we have $ m(\phi ) \leq kc = \frac{3}{{\textsf{v}}(\Pi )} \left ({\textsf{v}}(G)+k\right ) \leq 4 \frac{{\textsf{v}}(G)}{q^{ar}}$ . Applying Lemma2.3 to $\phi$ and using Lemma2.4 to bound $\textrm{stww}(\Pi )$ gives

\begin{align*}\textrm {stww}(G) \leq \max \{\textrm {stww}(\Pi ), kc\Delta (G)\} \leq \max \left \{ r^{2b} a^b q^{ar-b(r-1)+1}, \frac {4}{q^{ar}}{\textsf {v}}(G)\Delta (G)\right \},\end{align*}

as desired.

Proof. Let $b \,:\!=\, \left \lceil \frac{\ell ^{1/2}}{d\log \ell } \right \rceil$ , $a \,:\!=\, \lceil \frac{db}{2} \rceil \leq db$ , $r \,:\!=\, \left \lfloor \frac{\ell }{2db \log \ell } \right \rfloor$ . First note that

(15) \begin{align} r & \leq \frac{\ell }{2d \log \ell \cdot \frac{\ell ^{1/2}}{d\log \ell }} \leq \ell ^{1/2}, \qquad \mathrm{and} \end{align}

(16) \begin{align} ar &\leq db \cdot \frac{\ell }{2db\log \ell } \leq \frac{\ell }{2\log \ell } . \end{align}

Let $\kappa \,:\!=\, \frac{\ell }{(2a-b)r}$ , i.e. ${\textsf{v}}(G)= e^{\kappa (2a-b)r}$ . Finally, let $q \,:\!=\,\lceil e^{\kappa } \rceil \leq e^\kappa + 1 \leq 2 e^{\kappa }$ .

Our goal is to apply Lemma2.7, but first let us estimate $\kappa$ . For the lower bound we have

\begin{align*} \kappa \geq \frac{\ell }{2ar} \stackrel{(16)}{\geq } \frac{\ell }{2\frac{\ell }{2\log \ell }} = \log \ell . \end{align*}

Thus

(17) \begin{align} ar\log \left (\frac{q}{e^{\kappa }}\right ) \leq ar\!\left(\log (1+e^{-\kappa })\right) \leq are^{-\kappa } \leq \frac{ar}{\ell } \stackrel{(16)}{\leq } 1, \end{align}

and so

(18) \begin{align} q^{ar} = \left (\frac{q}{e^{\kappa }}\right )^{ar} \cdot e^{\kappa a r} \stackrel{(17)}{\leq } e^{\kappa ar +1}. \end{align}

Similarly for the upper bound on $\kappa$ , assuming ${\textsf{v}}(G)$ , and thus $\ell$ , are large enough, we have

\begin{align*} \frac{\ell }{\kappa } & = (2a-b)r \geq (d-1)br \\&\geq (d-1)b \left ( \frac{\ell }{2db \log \ell } -1\right ) \geq \frac{d-1}{2d} \frac{\ell }{ \log \ell } - bd \\ &\geq \frac{1}{4} \frac{\ell }{ \log \ell }- \left (\frac{\ell ^{1/2}}{d\log \ell } + 1\right )d \geq \frac{1}{6} \frac{\ell }{ \log \ell }, \end{align*}

where the last inequality uses that $d\leq \frac{\ell }{30\log \ell }$ and that $\ell$ is large. Thus we have

(19) \begin{align} \kappa \leq 6\log \ell . \end{align}

Next, we verify that (11) holds. As $a \geq bd/2$ implies $b \leq 2a/d$ and $\frac{a}{2a-b}$ is increasing in $b$ , we have

(20) \begin{align} e^{\kappa ar} \leq ({\textsf{v}}(G))^{\frac{a}{2a-b}} \leq ({\textsf{v}}(G))^{\frac{a}{2a-2a/d}} = ({\textsf{v}}(G))^{\frac{d}{2d-2}}. \end{align}

We have that

\begin{align*} 6 ra \cdot q^{ar+1}(\Delta (G))^{2r} & \stackrel{(15)}{\leq } 6 ra \cdot q^{ar+1}(\Delta (G))^{2\ell ^{1/2}}\\ & \stackrel{(18)}{\leq } 6 \cdot ra \cdot q \cdot e^{\kappa ar +1}(\Delta (G))^{2\ell ^{1/2}}\\ & \stackrel{(20)}{\leq } 6e\cdot ra\cdot q \cdot ({\textsf{v}}(G))^{\frac{d}{2d-2}}\cdot (\Delta (G))^{2\ell ^{1/2}}\\ & \stackrel{(16)}{\leq } 6e\cdot q \cdot \frac{\ell }{2\log \ell } \cdot ({\textsf{v}}(G))^{\frac{d}{2d-2}}\cdot (\Delta (G))^{2\ell ^{1/2}}\\ &\leq 12 e \cdot e^{\kappa } \cdot \frac{\ell }{2\log \ell } \cdot ({\textsf{v}}(G))^{\frac{d}{2d-2}} \cdot (\Delta (G))^{2 \ell ^{1/2}}\\ & \stackrel{(19)}{\leq } \ell ^{7} \cdot ({\textsf{v}}(G))^{\frac{d}{2d-2}} \cdot (\Delta (G))^{2 \ell ^{1/2}}, \end{align*}

where the last inequality holds for $\log \ell \geq 6e$ , and so to verify (11) it suffices to show that

(21) \begin{align} \ell ^{7} \cdot (\Delta (G))^{2 \ell ^{1/2}} \leq ({\textsf{v}}(G))^{\frac{d-2}{2d-2}}. \end{align}

By (13) and since $\frac{d-2}{2d-2}$ is increasing in $d$ we have

\begin{align*} \frac {d-2}{2d-2} \geq \frac {\ell ^{-1/6}}{2 + 2\ell ^{-1/6}} \geq \frac {1}{4}\ell ^{-1/6} \end{align*}

and therefore

\begin{align*} 7\log \ell + 2 \ell ^{1/2} \log \Delta (G) \stackrel{(13)}{\leq } 7\log \ell + 2 \ell ^{2/3} \leq \frac{1}{4}\ell ^{5/6} \leq \frac{d-2}{2d-2} \ell, \end{align*}

where the second inequality holds for $\ell$ large enough. Exponentiating the above we obtain (21).

Thus (11) holds and so (12) holds by Lemma2.7. As ${\textsf{v}}(G) \leq q^{(2a-b)r}$ , we have

\begin{align*} \textrm{stww}(G) & \leq \max \left \{ r^{2b} a^b q^{ar-b(r-1)+1}, \frac{4}{q^{ar}}{\textsf{v}}(G)\Delta (G)\right \} \\ &\leq 4r^{2b} a^b q^{b+1}\Delta (G) q^{(a-b)r} \\ &= \left (\Delta (G) \cdot ({\textsf{v}}(G))^{\frac{d-2}{2d-2}} \right ) \cdot \left ( 4 (r^{2b} a^b e^{\kappa (b+1)}) \cdot \left (\frac{q}{e^\kappa }\right )^{(a-b)r+b+1} \cdot \frac{e^{\kappa (a-b)r}}{({\textsf{v}}(G))^{\frac{d-2}{2d-2}}}\right ). \end{align*}

Thus to verify (14) it remains to show that

(22) \begin{align} 4 (r^{2b} a^b e^{\kappa (b+1)}) \cdot \left (\frac{q}{e^\kappa }\right )^{(a-b)r+b+1} \cdot \frac{e^{\kappa (a-b)r}}{({\textsf{v}}(G))^{\frac{d-2}{2d-2}}} = e^{O(d^{-1} \ell ^{1/2}\log \ell + \log d)}. \end{align}

We prove (22) by showing that the logarithms of the terms on the left side are of the form $O(d^{-1} \ell ^{1/2}\log \ell + \log d)$ , starting with the last:

\begin{align*} \log \left (\frac{e^{\kappa (a-b)r}}{({\textsf{v}}(G))^{\frac{d-2}{2d-2}}}\right ) &= \left ((a-b)r - \frac{d-2}{2d-2}(2a-b)r\right )\kappa \\ &=\left (\frac{2}{2d-2}a-\frac{d}{2d-2}b\right ) \kappa r\\ &\leq \left (\frac{2}{2d-2}\left (\frac{db}{2}+1\right )-\frac{d}{2d-2}b\right ) \kappa r \\ &= \frac{\kappa r}{d-1} = O\left (\frac{\log \ell \cdot \ell ^{1/2}}{d}\right ), \end{align*}

where the last estimate uses (15) and (19). For the second term, using that $r\geq 2$ for sufficiently large $\ell$ , we get

\begin{align*}\log \left (\left (\frac {q}{e^\kappa }\right )^{(a-b)r+b+1}\right ) \leq ar\log \left (\frac {q}{e^{\kappa }}\right ) \stackrel {(17)}{\leq } 1.\end{align*}

Finally, for the first term,

(23) \begin{align} \log \left (r^{2b} a^b e^{\kappa (b+1)} \right ) = b \cdot O\!\left( \log r + \log d + \log b + \kappa \right) = b \cdot O\!\left(\log d + \log \ell \right). \end{align}

If $d \leq \frac{\ell ^{1/2}}{\log \ell }$ then $\log d = O( \log \ell )$ and $b = O\!\left( \frac{\ell ^{1/2}}{d\log \ell }\right)$ and so the expression in (23) has the form $O\!\left( d^{-1}\ell ^{1/2}\right)$ as desired. Otherwise, $b=1$ and $\log \ell = O(\log d)$ and so the expression in (23) has the form $O(\log d)$ . This yields the desired bound for the first term in (22), and so (14) holds.

Proof. Let $G$ be an $n$ -vertex graph, $\ell \,:\!=\,\log n$ and $d \,:\!=\, \textrm{mad}(G)$ .

If $d = \Omega (\frac{\ell }{\log \log \ell })$ then by (1) we have

\begin{align*}\textrm {tww}(G) = O\!\left(\sqrt {dn}\right) = n^{\frac {d-2}{2d-2}} O\!\left(\sqrt {d}\cdot n^{\frac {1}{2d-2}}\right) = n^{\frac {d-2}{2d-2}} e^{O\left (\frac {\ell }{d} + \log d\right )} = n^{\frac {d-2}{2d-2}} e^{O( \log d)}.\end{align*}

Thus (3) holds, and so we may assume that $d \leq \frac{\ell }{30 \log \ell }$ . As it suffices to establish (3) when $n$ is sufficiently large (and sufficiently large as a function of $\varepsilon$ in (ii)), we assume from now on that $\ell$ is large enough to satisfy subsequent inequalities. In particular, we can assume $\ell ^{-1/6} \leq \varepsilon /2$ in (ii), and so that $d \geq 2 + \ell ^{-1/6}$ .

Given $2 + \ell ^{-1/6} \leq d \leq \frac{\ell }{30 \log \ell }$ , (3) follows from Lemma2.8 and (5), as long as

(24) \begin{align} \log\!\left(\Delta (G)\right) \leq \ell ^{1/6} \qquad \mathrm{and} \qquad \log \Delta (G) = O\!\left(d^{-1}\ell ^{1/2}\log \ell + \log d\right). \end{align}

Clearly, (24) holds in (i) as $\Delta (G) = d$ in this case.

It remains to verify that (24) holds with high probability if $G$ is as in (ii). It is well known and is an easy consequence of Chernoff type bounds that $\Delta (G) = O (\ell \frac{m}{n}) = O(\ell d)$ with high probability, and so $\log \Delta (G) = O(\log \ell )$ with high probability. Thus (24) holds with high probability as $d^{-1}\ell ^{1/2}\log \ell + \log d \geq \frac{1}{2}\log \ell$ (which can be easily seen by splitting into cases $d\geq l^{1/2}$ and $d\leq l^{1/2}$ ).

Proof. Let $n \,:\!=\,{\textsf{v}}(G)$ and $w \,:\!=\,\textrm{stww}(G)$ . Let $\mathcal P_1,\dots, \mathcal P_n$ be the sequence of partitions of $V(G)$ such that

1. 1. $|\mathcal{P}_i|=n-i+1$ for every $i\in [n]$ ,

2. 2. $\mathcal{P}_{i+1}$ is a coarsening of $\mathcal{P}_i$ for every $i\in [n-1]$ , and

3. 3. $G=G/\mathcal{P}_1,G/\mathcal{P}_2,\ldots, G/\mathcal{P}_n$ is a $w$ -contraction sequence for $G$ ,

which exists by definition of $\textrm{stww}(G)$ and contraction sequences.

We define a partition $\mathcal P=(P_1,\dots, P_k)$ for some $k \leq K$ recursively as follows. Suppose we have already defined $P_1,\dots, P_{r-1}$ . Let $X_{r-1}=P_1\cup \dots \cup P_{r-1}$ . If $V(G)\setminus X_{r-1}=\emptyset$ , we let $k=r-1$ . Otherwise, we wish to define $P_r$ .

Let $i_r$ be the minimum index $i\leq n$ such that $\mathcal P_{i} -X_{r-1}$ contains a part of size at least $\frac{{\textsf{v}}(G)}{K}$ and let $P_r$ be any such part. If no such index $i$ exists, let $i_r=n$ and set $P_r=V(G)\setminus X_{r-1}$ . Note that in the latter case, $P_r$ is the sole part of $\mathcal P_n-X_{r-1}$ , so we have $k=r$ and $|P_k|\lt \frac{{\textsf{v}}(G)}{K}$ .

We now show that $\mathcal{P}=(P_1,\dots, P_k)$ satisfies the requirements of the lemma. Clearly $\mathcal P$ is a partition of $G$ . We have $|P_r| \geq \frac{{\textsf{v}}(G)}{K}$ for $r \in [k-1]$ and $P_k \neq \emptyset$ . Thus ${\textsf{v}}(G) = \sum _{r=1}^{k}|P_r| \gt (k-1) \frac{{\textsf{v}}(G)}{K}$ , thus $|\mathcal P| = k \leq K$ as desired.

Next we show that $|P_r| \leq \frac{2{\textsf{v}}(G)}{K}$ for every $r\in [k]$ . As noted above this holds for $r=k$ and so we assume $r\lt k$ . Then $|P_r| \geq \frac{{\textsf{v}}(G)}{K} \gt 1$ and so $i_r\gt 1$ , and $P_r$ was chosen as a part of $\mathcal P_{i_r} -X_{r-1}$ of size at least $\frac{{\textsf{v}}(G)}{K}$ . As $P_r$ is a union of at most two parts of $\mathcal P_{i_r-1} -X_{r-1}$ , and each part of $\mathcal P_{i_r-1} -X_{r-1}$ has size less than $\frac{{\textsf{v}}(G)}{K}$ by the choice of $i_r$ , it follows that $|P_r| \leq \frac{2{\textsf{v}}(G)}{K}$ , as desired.

We now claim that $G/\mathcal P$ is $w$ -degenerate. It suffices to show that for every $r\in [k-1]$ , there are at most $w$ parts among $P_{r+1},\dots, P_{k}$ with neighbours in $P_r$ . Indeed, $P_r=P^{\prime}_r-X_{r-1}$ for some $P^{\prime}_r \in \mathcal{P}_{i_r}$ . As $G / \mathcal{P}_{i_r}$ has maximum degree at most $w$ , there are parts $\hat P_1,\hat P_2,\ldots, \hat P_s\in \mathcal{P}_{i_r}$ for some $s \leq w$ such that every neighbour of $P_r$ in $G-X_{r-1}$ belongs to one of them. As $i_r \leq i_{r+1} \leq \ldots \leq i_k$ , each part $\hat P_j$ intersects at most one of $P_{r+1},\dots, P_{k}$ , implying the claim.

This concludes the proof of the lemma.

Proof. Set $C_0 \,:\!=\,24000$ . Let $\varepsilon$ be given.

Choose $n_0$ large enough such that $\frac{\varepsilon }{2}\left (\frac{n_0}{\log n_0}\right )^{\frac{\varepsilon }{2+4\varepsilon }}\geq 1$ , and further such that $\frac{2}{d}+\frac{4d}{\log n} \leq 1$ for every $n,d$ such that $n\ge n_0$ and $2+2\varepsilon \leq d \leq \frac{1}{5}\log n$ .

Let $n,m,d$ be as in the statement.

Let $w \,:\!=\, \left \lfloor \varepsilon d \left (\frac{ n}{\log n}\right )^{\frac{d-2}{2d-2}} \right \rfloor$ and $K \,:\!=\,\left \lfloor \frac{d^2n}{w\log n}\right \rfloor$ .

By our choice of $n_0$ , we can ensure that

(27) \begin{align} w\geq \frac{\varepsilon }{2} d \left (\frac{ n}{\log n}\right )^{\frac{d-2}{2d-2}} \ge d \end{align}

and thus $K\le \frac{dn}{\log n}\le \frac{n}{5}\lt n$ . Furthermore, as $w\lt d\frac{n}{\log n}$ we have that $\frac{d^2n}{w\log n}\geq d\gt 2$ and so

(28) \begin{align} K\gt \frac{d^2n}{2w\log n}. \end{align}

By Lemma3.1, if $G$ is a graph with $V(G)=[n]$ and $\textrm{stww}(G) \leq w$ , then there exists a partition $\mathcal{P}=(P_1,\ldots, P_K)$ of $[n]$ such that $|P_i| \leq \frac{2n}{K}$ for every $i \in K$ and $G/\mathcal P$ is $w$ -degenerate. We wish to compute the number of graphs $G$ for which this is possible.

For a given partition $\mathcal P=(P_1,\ldots, P_K)$ of $[n]$ and $F \subseteq \binom{[K]}{2}$ , let $E(\mathcal{P},F)$ be the set of all $\{u,v\} \in [n]^2$ such that either $u,v \in P_i$ for some $i \in [K],$ or $u \in P_i$ and $v \in P_j$ for some $\{i,j\} \in F$ . In other words, $E(\mathcal{P},F)$ is the set of possible edges for a graph $G$ on $[n]$ if $E(G/\mathcal P)\subseteq F$ (writing $V(G/\mathcal P)=[K]$ for simplicity).

Let $N$ be the number of graphs $G$ with $V(G)=[n]$ , ${\textsf{e}}(G)=m$ and $\textrm{stww}(G) \leq w$ . Every such graph $G$ is determined by the choice of a partition $\mathcal{P}$ of $[n]$ with $|\mathcal{P}|=K$ , a set $F \subseteq \binom{[K]}{2}$ with $|F|=wK$ (since it follows from degeneracy that ${\textsf{e}}(G/\mathcal P) \leq wK$ ) and a choice of $E(G) \subseteq E(\mathcal{P},F)$ with $|E(G)|=m$ .

There are at most $K^n$ choices of $\mathcal{P}$ .

The number of choices of $F$ is upper bounded by

(29) \begin{align} \binom{\binom{K}{2}}{wK} &\stackrel{(25)}{\leq } \left (\frac{eK}{w}\right )^{wK} \stackrel{(28)}{\leq } \left (\frac{ed^2n}{w^2\log n}\right )^{\frac{d^2 n}{\log n}} \stackrel{(27)}{\leq }\left (\frac{ed^2n}{ \frac{\varepsilon ^2}{4} d^2 \left (\frac{ n}{\log n}\right )^{\frac{2d-4}{2d-2}} \log n}\right )^{\frac{d^2 n}{\log n}} \nonumber \\ &\leq \left (\frac{4e}{\varepsilon ^2}\right )^{\frac{d^2 n}{\log n}} n^{\frac{d^2 n}{(d-1)\log n}} =\left (\frac{4e}{\varepsilon ^2}\right )^{\frac{2dm}{\log n}} e^{\frac{2dm}{d-1}} \leq e^{4m}\cdot \left (\frac{4e}{\varepsilon ^2}\right )^{\frac{2d m}{\log n}} \end{align}

Finally, using that

\begin{align*}|E(\mathcal {P},F)| = \sum _{\{i,j\}\in F}|P_i||P_j| + \sum _{i \in [K]}\binom {|P_i|}{2} \leq (|F|+K)\left (\frac {2n}{K}\right )^2= K(w+1)\left (\frac {2n}{K}\right )^2\leq \frac {8wn^2}{K},\end{align*}

the number of choices of $E(G) \subseteq E(\mathcal{P},F)$ with $|E(G)|=m$ is upper bounded by

(30) \begin{align} \binom{|E(\mathcal{P},F)|}{m} \stackrel{(25)}{\leq } \left (\frac{e\frac{8wn^2}{K}}{m}\right )^{m} = \left (\frac{16ewn}{dK}\right )^{m}. \end{align}

Combining the upper bounds (29) and (30) on the number of choices of $F$ and $E(G) \subseteq E(\mathcal{P},F)$ , respectively, we obtain

\begin{align*} N^{\frac{1}{m}} &\leq K^{2/d} \cdot e^{4} \left (\frac{4e}{\varepsilon ^2}\right )^{\frac{2d}{\log n}} \cdot \frac{16ewn}{dK}\\ &= 16 e^5 \cdot (4e)^{\frac{2d}{\log n}}\cdot \varepsilon ^{-\frac{4d}{\log n}} \cdot K^{2/d-1}\cdot w \cdot \frac{n}{d}\\ &\stackrel{(26), (28)}{\leq } 8 e^5 \cdot (4e)^{\frac{2\cdot \frac{1}{5}\log n}{\log n}}\cdot \varepsilon ^{-\frac{4d}{\log n}}\cdot \left (\frac{2w\log n}{d^2 n}\right )^{\frac{d-2}{d}}\cdot w \cdot \frac{n^2}{m}\\ &\leq 16 e^5 \cdot (4e)^{\frac{2}{5}}\cdot \varepsilon ^{-\frac{4d}{\log n}} \cdot \left (\frac{\log n}{ n}\right )^{\frac{d-2}{d}}\cdot d^{-\frac{2d-4}{d}}\cdot w^{\frac{2d-2}{d}} \cdot \frac{n^2}{m}\\ &\leq 8000\cdot \varepsilon ^{-\frac{4d}{\log n}} \cdot \left (\frac{\log n}{ n}\right )^{\frac{d-2}{d}}\cdot d^{-\frac{2d-4}{d}}\cdot \left (\varepsilon d \left (\frac{ n}{\log n}\right )^{\frac{d-2}{2d-2}}\right )^{\frac{2d-2}{d}} \cdot \frac{n^2}{m}\\ &= 8000\cdot \varepsilon ^{2-\left (\frac{2}{d}+\frac{4d}{\log n}\right )} \cdot d^{\frac{2}{d}}\cdot \frac{n^2}{m}\\ &\leq 24000\cdot \varepsilon \cdot \frac{n^2}{m}=C_0\cdot \varepsilon \cdot \frac{n^2}{m}, \end{align*}

the last inequality following from our choice of $n_0$ .

This concludes the proof of the lemma.

Proof. Let $\varepsilon \,:\!=\, \frac{C_1}{3 C_0}$ , where $C_0$ and $C_1$ are the constants satisfying the conditions of Lemma3.2 and Theorem3.3, respectively. We may suppose that $n\geq n_0$ , where $n_0$ is obtained from Lemma3.2, depending on $\varepsilon$ . Let $w \,:\!=\, \varepsilon \frac{d}{\sqrt{\log n}}n^{\frac{d-2}{2d-2} }.$ Then by Lemma3.2 there are at most

\begin{align*}\left (C_0\varepsilon \frac {2n}{d}\right )^{\frac {dn}{2}}\end{align*}

$d$ -regular graphs on $n$ -vertices with $\textrm{stww}(G) \lt w$ , and by Theorem3.3 it follows that the probability that $\textrm{stww}(G) \lt w$ is at most

\begin{align*} \left (C_0\varepsilon \frac {2n}{d}\right )^{\frac {dn}{2}} / \left (C_1\frac {n}{d}\right )^{\frac {dn}{2}} = \left (\frac {2C_0\varepsilon }{C_1}\right )^{\frac {dn}{2}} = \left (\frac {2}{3}\right )^{\frac {dn}{2}}\leq \left (\frac {2}{3}\right )^n\xrightarrow {n\rightarrow \infty } 0.\end{align*}

Thus $\textrm{stww}(G)\geq w$ w.h.p., as desired.

Proof. Given the upper bound on $m$ , we may assume that $n$ is large enough such that $\binom{n}{2}-m\geq \frac{\binom{n}{2}}{e}$ (and $n\geq e^2+1$ ).

We start with an auxiliary computation. Let $d \,:\!=\, \frac{m}{n}\geq 1+\varepsilon$ and let

\begin{align*}f(x) \,:\!=\, e^{(2d+1)x} \left (\frac {x-1}{n-1}\right )^{(d-1)x}. \end{align*}

Note that for $2 \leq x \leq \alpha (n-1)$ , we have

\begin{align*} \frac{f(x+1)}{f(x)} &= e^{2d+1}\left (\frac{x}{x-1}\right )^{(d-1)x}\left (\frac{x}{n-1}\right )^{d-1} \leq e^{2d+1}4^{d-1}\alpha ^{d-1}=e^3 \!\left(4e^2\alpha \right)^{d-1}\\ &=e^3\!\left(e^{-\frac{4}{\varepsilon }+2}\right)^{d-1} \leq e^3\!\left(e^{-\frac{4}{\varepsilon }+2}\right)^{\varepsilon } =e^{2\varepsilon -1}\leq \frac{1}{2}, \end{align*}

where for the first inequality sign, we used that $\left(\frac{x}{x-1}\right)^x$ is monotonically decreasing for $x\gt 1$ and that $x\ge 2$ . It follows that $f(x) \leq f(2)2^{2-x}$ for all integers $2 \leq x \leq \alpha (n-1)$ .

Moving on to the main proof, for $X \subseteq [n]$ let $\mathcal{B}(X)$ denote the set of all graphs $G \in \mathcal{G}_{n,m}$ such that ${\textsf{e}}(G[X]) \gt d|X|$ . Let $x \,:\!=\, |X|$ and $k \,:\!=\, \lceil dx \rceil$ . Then

(31) \begin{align} |\mathcal{B}(X)| \leq \binom{\binom{x}{2}}{k} \binom{\binom{n}{2}}{m-k}, \end{align}

as there are at most $\binom{\binom{x}{2}}{k}$ ways of choosing $k$ edges of $G[X]$ and at most $\binom{\binom{n}{2}}{m-k}$ choices for the remaining edges. Thus

\begin{align*} \frac{|\mathcal{B}(X)|}{|\mathcal{G}_{n,m}|} &\leq \frac{\binom{\binom{x}{2}}{k} \binom{\binom{n}{2}}{m-k}}{\binom{\binom{n}{2}}{m}} = \binom{\binom{x}{2}}{k}\frac{ \frac{\binom{n}{2}!}{(m-k)!\left (\binom{n}{2}-(m-k)\right )!}}{\frac{\binom{n}{2}!}{m!\left (\binom{n}{2}-m\right )!}}\\ &= \binom{\binom{x}{2}}{k} \frac{m(m-1)\dots (m-k+1)}{\left (\binom{n}{2}-m+k\right )\left (\binom{n}{2}-m+k-1\right )\dots \left (\binom{n}{2}-m+1\right )}\\ &\leq \left (\frac{e\binom{x}{2}}{k}\right )^k \frac{m^k}{\left (\binom{n}{2}-m\right )^k} \leq \left (\frac{e\binom{x}{2}}{dx} \cdot \frac{dn}{\binom{n}{2}/e}\right )^k\\ &= \left (\frac{e^2 (x-1)}{n-1}\right )^k \leq \left (\frac{e^2 (x-1)}{n-1}\right )^{dx}. \end{align*}

We upper bound the proportion of graphs in $\mathcal{G}_{n,m}$ which are not $\alpha$ -balanced by

\begin{align*} \sum _{X \subseteq [n], 0 \lt |X| \lt \alpha n} &\frac{|\mathcal{B}(X)|}{|\mathcal{G}_{n,dn}|} \leq \sum _{1 \leq x \lt \alpha n} \binom{n}{x}\left (\frac{e^2(x-1)}{(n-1)}\right )^{dx} \leq \sum _{2 \leq x \lt \alpha n}\left (\frac{en}{x}\right )^{x}\left (\frac{e^2(x-1)}{(n-1)}\right )^{dx} \\ &\leq \sum _{2 \leq x \lt \alpha n} e^{(2d+1)x} \left (\frac{x-1}{n-1}\right )^{(d-1)x} = \sum _{2 \leq x \lt \alpha n} f(x) \leq f(2) \sum _{2 \leq x \lt \alpha n} 2^{2-x} \\ &\leq 2 f(2) = \frac{2e^{2(2d+1)}}{(n-1)^{2(d-1)}}=2e^6\left (\frac{e^2}{(n-1)}\right )^{2(d-1)} \leq 2e^6\left (\frac{e^2}{(n-1)}\right )^{2\varepsilon }. \end{align*}

As the last term tends to $0$ as $n \to \infty$ the lemma follows.

Proof. We may first suppose that $n$ is large enough such that $\alpha n\geq 3$ .

Say a graph $G$ with vertex set $[n]$ has property (*) if (32) holds for every $X\subseteq [n]$ with $|X|\geq \alpha n+1$ .

We first claim that if $G$ is a random graph $G(n,p)$ , with $p=\frac{m}{\binom{n}{2}}$ , then (*) holds.

Let $X\subseteq [n]$ such that $|X|\geq \max (\alpha n+1,3)$ be fixed and $x=|X|$ . Then, ${\textsf{e}}(G[X])$ is a sum of independent binomial variables (one for each possible edge). We have $\mathbb{E}[{\textsf{e}}(G[X])]=p\cdot \binom{x}{2}=\frac{m\cdot \binom{x}{2}}{\binom{n}{2}}= \frac{mx(x-1)}{n(n-1)}$ .

Note that the function $\frac{\log x}{x}$ is monotone decreasing for $x\geq e$ . In particular, as $x\leq n$ , $\frac{\log x}{x}\geq \frac{\log n}{n}$ . Let $f_1(n)$ and $f_2(n)$ be two functions, such that $n f_1(n)\leq m\leq n f_2(n)$ ; we will have to consider two different regimes. However we will always have $f_2(n)\leq \frac{1}{11}\log n$ , and so $\frac{\log n}{10f_2(n)}\gt 1$ . We then have that

\begin{align*} \frac{1}{10}x\log x &= \frac{1}{10}\cdot \frac{\log x}{x}x^2 \geq \frac{1}{10}\cdot \frac{\log n}{n}x^2\cdot \frac{m}{n f_2(n)} =\frac{\log n}{10 f_2(n)}\cdot \frac{mx^2}{n^2}\\ &\geq \frac{\log n}{10 f_2(n)}\cdot \frac{mx(x-1)}{n(n-1)} =\left (1+\left (\frac{\log n}{10 f_2(n)}-1\right )\right )\mathbb{E}[{\textsf{e}}(G[X])]. \end{align*}

Hence, by the Chernoff bound (10),

\begin{align*} \mathbb{P}\left [{\textsf{e}}(G[X])\geq \frac{1}{10}x\log x\right ] &\leq \mathbb{P}\left [{\textsf{e}}(G[X])\geq \left (1+\left (\frac{\log n}{10 f_2(n)}-1\right )\right )\mathbb{E}[{\textsf{e}}(G[X])]\right ]\\ &\leq \exp \left (-\frac{\left (\frac{\log n}{10 f_2(n)}-1\right )^2}{2+\left (\frac{\log n}{10 f_2(n)}-1\right )}\cdot \frac{mx(x-1)}{n(n-1)}\right )\\ &\leq \exp \left (-\frac{\left (\frac{\log n}{10 f_2(n)}-1\right )^2}{1+\frac{\log n}{10 f_2(n)}}\cdot \frac{n f_1(n)\cdot (\alpha n)^2}{n^2}\right )\\ &\lt \exp \left (-\alpha ^2\frac{\left (\frac{\log n}{10 f_2(n)}-1\right )^2}{\frac{\log n}{5 f_2(n)}}f_1(n) \cdot n \right ). \end{align*}

If $n\leq m\leq n\sqrt{\log n}$ , i.e. $f_1(n)=1$ and $f_2(n)=\sqrt{\log n}$ , then this value becomes

\begin{align*}\exp \left (-\alpha ^2\frac {\left (\frac {\log n}{10 \sqrt {\log n}}-1\right )^2}{\frac {\log n}{10 \sqrt {\log n}}}n\right ) =\exp \left (-\frac {\alpha ^2}{10}\left (\sqrt {\log n}-20+\frac {100}{\sqrt {\log n}}\right )n\right )\ll 2^{-n}.\end{align*}

Otherwise, if $n\sqrt{\log n}\leq m\leq \frac{1}{11}n\log n$ , i.e. $f_1(n)=\sqrt{\log n}$ and $f_2(n)=\frac{1}{11}\log n$ , then this value becomes

\begin{align*}\exp \left (-\alpha ^2\frac {\left (\frac {\log n}{10 \cdot \frac {1}{11}\log n}-1\right )^2}{\frac {\log n}{5 \cdot \frac {1}{11}\log n}}\sqrt {\log n}\cdot n \right ) =\exp \left (-\frac {\alpha ^2}{220}\sqrt {\log n} \cdot n\right )\ll 2^{-n}.\end{align*}

Given that are at most $2^n$ possible choices of $X$ , in all cases the probability that there is some $X$ with $|X|\geq \alpha n+1$ for which (32) does not hold converges to $0$ as $n\rightarrow \infty$ . This completes the proof of the claim.

We now show the statement when $G$ is uniformly chosen in $\mathcal G_{n,m}$ with a coupling argument.

Let $G(n,p,m)$ denote the random graph distribution defined by conditioning $G(n,p)$ on having at least $m$ edges. The number of edges of $G(n,p)$ follows a binomial distribution with parameters $B(\binom{n}{2},p)$ . It is well-known (see [Reference Lord9], for instance) that when the mean of a binomial distribution is an integer, it is also equal to the median. In particular, for our previous choice $p=\frac{m}{\binom{n}{2}}$ ,

\begin{align*}\mathbb {P}({\textsf {e}}(G(n,p)\geq m)\geq \frac {1}{2}.\end{align*}

It thus also holds that if $G$ is a random graph $G(n,p,m)$ , with high probability (*) holds.

Let $G$ and $G^{\prime}$ be random graphs obtained using the following process. $G^{\prime}$ will have distribution $G(n,p,m)$ , and $G$ will be chosen as a uniformly random subgraph of $G^{\prime}$ with exactly $m$ edges. It is immediate by symmetry that $G$ is a uniformly random graph in $\mathcal G_{n,m}$ . Furthermore, $E(G)\subseteq E(G^{\prime})$ and so ${\textsf{e}}(G[X])\leq{\textsf{e}}(G^{\prime}[X])$ for any $X\subseteq [n]$ . As (*) holds with high probability for $G^{\prime}$ , it thus follows that with high probability (*) holds for $G$ . This concludes the proof of the statement.

Proof. W.l.o.g. suppose $\varepsilon \lt 0.1$ , let $\alpha = \frac{1}{4}e^{-\frac{4}{\varepsilon }}$ and let $C_0$ be as in Lemma3.2. We show that $\delta = \frac{\alpha ^{3/2} 4^{-2/\alpha }}{24C_0}$ satisfies the theorem. We may suppose that $n$ is sufficiently large such that $\alpha (n-1) \geq \frac{\alpha }{2}n$ , $\binom{n}{2}-m\geq n^2/3$ , which is possible given the upper bound on $m$ , and $\alpha (n-1)\geq n_0$ , where $n_0$ is obtained from Lemma3.2.

Let $S(X,m^{\prime})$ be the set of all graphs in $\mathcal G_{n,m}$ such that ${\textsf{e}}(G[X])=m^{\prime}$ and $X$ is a maximal subset of $[n]$ satisfying $\textrm{mad}(G)=\frac{2{\textsf{e}}(G[X])}{|X|}$ , i.e. such that $\textrm{mad}(G)$ is the average degree of $G[X]$ . Note that $\textrm{mad}(G)\geq \frac{2e(G)}{{\textsf{v}}(G)}=\frac{2m}{n}$ .

By Lemma3.5, with high probability every $X\subseteq [n]$ with $|X|\leq \alpha (n-1)$ is such that ${\textsf{e}}(G[X])\leq \frac{m}{n}|X|$ . In particular, for such an $X$ , $\frac{2{\textsf{e}}(G[X])}{|X|}\leq \frac{2m}{n}\leq \textrm{mad}(G)$ . Hence, no such $X$ has average degree greater than that of the entire graph $G$ . Hence, with high probability $G$ has a set $X\subseteq [n]$ which attains the maximum average degree and has size $|X|\geq \alpha (n-1)$ .

On the other hand, Lemma3.6 states that with high probability every set $X$ with $|X|\geq \alpha (n-1)$ is such that ${\textsf{e}}(G[X])\leq \frac{1}{10}|X|\log |X|$ .

Hence, with high probability $G$ belongs to some set $S(X,m^{\prime})$ where $|X| \geq \alpha (n-1)$ and $m^{\prime}\leq \frac{1}{10}|X|\log |X|$ . Furthermore, as $X$ attains the maximum average degree, then $\frac{2m^{\prime}}{|X|}\geq \frac{2m}{n}$ and so $m^{\prime}\geq \frac{m}{n}|X|\geq (1+\varepsilon )|X|$ .

Let $w \,:\!=\, \delta \frac{d}{\sqrt{\log n}}n^{\frac{d-2}{2d-2} }$ . Let $N(X,m^{\prime})$ be the number of graphs $G \in S(X,m^{\prime})$ with $\textrm{stww}(G) \leq w$ . As there are at most $2^n$ choices of $X$ and $o(2^n)$ choices of $m^{\prime}$ , to prove the theorem it suffices to show that for any $X$ and $m^{\prime}$ as above we have

(34) \begin{align} 4^n N(X,m^{\prime}) =o( |\mathcal G_{n,m}|). \end{align}

Let $x \,:\!=\,|X|$ and $\varepsilon ^{\prime} \,:\!=\,\frac{2\delta }{\alpha ^{1/2}}$ . Note that

\begin{align*}\varepsilon ^{\prime}=\frac {\alpha \cdot 4^{-2/\alpha }}{12C_0}\lt \alpha =\frac {1}{4}e^{-\frac {4}{\varepsilon }}\lt \varepsilon .\end{align*}

As $n\geq x \geq \alpha (n-1) \geq \frac{\alpha }{2}n$ , we have

\begin{align*}\varepsilon ^{\prime} d\left (\frac {x}{\log x}\right )^{\frac {d-2}{2d-2}} \geq \varepsilon ^{\prime} \sqrt {\frac {\alpha }{2}} \cdot \frac {d}{\sqrt {\log n}} n^{\frac {d-2}{2d-2}} \geq w.\end{align*}

Hence, as $\textrm{stww}(G) \leq w$ we have $\textrm{stww}(G[X]) \leq w \leq \varepsilon ^{\prime} \left (\frac{x}{\log x}\right )^{\frac{d-2}{2d-2}}$ . Given that $x\geq \alpha (n-1)\geq n_0$ and $(1+\varepsilon ^{\prime})x\leq (1+\varepsilon )x\leq m^{\prime}\leq \frac{1}{10}x\log x$ , by Lemma3.2 there are at most $\left (C_0 \varepsilon ^{\prime} \frac{x^2}{m^{\prime}}\right )^{m^{\prime}}$ possible choices of for the subgraph $G[X]$ such that $G \in S(X,m^{\prime})$ and $\textrm{tww}(G) \leq w$ . There are also at most $\binom{\binom{n}{2}-\binom{x}{2}}{m-m^{\prime}}\leq \binom{\binom{n}{2}}{m-m^{\prime}}$ choices for the remaining edges of $G$ . It follows that

\begin{align*} N(X,m^{\prime}) \leq \left (C_0 \varepsilon ^{\prime} \frac {x^2}{m^{\prime}}\right )^{m^{\prime}}\binom {\binom {n}{2}-\binom {x}{2}}{m-m^{\prime}}.\end{align*}

Using $m \leq \frac{n}{x}m^{\prime} \leq \frac{2}{\alpha }m^{\prime}$ , we obtain

\begin{align*} &\left (\frac{4^nN(X,m^{\prime})}{|G_{n,m}|}\right )^{1/m^{\prime}} \leq 4^{n/m^{\prime}} C_0 \cdot \varepsilon ^{\prime} \cdot \frac{x^2}{m^{\prime}} \left (\frac{\binom{\binom{n}{2}}{m-m^{\prime}}}{\binom{\binom{n}{2}}{m}}\right )^{1/m^{\prime}} \\ & \leq 4^{m/m^{\prime}} C_0 \cdot \frac{2\delta }{\alpha ^{1/2}} \cdot \frac{x^2}{m^{\prime}} \left (\frac{\frac{\binom{n}{2}!}{(m-m^{\prime})!\left (\binom{n}{2}-(m-m^{\prime})\right )!}}{\frac{\binom{n}{2}!}{m!\left (\binom{n}{2}-m\right )!}}\right )^{1/m^{\prime}} \\ & \leq 4^{m/m^{\prime}} C_0 \cdot \frac{2\delta }{\alpha ^{1/2}} \cdot \frac{x^2}{m^{\prime}} \left (\frac{m(m-1)\dots (m-m^{\prime}+1)}{\left (\binom{n}{2}-m+m^{\prime}\right )\left (\binom{n}{2}-m+m^{\prime}-1\right )\dots \left (\binom{n}{2}-m+1\right )}\right )^{1/m^{\prime}} \\ &\leq 4^{2/\alpha } C_0 \cdot \frac{2\delta }{\alpha ^{1/2}} \cdot \frac{x^2}{m^{\prime}}\cdot \frac{m}{\binom{n}{2}-m} \leq 4^{2/\alpha } C_0 \cdot \frac{2\delta }{\alpha ^{1/2}} \cdot \frac{m}{m^{\prime}} \cdot \frac{x^2}{n^2/3} \\ &\leq \delta \cdot \frac{12}{\alpha ^{3/2}} \cdot 4^{2/\alpha } \cdot C_0 \leq 1/2, \end{align*}

implying (34) as desired. This concludes the proof of the theorem.