Proof. The first equation ?? follows immediately from Theorems 6 and 8, while ?? follows from Theorems 7, 8 and the additional observation that \(h(T)w(T)\geq t\). ◻

Proof. For \(m,t\in \mathbb{N}\), \(S\subset [t]\) and \(u\in S\) let \(\mathcal{D}_m(S;u)\) be the set of trees on \(S\) rooted at \(u\) whose height is at least \(m-1\). For \(v\in [t]\setminus S\) and a rooted tree \(T_v\in \mathcal{D}_m(S,v)\), we write \(T_u+T_v\) for the tree on \([t]\) with edge set \(E(T_u)\cup E(T_v)\cup \{uv\}\). Note that \(uv\) is an \(m\)-centred edge of \(T_u+T_v\) so that \((uv,T_u+T_v)\in \mathcal{M}(t,m)\). Thus the following map is well-defined. \[\begin{align} \phi\colon \bigcup_{\substack{S\subset [t]\\ u\in S\\ v\in [t]\setminus S}} \mathcal{D}_m(S;u)\times \mathcal{D}_m([t]\setminus S;v) &\rightarrow \mathcal{M}(t,m) & (T_u,T_v) &\mapsto (uv,T_u + T_v). \end{align}\] For each \((uv,T)\in \mathcal{M}(t,m)\), if \(T_u\) and \(T_v\) are the components of \(T-uv\) rooted at \(u\) and \(v\), respectively, then \(\phi^{-1}(uv,T)=\{(T_u,T_v),(T_v,T_u)\}\). Thus, the domain of \(\phi\) is exactly twice as large as its codomain \(\mathcal{M}(t,m)\), and since \(\mathcal{D}_m(S;u)\) is empty unless \(\vert S\vert \geq m\), we have \[\begin{align} \label{eq:midpath-bound1} \vert \mathcal{M}(t,m)\vert &= \frac{1}{2}\sum_{k=m}^{t-m} \sum_{\substack{S\in [t]^{(k)}\\ u\in S\\ v\in [t]\setminus S}} \vert \mathcal{D}_m(S;u)\vert \cdot \vert \mathcal{D}_m([t]\setminus S;v)\vert\nonumber\\ &=\frac{1}{2}\sum_{k=m}^{t-m} \binom{t}{k}k(t-k) \vert \mathcal{D}_m([k];1)\vert \cdot \vert \mathcal{D}_m([t-k];1)\vert. \end{align}\tag{3}\] To bound this quantity from above, note that since there are exactly \(k^{k-2}\) trees on \([k]\) overall, we may infer from 4 that \[\begin{align} \vert \mathcal{D}_m([k];1)\vert \ll k^{k-2}e^{-cm^2/k}. \end{align}\] Inserting this into 3 , we find that \[\begin{align} \vert \mathcal{M}(t,m)\vert &\ll \sum_{k=m}^{t-m} \binom{t}{k}k^{k-1}(t-k)^{t-k-1} e^{-cm^2(1/k+1/(t-k))}\\ &\ll \sum_{k=m}^{t/2} \binom{t}{k}k^{k-1}(t-k)^{t-k-1} e^{-cm^2/k}\\ &=\sum_{k=m}^{t/2} \frac{t!k^{k-1}(t-k)^{t-k-1}}{k!(t-k)!} e^{-cm^2/k}. \end{align}\] By Stirling’s formula (1), this can be bounded as \[\begin{align} \vert \mathcal{M}(t,m)\vert &\ll \sum_{k=m}^{t/2} \frac{t^{t+1/2}}{k^{3/2}(t-k)^{3/2}} e^{-cm^2/k}\ll t^{t-1}\sum_{k=m}^{t/2} k^{-3/2} e^{-cm^2/k}, \end{align}\] as desired.

To bound \(\vert \mathcal{M}(t,m)\vert\) from below, we observe that by 4, \[\begin{align} \vert \mathcal{D}_m([k];1) \vert \geq k^{k-2} (1-Ce^{-ck/m^2}). \end{align}\] In particular, there exists a constant \(c_2\) such that \(\vert \mathcal{D}_m([k];1) \vert \geq k^{k-2}/2\) when \(k>c_2 m^2\). Therefore, we deduce from 3 that \[\begin{align} \vert \mathcal{M}(t,m)\vert \gg \sum_{k=c_2 m^2}^{t/2} \binom{t}{k}k^{k-1}(t-k)^{t-k-1}. \end{align}\] As before, it follows from Stirling’s formula that \[\begin{align} \vert \mathcal{M}(t,m)\vert &\gg t^{t-1}\sum_{k=c_2 m^2}^{t/2} k^{-3/2}. \qedhere \end{align}\] ◻

