Proof. Let $V(G)=V_1\cup \ldots \cup V_n$ be a random partition of $V(G)$ into sets of size $Cd$ . Then, for any vertex $v\in V(G)$ and index $i\in [n]$ , $d(v,V_i)$ follows a hypergeometric distribution with parameters $N^{\prime}=N$ , $n^{\prime}=|V_i|$ and $m^{\prime}=d(v)$ , and has expectation

\begin{equation*}\mathbb E[d(v,V_i)]=d(v)\cdot \frac {|V_i|}{N}\ge \alpha Cd.\end{equation*}

Then, from Lemma 2.1, we have

\begin{equation*}\mathbb P(d(v,V_i)\le (\alpha -\delta )Cd)\le 2e^{-2\delta ^2Cd}.\end{equation*}

Therefore, using the union bound and that $H$ is $d$ -regular, we have

\begin{equation*}\mathbb P((V_1,\ldots,V_n)\mbox { is not }(H,\alpha -\delta )\mbox {-good})\le 2 |G|\cdot d\cdot 4e^{-2\delta ^2Cd}\le 2Cn^3e^{-2\delta ^2C\log n}\lt 1.\end{equation*}

Proof. Set $m_1=\dots =m_{d-1}=C-1$ and $m_d=C-2$ . We start by dividing $[d]$ into a collection of subintervals that we will use as a guide for constructing our partition. Let $I_{0,1}=[d]$ and let $s\ge 0$ be minimal integer such that $2^{s-1}\lt d\le 2^{s}$ . Iteratively, for $0\le i\lt s$ and $1\le j\le 2^{i}$ , we partition $I_{i,j}$ into intervals $I_{i+1,2j-1}$ and $I_{i+1,2j}$ such that $\big ||I_{i+1,2j-1}|-|I_{i+1,2j}|\big |\le 1$ . Note that at each step $I_{i,j}$ is divided into two subintervals of length roughly $|I_{i,j}|/2$ and thus, after $i$ steps, $[d]$ is divided into $2^{i}$ subintervals of length approximately $d/2^{i}$ . Furthermore, as $\big ||I_{i+1,2j-1}|-|I_{i+1,2j}|\big |\le 1$ for all $0\le i\lt s$ and $1\le j\le 2^i$ , by definition of $s$ each $I_{s-1,\ell }$ , for $\ell \in [2^{s-1}]$ , is either a singleton or contains exactly $2$ elements.

Set $V_{0,1}=V(G)\setminus \{v_0,v_1,\ldots, v_d\}$ . Iteratively, for $0\le i\lt s$ and $1\le j\le 2^i$ , partition $V_{i,j}$ uniformly at random into sets $V_{i+1,2j-1}$ and $V_{i+1,2j}$ such that

\begin{equation*}|V_{i+1,2j-1}|=\sum _{\ell \in I_{i+1,2j-1}}m_\ell \quad \text {and}\quad |V_{i+1,2j}|=\sum _{\ell ^{\prime}\in I_{i+1,2j}}m_{\ell ^{\prime}}.\end{equation*}

This is possible as $I_{i,j}=I_{i+1,2j-1}\cup I_{i+1,2j}$ and $|V_{i,j}|=\sum _{\ell \in I_{i,j}}m_\ell$ . Let $J\subset [2^{s-1}]$ be the set of those indices $j\in [2^{s-1}]$ such that $I_{s-1,j}$ is a singleton. Let $t=|J|$ and note that $0\le t\lt 2^{s-1}$ , as $2^{s-1}\lt d\le 2^s$ . After relabelling the indices, we may assume that $[2^{s-1}]\setminus J=[2^{s-1}-t]$ . At step $s$ , for each $1\le j\le 2^{s-1}-t$ we partition $V_{s-1,j}$ uniformly at random into sets $V_{s,2j-1}$ and $V_{s,2j}$ such that $\big ||V_{s,2j-1}|-|V_{s,2j}|\big |\le 1$ , and, noting that $d=2^s-t$ , for each $2^{s-1}-t\lt j^{\prime}\le 2^{s-1}$ we set $V_{s,2^{s-1}-t+j^{\prime}}=V_{s-1,j^{\prime}}$ . For $0\le i\lt s$ and $1\le j\le 2^i$ , let $\mathbf{Y}_{i,j}$ denote the event where the following three properties hold:

1. A1 $\delta (G[V_{i,j}])\ge (\alpha -2|V_{i,j}|^{-1/4})|V_{i,j}|$ .

2. A2 $d(v_0,V_{i,j})\ge (\alpha -2|V_{i,j}|^{-1/4})|V_{i,j}|$ .

3. A3 $d(v_\ell, V_{i,j})\ge (\alpha -2|V_{i,j}|^{-1/4})|V_{i,j}|$ for all $\ell \in I_{i,j}$ .

For $j\in [d]$ , let $\mathbf{Y}_{s,j}$ denote the event where A1, A2 and the following hold:

1. A4 $d(v_j,V_{s,j})\ge (\alpha -2|V_{s,j}|^{-1/4})|V_{s,j}|$ .

For $0\le i\le s$ , let $\mathbf{Y}_{i}$ be the event where $\mathbf{Y}_{i,j}$ holds for all $1\le j\le \min \{2^{i},d\}$ .

Proof of Claim 2.5 . Let $1\le i\lt s$ and suppose that we have chosen our partition $V(G)=\bigcup _{j\in [2^{i-1}]}V_{i-1,j}$ for which $\mathbf{Y}_{i-1}$ holds. In what follows, all probabilities and expectations are conditioned on $\mathbf{Y}_{i-1}$ . Let $1\le j\le 2^{i-1}$ . For a vertex $v\in V_{i-1,j}$ , observe that $d(v,V_{i,2j})$ follows a hypergeometric distribution with parameters $N^{\prime}=|V_{i-1,j}|$ , $n^{\prime}=|V_{i,2j}|$ and $m^{\prime}=d(v,V_{i-1,j})$ . Then, assuming $\mathbf{Y}_{i-1}$ and hence $\mathbf{Y}_{i-1,j}$ , from A1 we deduce that

\begin{equation*}\mathbb E[d(v,V_{i,2j})]\ge (\alpha -2|V_{i-1,j}|^{-1/4})|V_{i,2j}|\end{equation*}

and thus, from Lemma 2.1,

(1) \begin{equation} \mathbb P\left (d(v,V_{i,2j})\le (\alpha -2|V_{i-1,j}|^{-1/4})|V_{i,2j}|-|V_{i,2j}|^{2/3}\right )\le 2 \exp (\!-2|V_{i,2j}|^{1/3}). \end{equation}

On the other hand, using that $|V_{i,2j}|\le \frac{11}{20}|V_{i-1,j}|$ , we have

(2) \begin{equation} 2|V_{i-1,j}|^{-1/4}\cdot |V_{i,2j}|+|V_{i,2j}|^{2/3}\le 2\cdot \left (\tfrac{11}{20}\right )^{1/4}|V_{i,2j}|^{3/4}+\tfrac{1}{10}|V_{i,2j}|^{3/4}\le 2|V_{i,2j}|^{3/4}, \end{equation}

where we have used that $|V_{i,2j}|\ge C-2$ and $1/C\ll 1$ . Combining (1) and (2), we finally have

\begin{equation*}\mathbb P\left (d(v,V_{i,2j})\le (\alpha -2|V_{i,2j}|^{-1/4})|V_{i,2j}|\right )\le 2\exp (\!-2|V_{i,2j}|^{1/3}). \end{equation*}

Using the union bound over all $v\in V_{i-1,j}$ , it follows that A1 holds for $i$ and $2j$ with probability at least

(3) \begin{equation} 1-2|V_{i-1,j}|\cdot \exp (\!-2|V_{i,2j}|^{1/3})\ge 1-2|V_{i-1,j}|\cdot \exp (\!-|V_{i-1,j}|^{1/3}), \end{equation}

where we have used that $2|V_{i,2j}|^{1/3}\ge 2\cdot \left (\tfrac{9}{20}\right )^{1/3}|V_{i-1,j}|^{1/3}\ge |V_{i-1,j}|^{1/3}$ . Similar calculations show that A2 and A3 hold with probability at least (3), and clearly the same conclusions hold for $2j-1$ . Therefore, the probability that $\mathbf{Y}_{i,2j-1}$ and $\mathbf{Y}_{i,2j}$ hold, given a partition $V(G)=\bigcup _{j\in [2^{i-1}]}V_{i-1,j}$ for which $\mathbf{Y}_{i-1,j}$ holds, is at least