Proof of 3. For every \(\varepsilon>0\), there exists a unique \(\mu=\mu(\varepsilon)\in (0,1)\) such that \(\mu e^{-\mu}=(1+\varepsilon)e^{-(1+\varepsilon)}\). We choose \(\varepsilon_0\) such that for all \(\varepsilon<\varepsilon_0\), we have \(1-\mu(\varepsilon)>\varepsilon/2\) and \(1+\varepsilon\leq e^{\varepsilon- \frac{\varepsilon^2}{3}}\). Let \(\delta\in (0,1]\) and \(\varepsilon\in (0,\varepsilon_0)\).

As a path of length \(m\) consists of \(m-1\) edges and \(m\) vertices, it is equivalent to show that whp any set of vertex-disjoint paths of lengths at least \(\ell=\frac{\delta}{\varepsilon}\) covers at most \(D\varepsilon^2 \delta^{-2} n\) edges, for some absolute constant \(D > 0\). Note that the claim is trivial if \(\ell<100\) so that we may assume that \(\ell\geq 100\). Here and throughout the proof, we ignore rounding unless it is critical to the correctness of the proof.

Let \(\mathcal{C}_1\) be the largest connected component of \(G\), let \(\mathcal{C}^{(2)}_1\) be the \(2\)-core of \(\mathcal{C}_1\), and let \(\mathcal{C}_1 \setminus \mathcal{C}^{(2)}_1\) be the graph obtained from \(\mathcal{C}_1\) by deleting the edges of \(\mathcal{C}^{(2)}_1\). Furthermore, we define the following random variables:

• Let \(X_{\ell}\) be the maximum number of edges covered by vertex-disjoint paths of length at least \(\ell\) in components of \(G\) of size at most \(20 \log n/\varepsilon^2\).

• Let \(Y_{\ell}\) be the maximum number of edges covered by vertex-disjoint paths of length at least \(\ell\) in \(\mathcal{C}_1\).

• Let \(Z_{\ell}\) be the maximum number of edges covered by vertex-disjoint paths of length at least \(\ell/3\) in \(\mathcal{C}_1 \setminus \mathcal{C}^{(2)}_1\).

By 3(b), we have that whp the number of edges of \(G\) covered by vertex-disjoint paths of length at least \(\ell\) is at most \(X_{\ell}+Y_{\ell}\). As in ferber-2017?, a simple counting argument shows that \(Y_{\ell} \leq 6|\mathcal{C}^{(2)}_1|+6Z_{\ell}\), and hence by 3(c), we have whp \(Y_{\ell} \leq 12 \varepsilon^2 n+6Z_{\ell}\). Therefore, to finish the proof, it suffices to prove that whp we have \(X_{\ell} \ll \varepsilon^2\delta^{-2} n\) and \(Z_\ell \ll \varepsilon^2\delta^{-2} n\). We start by proving that \(X_{\ell} \ll \varepsilon^2 \delta^{-2} n\) whp.

Let \(S\subset [n]\) and set \(m=\ell/3\). We define a random variable \(X_S\) whose value depends on a case distinction. If \(G[S]\) is connected and there are no edges between \(S\) and \([n]\setminus S\), then \(X_S\) is defined as the number of edges in \(G[S]\) that are \(m\)-centred. If either condition is not satisfied, we define \(X_S\) to be 0. Observe next that if \(G[S]\) is connected and \(e\) is an \(m\)-centred edge in \(G[S]\), then \(G[S]\) has a spanning tree \(T\) such that \(e\) is also \(m\)-centred in \(T\). Therefore, we have \[\begin{align} \label{eq:BoundFixedSTriples} \mathbb{E}[X_S] \leq |\mathcal{M}(t,m)|p^{t-1} (1-p)^{t(n-t)}. \end{align}\tag{4}\] Indeed, \(|\mathcal{M}(t,m)|\) counts the number of pairs \((e,T)\) such that \(T\) is a spanning tree on \(S\) and \(e\) is \(m\)-centred in \(T\), \(p^{t-1}\) is the probability that \(T\subset G[S]\), and \((1-p)^{t(n-t)}\) is the probability that there are no edges between \(S\) and \([n]\setminus S\). Since \(X_\ell\) is bounded by the sum of all \(X_S\) for which \(S\subset [n]\) has size between \(m\) and \(20\log n/\varepsilon^2\), inserting the upper bound from 7 into 4 , yields \[\begin{align} \mathbb{E}[X_{\ell}] &\ll \sum_{t=m}^{\frac{20}{\varepsilon^2} \log n} \binom{n}{t} \sum_{k=m}^{t/2} t^{t-1}k^{-3/2} e^{-c\frac{m^2}{k}} p^{t-1} (1-p)^{t(n-t)} \\ &\ll \sum_{t=m}^{\frac{20}{\varepsilon^2} \log n} \frac{n!}{t!(n-t)!} \sum_{k=m}^{t/2} t^{t-1}k^{-3/2} e^{-c\frac{m^2}{k}} \frac{e^{\varepsilon(t-1)}}{n^{t-1}} e^{-\frac{1+\varepsilon}{n}t(n-t)}. \end{align}\] Simplifying and applying 1, we obtain \[\begin{align} \label{eq:proof1} \mathbb{E}[X_{\ell}] &\ll n \sum_{t=m}^{\frac{20}{\varepsilon^2} \log n} \frac{n^{n-t+1/2}}{t^{t+1/2}(n-t)^{n-t+1/2}} \sum_{k=m}^{t/2} t^{t-1}k^{-3/2} e^{-c\frac{m^2}{k}} e^{-t}. \end{align}\tag{5}\] Moreover, we have \[\begin{align} \label{eq:proof2} \frac{n^{n-t+1/2}}{(n-t)^{n-t+1/2}} = \frac{1}{(1-t/n)^{n-t+1/2}} = e^{t+O(\frac{t^2}{n})} \ll e^{t}. \end{align}\tag{6}\] Inserting 6 into 5 , we obtain \[\begin{align} \mathbb{E}[X_{\ell}] &\ll n \sum_{t=m}^{\frac{20}{\varepsilon^2} \log n} \sum_{k=m}^{t/2} k^{-3/2}t^{-3/2} e^{-c\frac{m^2}{k}} \\ &\ll n \sum_{t=m}^{\infty} \sum_{k=m}^{t/2} k^{-3/2}t^{-3/2} e^{-c\frac{m^2}{k}} \\ &\ll n \sum_{t=m}^{\infty} t^{-3/2} \int_{m}^{t/2} k^{-3/2}e^{-c\frac{m^2}{k}} \mathrm{d}k, \end{align}\] where the integral comparison that yields the last inequality is valid because the integrand is positive and for all \(x,y\geq m \geq 1\) such that \(\vert x-y\vert \leq 1\), we have \[\frac{x^{-3/2}e^{-c\frac{m^2}{x}}}{y^{-3/2}e^{-c\frac{m^2}{y}}}=\left(\frac{y}{x}\right)^{3/2}e^{c\left( \frac{m^2}{y}-\frac{m^2}{x} \right)}\leq 2^{3/2} e^{c}.\] Performing the substitution \(k={m}^2/x^2\), we obtain \[\begin{align} \mathbb{E}[X_{\ell}] &\ll n{m}^{-1} \sum_{t=m}^{\infty} t^{-3/2} \int_{\sqrt{\frac{2}{t}}m}^{\sqrt{m}} e^{-cx^2} \mathrm{d}x \\ &\ll n{m}^{-1} \sum_{t=m}^{\infty} t^{-3/2} \int_{0}^{\sqrt{m}} \mathbb{1}_{x \geq \sqrt{\frac{2}{t}}m} e^{-cx^2} \mathrm{d}x\\ &\ll n{m}^{-1} \int_{0}^{\sqrt{m}} e^{-cx^2}\sum_{t=\max(2m^2/x^2, m)}^{\infty} t^{-3/2} \mathrm{d}x\\ &\ll n{m}^{-1} \int_{x=0}^{\sqrt{m}} e^{-cx^2} \int_{t=2m^2/x^2}^{\infty} t^{-3/2} \mathrm{d}t \mathrm{d}x \\ &\ll n{m}^{-1} \int_{x=0}^{\sqrt{m}} e^{-cx^2} (2m^2/x^2)^{-1/2} \mathrm{d}x \\ &\ll n{m}^{-2} \int_{0}^{\infty} xe^{-cx^2} \mathrm{d}x. \end{align}\] Since the moments of a Gaussian random variable exist and are finite, we may insert the value of \(m\) to obtain \(\mathbb{E}[X_{\ell}] \ll n \varepsilon^2\delta^{-2}\). An application of 2 gives the desired conclusion.
We now move on to bounding \(Z_\ell\). Let \(0 < \mu <1\) be such that \(\mu e^{-\mu}=(1+\varepsilon)e^{-(1+\varepsilon)}\) and consider \(2 \varepsilon^2 n\) independent Poisson(\(\mu\))-Galton-Watson trees \(T_1, \dots, T_{2\varepsilon^2 n}\). By 6, to prove that \(Z_\ell \ll \varepsilon^2 \delta^{-2} n\) whp, it is enough to show that \(M_\ell\), the number of edges that can be covered by vertex-disjoint paths in \(T_1\cup \ldots \cup T_{2\varepsilon^2 n}\) of length at least \(\ell/3\), satisfies \(M_\ell\ll \varepsilon^2 \delta^{-2} n\) whp.