(4) \begin{equation} 1-12|V_{i-1,j}|\cdot \exp (\!-|V_{i-1,j}|^{1/3}). \end{equation}

Finally, using that the events $(\mathbf{Y}_{i,2j-1}\wedge \mathbf{Y}_{i,2j})_{1\le j\le 2^{i-1}}$ are mutually independent given a partition $V(G)=V_{i-1,1}\cup \ldots \cup V_{i-1,2^{i-1}}$ for which $\mathbf{Y}_{i-1}$ holds, we can compute

\begin{align*} \mathbb P(\mathbf{Y}_i\mid \mathbf{Y}_{i-1}) &\overset{(2.4)}{\ge } \prod _{j=1}^{2^{i-1}}(1-12 |V_{i-1,j}|\cdot \exp (\!-|V_{i-1,j}|^{1/3}) \\ &\ge \prod _{j=1}^{2^{i-1}}\exp (\!-24|V_{i-1,j}|\cdot \exp (\!-|V_{i-1,j}|^{1/3})) \ge \exp (\!-2^{i-1}), \end{align*}

where we have used that $e^{-2x}\le 1-x$ holds for all $0\lt x\le \frac{1}{2}$ and that $|V_{i-1,j}|\cdot \exp (\!-|V_{i-1,j}|^{1/3})\ll 1$ as $|V_{i-1,j}|\ge C-2$ and $1/C\ll 1$ . Similar arguments show that $\mathbb{P}(\mathbf{Y}_s\mid \mathbf{Y}_{s-1})\ge \exp (\!-2^{s-1})$ .

Proof of Theorem 1.3 . We start by picking a constant $1/C_0\ll \varepsilon$ and let $C\ge C_0$ and $n\ge 2$ . Let $\log n\le d\lt n$ and let $H$ be a $d$ -regular graph with vertex set $V(H)=[n]$ . Given a graph $G$ with $N=Cdn$ vertices and minimum degree $\delta (G)\ge (1+\varepsilon )N/2$ , we now find a partition of $V(G)$ which will be used as a template to embed the $H$ -subdivision.

Proof of Claim 2.7 . Use Lemma 2.3, with parameter $\delta =\varepsilon/2$ , to find an $\left(H,\frac{1}{2}+\frac{\varepsilon }{2}\right)$ -good partition $V(G)=\bigcup _{i\in [n]}V_{i}$ such that

1. (i) $|V_{i}|=Cd$ for all $i\in [n]$ ,

2. (ii) $\delta (G[V_i])\ge (1+\tfrac{\varepsilon }{2})\frac{Cd}{2}$ , and

3. (iii) $\delta (G[V_i,V_j])\ge (1+\tfrac{\varepsilon }{2})\frac{Cd}{2}$ for all $ij\in E(H)$ .

Figure 1.

Creating the $v_i,v_j$ -path $Q_{ij}$ .

Then, for each $ij\in E(H)$ pick vertices $v_{i,j}\in V_i$ and $v_{j,i}\in V_j$ such that $v_{i,j}v_{j,i}\in E(G)$ , and, for $i\in [n]$ , pick an arbitrary vertex $v_i\in V_i$ , choosing new vertices at each time. For each $i\in [n]$ , use Lemma 2.4, with parameter $\delta =\varepsilon/4$ , to find a partition $V_i=\{v_i\}\cup \{v_{i,j}:j\in N_H(i)\}\cup \bigcup _{j\in N_H(i)}V_{i,j}^{\prime}$ such that

• • $|V^{\prime}_{i,j}|\in \{C-2,C-1\}$ for all $j\in N_H(i)$ ,

• • $d(v_{i,j},V^{\prime}_{i,j}), d(v_i,V^{\prime}_{i,j})\ge (1+\tfrac{\varepsilon }{4})\frac{|V^{\prime}_{i,j}|}{2}$ , and

• • $\delta (G[V^{\prime}_{i,j}])\ge (1+\tfrac{\varepsilon }{4})\frac{|V^{\prime}_{i,j}|}{2}$ .

Finally, for each $i\in [n]$ and $j\in N_H(i)$ , we set $V_{i,j}=V_{i,j}^{\prime}\cup \{v_i,v_{i,j}\}$ , which clearly satisfies B1–B6.