To bound \(M_\ell\), we employ the second moment method, as was done in ferber-2017?. However, 7 will allow us to obtain better bounds once more. Set \(m=\ell/9\) and let \(T\) be a Poisson(\(\mu\))-Galton-Watson tree and let \(S_\ell\) be the number of \(m\)-centred edges in \(T\). Thus, \(\mathbb{E}[M_\ell]\leq 6\varepsilon^2n \mathbb{E}[S_\ell]\). It is clear that \[\begin{align} \mathbb{E}[S_{\ell}] &\leq 3\sum_{t \geq m} \mathbb{P}(|T|=t)|\frac{|\mathcal{M}(t,m)|}{t^{t-2}}. \end{align}\] Inserting [lem:distrib-Poisson-GW,lem:Counting-lemma] into the above, we obtain \[\begin{align} \mathbb{E}[S_{\ell}] &\ll \sum_{t \geq m} \frac{1}{t^{t-2}} \frac{t^{t-1}(\mu e^{-\mu})^t}{\mu t!} \sum_{k=m}^{t/2} t^{t-1}k^{-3/2} e^{-c\frac{m^2}{k}} \\ &\ll \sum_{t \geq m} \frac{t (1+\varepsilon)^te^{-(1+\varepsilon)t}}{t!} \sum_{k=m}^{t/2} t^{t-1}k^{-3/2} e^{-c\frac{m^2}{k}}. \end{align}\] Using that \((1+\varepsilon)^t \leq e^{\varepsilon t- \frac{\varepsilon^2}{3}t}\) and 1, we have \[\begin{align} \mathbb{E}[S_{\ell}] &\ll \sum_{t \geq m} \sum_{k=m}^{t/2} k^{-3/2}t^{-1/2} e^{-\frac{\varepsilon^2}{3}t} e^{-c\frac{m^2}{k}} \\ &\ll \sum_{t \geq m} e^{-\frac{\varepsilon^2}{3}t} t^{-1/2} \int_{k=m}^{t/2} k^{-3/2}e^{-c\frac{m^2}{k}}\mathrm{d}k. \end{align}\] As for the computation of \(\mathbb{E}[X_{\ell}]\), we substitute \(k={m}^2/x^2\) in the integral to obtain \[\begin{align} \mathbb{E}[S_{\ell}] &\ll {m}^{-1} \sum_{t=m}^{\infty} e^{-\frac{\varepsilon^2}{3}t} t^{-1/2} \int_{\sqrt{\frac{2}{t}}m}^{\sqrt{m}} e^{-cx^2} \mathrm{d}x \\ &\ll {m}^{-1} \sum_{t=m}^{\infty} \int_{x=\sqrt{\frac{2}{t}}m}^{\sqrt{m}} \mathbb{1}_{x \geq \sqrt{\frac{2}{t}}m} e^{-\frac{\varepsilon^2}{3}t} t^{-1/2} e^{-cx^2} \mathrm{d}x \\ &\ll {m}^{-1} \int_{x=0}^{\sqrt{m}} e^{-cx^2} \sum_{t=2{m}^2/x^2}^{\infty} e^{-\frac{\varepsilon^2}{3}t} t^{-1/2} \mathrm{d}x \\ &\ll {m}^{-1} \int_{x=0}^{\sqrt{m}} e^{-cx^2} \int_{t=2{m}^2/x^2}^{\infty} e^{-\frac{\varepsilon^2}{3}t} t^{-1/2} \mathrm{d}t \mathrm{d}x. \end{align}\] Performing the second substitution \(t=y^2/\varepsilon^2\) in the integral, we obtain \[\begin{align} \mathbb{E}[S_{\ell}] &\ll {m}^{-1} \int_{x=0}^{\sqrt{m}} e^{-cx^2} \int_{y=\sqrt{2}m \varepsilon/x}^{\infty} \frac{e^{-\frac{y^2}{3}}}{\varepsilon} \mathrm{d}y \mathrm{d}x \\ &\ll \delta^{-1} \int_{x=0}^{\infty} e^{-cx^2} \int_{y=0}^{\infty} e^{-\frac{y^2}{3}} \mathrm{d}y \mathrm{d}x \\ &\ll \delta^{-1}, \end{align}\] showing that \(\mathbb{E}[M_\ell]\ll \varepsilon^2\delta^{-1}n\).

For the second moment, we use the same computation as ferber-2017?. Using 5, which specifies the distribution of \(\vert T\vert\), we can calculate that \(\mathbb{E}[\vert T\vert^2]=(1-\mu)^{-3}\). Thus, \[\begin{align} \mathop{\mathrm{Var}}[M_{\ell}] \leq 18\varepsilon^2 n \mathbb{E}[S^2_{\ell}] \leq 18\varepsilon^2 n\mathbb{E}[|T|^2] =\frac{18\varepsilon^2 n}{(1-\mu)^3} \leq \frac{144n}{\varepsilon}, \end{align}\] where the last inequality follows from \(1-\mu \geq \frac{\varepsilon}{2}\). Since \(\mathbb{E}[M_\ell]\ll \varepsilon^2\delta^{-1}n\) and \(\mathop{\mathrm{Var}}[M_{\ell}] \ll n\varepsilon^{-1}\) as well, it follows from Chebyshev’s inequality that \(M_{\ell} \ll \varepsilon^2 \delta^{-1} n\) whp, as desired. ◻

Proof. For a tree \(T\) on \([t]\) and \(m\leq t\), let \(X_m(T)\) be the number of pairs \((e,T)\) in \(\mathcal{M}(t,m)\), i.e., the number of \(m\)-centred edges in \(T\). Recall that by 1 , we have \(\mathrm{cov}_{3m}(T)\leq 3X_m(T)\), while by 2 , we have \(X_\ell(T)\leq \mathrm{cov}_\ell(T)\). Observe further that since \(\mathrm{cov}_{\ell'}(T)\leq \mathrm{cov}_\ell(T)\) for \(\ell'>\ell\), it is enough to show the upper bound in the claim when \(\ell\) is divisible by three. Thus, to prove the claim, it suffices to show that \(\mathbb{E}[X_m]=O(t/m)\) for \(1\leq m\leq t\), and that there exists \(c>0\) such that \(\mathbb{E}[X_m]=\Omega(t/m)\) for \(1\leq m \leq c\sqrt{t}\).

To bound \(\mathbb{E}[X_m]\) from above, we make similar calculations to those in the proof of 3. By 7, we have \[\begin{align} \mathbb{E}[X_m(T)] &\ll t\sum_{k=m}^{t/2} k^{-3/2} e^{-c\frac{t^2}{k}} \ll t\int_m^{t/2} k^{-3/2} e^{-c\frac{t^2}{k}} \mathrm{d}k \ll t\int_m^{t/2} k^{-3/2} e^{-c\frac{m^2}{k}} \mathrm{d}k. \end{align}\] By substituting \(k=m^2/x^2\), we obtain \[\begin{align} \mathbb{E}[X_m(T)] &\ll \frac{t}{m}\int_{m/\sqrt{t}}^{\sqrt{m}} e^{-cx^2} \mathrm{d}x\ll\frac{t}{m}, \end{align}\] as desired.

It remains to bound \(\mathbb{E}[X_m(T)]\) from below. By the lower bound in 7, there exists a constant \(c_2\) such that \[\begin{align} \mathbb{E}[X_m(T)] \gg t\sum_{k=c_2\ell^2}^{t/2} k^{-3/2}. \end{align}\] Assuming that \(c_2m^2<t/4\), this gives \[\begin{align} \mathbb{E}[X_m(T)] \gg t \int_{c_2 m^2}^{t/2} k^{-3/2} \mathrm{d}k \gg \frac{t}{\sqrt{c_2 m^2}}-\frac{t}{\sqrt{t/2}} \gg \frac{t}{m}, \end{align}\] as desired. ◻

Proof of 5. For \(v\in [t-1]\) let \(\Omega_v=[t]\) and consider the product space \(\Omega=\prod_{v=1}^{t-1} \Omega_v\) with uniform probability measure \(\mathbb{P}_\omega\). Each element \(\omega\in \Omega\) can be associated with a graph with vertex set \([t]\) and edge set \(\{uv:\omega_u=v\lor \omega_v=u\}\). In particular, each tree \(T\) on \([t]\) is associated with the unique element \(\omega\in \Omega\) for which \(\omega_v\) is the first vertex on the path from \(v\) to \(t\). For \(\omega\in \Omega\), we define \(\mathrm{cov}_\ell(\omega)\) as \(\mathrm{cov}_\ell(G_\omega)\) for the unique graph \(G_\omega\) associated with \(\omega\).

Observe that the random variable \(\omega \mapsto \mathrm{cov}_\ell(G_\omega)\) is \(2\ell\)-Lipschitz. Furthermore, if \(G_\omega\) has a system of vertex-disjoint paths of length at least \(\ell\) that cover \(m\) vertices, then the \(m-1\) edges of this path system certify that \(\mathrm{cov}_\ell(G_\omega)\geq m\). Hence, \(\mathrm{cov}_\ell\) is \(f\)-certifiable for \(f(s)=s-1\). Therefore, we may apply 9 to see that for any \(\alpha,\mu >0\), \[\begin{align} \mathbb{P}_\omega\left(\mathrm{cov}_\ell(G_\omega)\leq \mu - \alpha\ell\sqrt{\mu}\right) \mathbb{P}_\omega(\mathrm{cov}_\ell(G_\omega)\geq \mu)\leq e^{-\alpha^2/4}. \end{align}\] Since the size of \(\Omega\) is \(t^{t-1}\) and there are \(t^{t-2}\) trees on \([t]\), the set \(\{\omega:G_\omega \text{ is a tree}\}\) has density \(1/t\) in \(\Omega\), it follows that for the uniform probability measure \(\mathbb{P}_T\) over all trees on \([t]\), we have \[\label{eq:packing-talagrand} \mathbb{P}_T\left(\mathrm{cov}_\ell(T)\leq \mu - \alpha\sqrt{\ell^2 \mu}\right) \mathbb{P}_T(\mathrm{cov}_\ell(T)\geq \mu)\leq t^2e^{-\alpha^2/4}.\tag{7}\] Let \(\delta\in (0,1)\). By 10, there exists \(c>0\) such that \(\mathbb{E}_T[\mathrm{cov}_\ell(T)]\geq ct/\ell\), independently of \(t\) as long as \(\ell\ll c\sqrt{t}\). Thus, to bound \(\mathbb{P}_T(\mathrm{cov}_\ell(T)\geq (1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)])\), we may apply 7 with \(\mu=(1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)]\) and \[\alpha=\frac{\delta}{4}\sqrt{\frac{\mathbb{E}_T[\mathrm{cov}_\ell(T)]}{\ell^2}}\geq \frac{\delta}{4}\sqrt{\frac{ct}{\ell^3}},\] so that \[\mu-\alpha\sqrt{\ell^2\mu}=(1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)]-\frac{\delta}{4}\sqrt{(1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)]^2}\geq (1+\delta/2)\mathbb{E}_T[\mathrm{cov}_\ell(T)].\] Inserting this into 7 , we obtain \[\mathbb{P}_T(\mathrm{cov}_\ell(T)\geq (1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)])\leq \frac{t^2e^{-\frac{ct\delta^2}{64\ell^3}}}{\mathbb{P}_T\left(\mathrm{cov}_\ell(T)\leq (1+\delta/2)\mathbb{E}_T[\mathrm{cov}_\ell(T)]\right)}.\] By Markov’s inequality, the denominator is at least \(1-1/(1+\delta/2)\geq \delta/3\) so that \[\label{eq:concentration-upper} \mathbb{P}_T(\mathrm{cov}_\ell(T)\geq (1+\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)])\leq \frac{3t^2e^{-\frac{ct\delta^2}{64\ell^3}}}{\delta}.\tag{8}\]

On the other hand, if we let \(\mu=\mathbb{E}_T[\mathrm{cov}_\ell(T)]\) and \(\alpha=\delta\sqrt{ct/\ell^3}\) and denote \(\mathbb{P}_T(\mathrm{cov}_\ell(T)<(1-\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)])\) by \(q_\delta\), then \[\mathbb{P}_T(\mathrm{cov}_\ell(T)\geq \mathbb{E}_T[\mathrm{cov}_\ell(T)])\leq t^2q_\delta^{-1}e^{-\frac{ct\delta^2}{\ell^3}}.\] Since \(\mathrm{cov}_\ell(T)\) is bounded by \(t\), \(\mathbb{E}_T[\mathrm{cov}_\ell(T)]\) can be bounded as \[\begin{align} \mathbb{E}_T[\mathrm{cov}_\ell(T)]&\leq q_\delta(1-\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)]+(1-q_\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)]+\mathbb{P}_T(\mathrm{cov}_\ell(T) > \mathbb{E}_T[\mathrm{cov}_\ell(T)])t\\ &\leq (1-q_\delta\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)] + t^3q_\delta^{-1}e^{-\frac{ct\delta^2}{\ell^3}}, \end{align}\] which implies that \[\label{eq:concentration-lower} \mathbb{P}_T(\mathrm{cov}_\ell(T)<(1-\delta)\mathbb{E}_T[\mathrm{cov}_\ell(T)])=q_\delta \leq \left(\frac{t^3}{\delta\mathbb{E}_T[\mathrm{cov}_\ell(T)]}e^{-\frac{ct\delta^2}{\ell^3}}\right)^{1/2}\leq t\sqrt{\frac{\ell}{c\delta}} e^{-\frac{ct\delta^2}{2\ell^3}}.\tag{9}\] We may now apply a union bound for 8 and 9 , and by renaming the constant \(c\) appropriately, we obtain the claim. ◻

Proof of 2. By 3, there exist \(D>1,\varepsilon_0'>0\) such that for all \(\delta\in (0,1]\) and \(\varepsilon\in (0,\varepsilon_0')\) the following holds. With high probability, \(G\sim G(n,\frac{1+\varepsilon}{n})\) contains no system of vertex-disjoint paths of length at least \(\frac{\delta}{3\varepsilon}\) that covers more than \(D\varepsilon^2 \delta^{-2} n\) vertices.

For \(\delta, q\in (0,1]\), let \(\varepsilon_0\) be the minimum of \(\varepsilon_0'\) and \(\frac{q \delta^2}{192 D}\) and let \(p=\frac{1+\varepsilon}{n}\). Suppose that Alg is an adaptive algorithm that reveals a path of length \(\ell\geq \delta/\varepsilon\) with probability at least \(q\) by querying at most \(\frac{\delta q \ell}{1152 D p \varepsilon}\) pairs of vertices in a graph \(G \sim G(n,p)\).

Let \(n' = (1 + \frac{96 D \varepsilon^2}{q \delta^2})n\), and note that this is at most \((1+\varepsilon/2)n\), as \(\varepsilon\leq \frac{q \delta^2}{192 D}\). Let further \(V_0 = [n']\), \(I_0 = \emptyset\), and \(s = \frac{96 D \varepsilon^2 n}{\delta^2 q (\ell + 1)}\). We will now construct a sequence of sets \(V_0\supset V_1\supset \ldots \supset V_s\) recursively, by repeating the following steps for \(i \in \{1, \ldots, s\}\).

• Sample an injection \(f_i\colon [n]\rightarrow V_{i-1}\) uniformly at random and sample \(G_{i} \sim G(V_{i-1}, p)\). We let \(f_i^{-1}(G_{i})\) denote the graph with vertex set \([n]\) and edge set \(\{uv\in [n]^{(2)}:f(uv)\in E(G_{i})\}\). We run Alg on \(f_i^{-1}(G_i)\), noting that since \(f_i^{-1}(G_i)\sim G(n,p)\), the probability of success is at least \(q\).

• Let \(L_i\) be the graph on \(V_{i-1}\) with edge set \(\{f(uv):uv \text{ was queried by Alg}\}\) (note that \(|E(L_i)| \leq \frac{q \ell \delta}{1152 D p \varepsilon}\)), and let \(K_i \subseteq L_i\) be the intersection of \(L_i\) and \(G_i\).

• If \(K_i\) contains a path of length \(\ell\), then we fix one such path which we call \(P_i\) and let \(V_i = V_{i-1} \setminus V(P_i)\) and \(I_i = I_{i-1} \cup \{i\}\). Otherwise, we let \(V_i = V_{i-1}\) and \(I_i = I_{i-1}\).

Observe that we are indeed able to repeat these steps \(s\) times since for every \(i \in [s]\), \(|V_{i-1}| \geq |V_s| \geq n' - (\ell+1) s = n\).

We now define a graph \(H\) on the vertex set \(V_0\) so that \(\{u,v\} \in E(H)\) if and only if \(\{u,v\} \in E(L_i)\) for some \(i \in [s]\) and for the smallest such \(i_0\) it holds that \(\{u,v\} \in E(K_{i_0})\). For every \(e\in [n']^{(2)}\), we have \[\mathbb{P}(e\in E(H))\leq \frac{1+\varepsilon}{n} = \frac{1+\varepsilon}{n'}+\frac{1+\varepsilon}{n'}\left(\frac{n'}{n}-1\right)\leq \frac{1+2\varepsilon}{n'},\] and while the presence of edges in \(H\) is not necessarily independent, one can check that for any distinct \(e_1,\ldots,e_r\in [n']^{(2)}\), \[\mathbb{P}(e_1,\ldots,e_r \in E(H)) \leq \left(\frac{1+2\varepsilon}{n'}\right)^r.\] Thus, since the property of having a family of vertex-disjoint paths with length at least \(\ell\) that cover \(M\) vertices is monotone for all \(\ell\) and \(M\), the following holds. If \(H\) contains a set of vertex-disjoint paths with length at least \(\frac{\delta}{\varepsilon}\) that cover at least \(4 D \varepsilon^2 \delta^{-2} n' = D (2 \varepsilon)^2 \delta^{-2} n'\) vertices with probability at least \(\frac{q^2}{4}\), the same holds with probability at least \(\frac{q^2}{4}\) for \(G\sim G(n', \frac{1+2\varepsilon}{n'})\).

Thus, it is enough to prove that \(H\) has this property with probability at least \(\frac{q^2}{4}\) since this will then be in contradiction with 3 for sufficiently large \(n\).

For every \(i \in I_s\) let \(H_i\) be the graph on vertices \(V_{i-1}\) with edges \(\left( \bigcup_{j=1}^{i-1} E(L_j) \right) \cap V_{i-1}^{(2)}\). Observe that \[\begin{align} \label{eq:H95i} |E(H_i)| \leq \frac{\varepsilon}{6 \delta} \binom{|V_{i-1}|}{2}. \end{align}\tag{10}\]

By definition, \(V_{i-1} \setminus V_i\) is a path \(P_i\) in \(K_i\) for every \(i \in I_s\). Thus, we can define \(B_i = E(P_i) \cap E(H_i)\) and \(Q_i\) to be the graph obtained from \(P_i\) by deleting all edges in \(B_i\). Clearly, \(E(Q_i) \subseteq E(H)\), and the graphs \(\{Q_i\}_{i \in I_s}\) are vertex-disjoint.

Let \(I = \{i \in I_s : |B_i| \leq \frac{\varepsilon}{ \delta} \ell\}\). Applying 8 with \(\alpha=\delta/\varepsilon\), we get that for every \(i \in I\), there exist vertex-disjoint subpaths \(\{Q_i^j\}_{j\in J_i}\) of \(Q_i\) such that each \(Q_i^j\) has length at least \(\frac{\delta}{3\varepsilon}\) and they cover at least \((\frac{1}{3} - \frac{\varepsilon}{ \delta}) \ell \geq \frac{1}{4} (\ell + 1)\) vertices of \(P_i\), where the last inequality holds since \(\varepsilon<\frac{q \delta^2}{192 D}\), and thus, \(\ell\geq 192\).

If \(|I| \geq \frac{sq}{3}\), then \(\{Q_i^j\}_{j \in J_i}\) is a collection of paths of length at least \(\frac{\delta}{3\varepsilon}\) that cover at least \(\frac{1}{4} (\ell+1) |I| \geq 4 D \varepsilon^2 \delta^{-2} n'\). So it suffices to show that \(|I| \geq \frac{sq}{3}\) with probability at least \(\frac{q^2}{4}\).

Let \(I' = [s] \setminus I\). For every \(i \in [s]\), we have \[\begin{align} \label{eq:I39} \mathbb{P}(i \in I') & = \mathbb{P}(i \notin I_s) + \mathbb{P}\left(i \in I' \mid i \in I_s\right) \mathbb{P}(i \in I_s). \end{align}\tag{11}\] Recall that \(\mathbb{P}(i \in I_s)\) is simply the success probability of Alg, which is at least \(q\). For \(i \in I_s\), consider the random embedding \(f_i\colon [n]\rightarrow V_{i-1}\) that was chosen to pull \(G_i\) back onto \([n]\). Since \(f_i\) was sampled independently from all random variables that determined \(H_i\) and \(P_i\) is the image of a path under \(f_i\), we have by 10 , that \(\mathbb{P}(e \in E(H_i)) \leq \frac{\varepsilon}{6 \delta}\) for every \(e \in E(P_i)\). By the linearity of expectation we have that \(\mathbb{E}[|B_i|] = \mathbb{E}[|E(P_i) \cap E(H_i)|] \leq \frac{\varepsilon}{6 \delta} \ell\). Using Markov’s inequality, we obtain that \[\mathbb{P}(i \in I' \mid i \in I_s) = \mathbb{P}\left(|B_i| \geq \frac{\varepsilon}{\delta} \ell \mid i \in I_s\right) \leq \frac{\mathbb{E}[|B_i| \mid i \in I_s]}{\frac{\varepsilon}{\delta} \ell} \leq \frac{\frac{\varepsilon}{6 \delta} \ell}{\frac{\varepsilon}{\delta} \ell} < \frac{1}{2}.\] Using these inequalities in 11 yields \[\mathbb{P}(i \in I') \leq 1 - \mathbb{P}(i \in I_s) + \frac{1}{2} \mathbb{P}(i \in I_s) = 1 - \frac{1}{2} \mathbb{P}(i \in I_s) \leq 1 - \frac{q}{2}.\]

Linearity of expectation now gives \(\mathbb{E}[|I'|] \leq s (1 - \frac{q}{2})\), and Markov’s inequality implies that \(\mathbb{P}(|I'| \geq \frac{s}{1 + \frac{q}{2}}) \leq 1 - \frac{q^2}{4}\). Therefore, as \(q \in (0,1)\), \[\mathbb{P}(|I| \geq \frac{sq}{3}) \geq \mathbb{P}(|I| \geq \frac{sq}{2+q}) = \mathbb{P}(|I'| \leq s - \frac{sq}{2+q}) = \mathbb{P}(|I'| \leq \frac{s}{1+\frac{q}{2}}) \geq \frac{q^2}{4},\] as desired. ◻