Packing and finding paths in sparse random graphs
Vesna Iršič Julien Portier Leo Versteegen












Packing and finding paths in sparse random graphs
    Vesna Iršič [mailto:vesna.irsic@fmf.uni-lj.sivesna.irsic@fmf.uni-lj.si, Faculty of Mathematics and Physics, University of Ljubljana, Slovenia]
Julien Portier [mailto:jp899@cam.ac.ukjp899@cam.ac.uk, Department of Pure Mathematics and Mathematical Statistics (DPMMS), University of Cambridge, Wilberforce Road, Cambridge, CB3 0WA, United Kingdom]
Leo Versteegen [mailto:lversteegen.math@gmail.comlversteegen.math@gmail.com, Department of Pure Mathematics and Mathematical Statistics (DPMMS), University of Cambridge, Wilberforce Road, Cambridge, CB3 0WA, United Kingdom]
    September 9, 2024
============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




§ ABSTRACT 
Let G∼ G(n,p) be a (hidden) Erdős-Rényi random graph with p=(1+)/n for some fixed constant >0. Ferber, Krivelevich, Sudakov, and Vieira showed that to reveal a path of length ℓ=Ω(log(1/)/) in G with high probability, one must query the adjacency of Ω(ℓ/plog(1/)) pairs of vertices in G, where each query may depend on the outcome of all previous queries. Their result is tight up to the factor of log(1/) in both ℓ and the number of queries, and they conjectured that this factor could be removed. We confirm their conjecture. The main ingredient in our proof is a result about path-packings in random labelled trees of independent interest. Using this, we also give a partial answer to a related question of Ferber, Krivelevich, Sudakov, and Vieira. Namely, we show that when ℓ=o((t/log t)^1/3), the maximum number of vertices covered by edge-disjoint paths of length at least ℓ in a random labelled tree of size t is Θ(t/ℓ) with high probability.


Keywords: Adaptive algorithms, Path-packing, Random graphs, Random trees

AMS Subj. Class. (2020): 05C80, 05C85





§ INTRODUCTION


In the Erdős–Rényi random graph model a graph G ∼ G(n,p) is obtained by independently adding an edge between each pair of n labelled vertices with probability p ∈ [0,1]. We say that an event whose probability depends on n occurs with high probability (or whp for short) if its probability goes to 1 as n goes to infinity.

In the companion papers <cit.> Ferber, Krivelevich, Sudakov, and Vieira introduced the following type of algorithmic problem on Erdős–Rényi random graphs.
Let 𝒫 be an increasing graph property, i.e., a graph property such that when G_1 is a subgraph of G_2 and G_1 has the property 𝒫, then G_2 does as well. Suppose that p=p(n) is chosen such that when G is sampled according to the Erdős-Rényi graph model G(n,p), then G has the property 𝒫 with high probability. 

An adaptive algorithm queries for pairs of vertices in V(G) whether or not they are an edge of G. Each query is allowed to depend on the outcome of previous queries, and the algorithm terminates once the revealed edges witness that G has 𝒫. The principal objective in this setting is to determine the minimum number of queries that an adaptive algorithm requires to terminate with high probability. After the research of adaptive algorithms on random graphs was initiated in  <cit.>, problems of this type were studied in multiple papers, see for instance <cit.>.

If all graphs with property 𝒫 have at least m edges, then it is obvious that one needs to query at least (1+o(1)) m/p pairs of vertices, as the algorithm requires at least m positive responses in order to satisfy the target property.
In <cit.>, where a question of this type appeared implicitly, Krivelevich and Sudakov showed that this trivial lower bound is tight in the supercritical regime if 𝒫 is the property of having a giant component.
More precisely, they showed that there is an adaptive algorithm which finds a connected component of size at least n/2 in G∼ G(n,p) in at most n^2/2 queries with high probability when p=1+/n.
Similarly, Ferber, Krivelevich, Sudakov, and Vieira proved in <cit.> that this trivial lower bound is also tight for the property of having a Hamilton cycle.
They established that when p≥ln n+lnln n+ω(1) there exists an adaptive algorithm that finds a Hamiltonian cycle in G∼ G(n,p) in at most (1+o(1))n/p queries with high probability.
The naive bound, however, is not always tight. In <cit.>, Ferber, Krivelevich, Sudakov, and Vieira showed that if the property of interest is to have a path of length ℓ, then one may need substantially more than ℓ/p queries.



 There exists an absolute constant C >0 such that the following holds. For every
constant q ∈ (0,1), there exists n_0,_0 such that for every fixed ∈ (0, _0) and any n ≥ n_0, there is no adaptive algorithm which reveals a path of length ℓ≥3C/log(1/) with probability at least q in G ∼ G(n,p), where p=1+/n, by quering at most qℓ/8640Cplog(1/) pairs of vertices.


They conjectured that the log(1/) factor in the denominator could be removed, and noticed that this would be optimal, since an argument from <cit.> can be adapted to show that there exists an adaptive algorithm which finds a path of length ℓ≤1/5^2n in G(n,p) when p=1+/n with probability at least 1-exp(-Ω(ℓ/)) in at most O(ℓ/p) queries.
In this paper, we confirm their conjecture in form of the following theorem. 



 For all δ∈ (0,1] and all q ∈ [0,1], there exists n_0∈,_0 >0 such that for every ∈ (0, _0) and any n ≥ n_0 the following holds. Any adaptive algorithm which reveals a path of length ℓ≥δ/ with probability at least q in G ∼ G(n,1+/n) requires Ω(qℓδ/p ) queries. 


We prove <Ref> by making the following improvement on a technical result that is the main ingredient in the proof of <Ref> in <cit.>.


    
    There exists _0>0 such that for all δ∈ (0,1] and ∈ (0, _0), with high probability, the following holds.
    Let S be a set of vertex-disjoint paths in G ∼ G(n,1+/n), each of length at least δ/.
    Then S covers O(^2 δ^-2 n) vertices.


For a graph G and an integer ℓ, let _ℓ(G) denote the maximum number of vertices that can be covered by a system of vertex-disjoint paths of length at least ℓ in G. In <cit.>, it was observed that to estimate _ℓ(G) when G∼ G(n,1+/n) it is actually sufficient to bound _ℓ(T) for a random labelled tree T of any given size t. Somewhat surprisingly, the insight that _ℓ(T)=0 when T does not contain any path of length ℓ, together with the trivial bound _ℓ(T)≤ t for all other trees, is ultimately sufficient to prove <Ref>.

The key ingredient of our improvement is a more sophisticated bound on _ℓ(T) for a typical labelled tree T. We obtain this bound through <Ref> by counting the number of pairs (e,T) such that e is an edge that lies near the centre of a long path of size at least ℓ of a random labelled tree on t vertices.

The deduction of <Ref> from <Ref> proceeds in the same manner as that of <Ref> from the result in <cit.> that is analogous to <Ref>. For completeness, we include this proof in Appendix <ref>.

Having identified the number of paths of length at least ℓ that can be packed into a random labelled tree as useful information for progress on <Ref>, the authors of <cit.> asked the following question, which we believe is of independent interest.


    Given a=a(t) ∈ℕ and b=b(t) ∈ℕ, what is the probability that a random labelled tree on t vertices contains b vertex-disjoint paths, each of length at least a?


Because each path of length longer than 2ℓ may be split into paths of length in [ℓ,2ℓ], the maximum number of vertex-disjoint paths of length at least ℓ in a tree T lies between _ℓ(T)/2ℓ and _ℓ(T)/ℓ. Thus, by our aforementioned result that [_ℓ(T)]=Θ(t/ℓ), the average number of paths of length at least ℓ that can be packed into T is Θ(t/ℓ^2), as long as ℓ=O(√(t)). What is more, if ℓ = o((t/log t)^1/3), we can use Talagrand's inequality to show that _ℓ(T) is tightly concentrated around its mean, thus giving a partial answer to <Ref>. For the avoidance of doubt, the following theorem is phrased in terms of (unlabelled) trees on the fixed vertex set [t] which is conceptually equivalent to labelled trees on t unspecified vertices.



    There exist C_1,C_2>0 such that for all t∈ the following hold. Let T be sampled uniformly at random from all trees on vertex set [t]. For all integers ℓ∈ [1,t], we have [_ℓ(T)]≤C_1t/ℓ, and for all integers ℓ∈ [1,C_2t], we have [_ℓ(T)]≥ C_2t/ℓ.
    
    Furthermore, there exists c>0 such that for all integers ℓ≤ c√(t) and δ∈ (0,1), if T is sampled uniformly at random from all trees on vertex set [t], then we have
    
    _T(|_ℓ(T) - [_ℓ(T)]| > δ t/ℓ)≤ct^2/δ e^cδ^2t/ℓ^3.



The remainder of the paper is structured as follows. In <Ref> we introduce some notation and tools, most of them already appearing in <cit.>. In <Ref> we state and prove the main counting lemma which is the crux of our proofs. In <Ref> we proceed to the proof of <Ref>. In <Ref> we prove <Ref>.





§ PRELIMINARIES




For a positive integer n, let [n] = {1, …, n}, and for a set S, let S^(n) denote the set of all subsets of S of size n. For functions f and g, we denote f ≪ g if and only if there exist constants N, k > 0 such that for every x > N, we have f(x) < k g(x). Note that this is different from the usual use of ≪ when studying random graphs.

We record the following version of Stirling's formula for later use.


    There exists two absolute positive constants K_1 and K_2 such that for every integer N, we have K_1 √(N) (N/e)^N ≥ N! ≥ K_2 √(N) (N/e)^N.


We will make use of the following concentration inequality for the edge exposure martingale in G(n,p) which is an easy consequence of <cit.>.



    Let X be a random variable in the probability space G(n,p) such that we have |X(H_1)-X(H_2)| ≤ C if H_1 and H_2 differ in at most one edge. Then, for any positive α < 2 √(n^2p), we have 
    
    (|X-[X]| > C α√(n^2p)) ≤ 2e^-α^2/4



The 2-core of a graph G is the maximal induced subgraph of G in which all vertices have degree at least 2. The next lemma is a simple consequence of Theorem 5.4 of <cit.> and Theorem 3 of <cit.>.



    Let >0 be fixed, and let p=1+/n. Then there exists _0>0 such that for every ∈ (0, _0), the following three properties hold whp in G ∼ G(n,p).
    
        
  * the largest connected component of G has size between n and 3  n,
        
  * the second largest connected component of G has size at most 20 log n/^2,
        
  * the 2-core of the largest connected component of G has size at most 2^2 n.
    


For n ≥ 1, a path P_n is a graph on n vertices v_1, …, v_n with edges v_1 v_2, …, v_n-1v_n. 

A rooted tree is a connected graph with no cycles, where one of the vertices of T has been marked as the root. Recall that Cayley's formula[Cayley's formula is often phrased as counting the number of labelled trees on t vertices.] states that the number of trees on vertex set [t] is t^t-2. It follows that the number of rooted trees on vertex set [t] vertices is t^t-1. 

If T is a tree rooted at v, then the depth (w) of a vertex w is the distance from w to v in T. The height of T, denoted by h(T) is the maximum depth of a vertex in T, while the width of T is given by

    w(T)=max_k∈ [h(T)]|{w∈ V(T):(w)=k}|.

If u is a vertex in a tree T without a root, we refer to the height of T rooted at u as the height of u.

A Galton-Watson tree is a rooted tree which is constructed recursively at random. Starting from the root, each vertex is given a random number of children independently of the other vertices according to a distribution ξ on ℕ_0. The distribution ξ is called the offspring distribution and the tree is referred to as the ξ-Galton-Watson tree. For concreteness, we say that the vertex set of a Galton-Watson tree T is the integer interval [| T|].

In <cit.>, Addario-Berry, Devroye, and Janson established sub-gaussian tail bounds for the distributions of the width and height of a Galton-Watson tree conditioned on the number of its vertices. In the following two theorems, ξ is a distribution on _0 with expectation 1 and positive, but finite, variance.


There exist c_1, C_1>0 such that for a ξ-Galton-Watson tree T and all x,t∈, 

    (h(T) ≥ x || V(T)|=t) ≤ C_1e^-c_1 x^2/t.




There exist c_2, C_2>0 such that for a ξ-Galton-Watson tree T and all x,t∈,

    (w(T) ≥ x|| V(T)|=t) ≤ C_2e^-c_2 x^2/t.



The relevance of these theorems for our paper stems from the following theorem from <cit.>.


    If ξ is the Poisson(1) distribution and T is a ξ-Galton-Watson tree, then the distribution of T conditioned on the event | V(T)| = t is the same as the uniform distribution over rooted trees on vertex set [t].


The following lemma is a corollary of the previous three results, and it will be central in our proof of <Ref>.



    There exist constants c_1, c_2, C_1,C_2 >0 such that for all x,t∈, if T is sampled uniformly at random from all rooted trees on [t], then 
    
    (h(T) ≥ x) ≤ C_1e^-c_1 x^2/t,

    and 
    
    (h(T) ≤ t/x) ≤ C_2e^-c_2 x^2/t.




    The first equation (<ref>) follows immediately from Theorems <ref> and <ref>, while (<ref>) follows from Theorems <ref>, <ref> and the additional observation that h(T)w(T)≥ t.


We need the following well-known fact about Poisson(μ)-Galton-Watson tree (see for instance Section 6 of <cit.>).



    Let 𝒯 be a Poisson(μ)-Galton-Watson tree. Then
    
    (|𝒯|=t)=t^t-1(μ e^-μ)^t/μ t!.



Ding, Lubetzky and Peres <cit.> gave a full characterisation of the structure of the giant component of G ∼ G(n,p) in the strictly supercritical regime, i.e. where p=1+/n for some constant >0. We will use the following consequence of their work, which was already used in a slightly different form in <cit.>.


 
    Let p=1+/n for some constant >0.
    Let 𝒞_1 be the largest connected component of G ∼ G(n,p), let 𝒞^(2)_1 be the 2-core of 𝒞_1, and let 𝒞_1 ∖𝒞^(2)_1 be the graph obtained from 𝒞_1 by deleting all edges from 𝒞^(2)_1.
    Let 0 < μ <1 be such that μ e^-μ=(1+)e^-(1+) and consider 2 ^2 n independent Poisson(μ)-Galton-Watson trees T_1, …, T_2^2 n.
    Then, for every ℓ and M, if whp the disjoint union of T_1, …, T_2 ^2 n does not contain a set of vertex-disjoint paths of length ℓ covering at least M edges, then the same holds whp for 𝒞_1 ∖𝒞^(2)_1.


Finally, to prove the concentration part of <Ref>, we will also require Talagrand's inequality. Let Ω=∏_i=1^nΩ_i be a probability space where each Ω_i is a finite probability space and Ω has the product measure. A random variable XΩ→ is called K-Lipschitz if | X(ω)-X(ω')|≤ K whenever ω,ω'∈Ω differ in at most one coordinate. Let f→. We say that X is f-certifiable if for all ω∈Ω and s∈, if X(ω)≥ s there exists
I ⊂ [n] with | I|≤ f(s) so that all ω' ∈Ω that agree with ω on I satisfy X(ω')≥ s. The following theorem is a simple corollary to Talagrand's inequality (see Theorem 7.7.1 of <cit.>).


    Let f→ be a function and let XΩ→ be K-Lipschitz and f-certifiable. Then for all μ, α∈,
    
    (X≤μ - α K√(f(μ)))(X≥μ) ≤ e^-α^2/4.





§ THE MAIN COUNTING LEMMA



For a graph G, we say that an edge uv of G is m-centred if there exist two vertex-disjoint paths of length at least m-1 in G - uv starting at u and v, respectively. For t≥ m, we define (t,m) as the set of pairs (uv,T) such that T is a tree on [t] and uv is an m-centred edge of T.

Recall that for a graph G and an integer ℓ, _ℓ(G) is the maximum number of vertices that can be covered by a system of vertex-disjoint paths of length at least ℓ in G. The key insight of our proofs is that the number of m-centred edges in a tree T can be used to estimate _ℓ(T). Indeed, if v_0… v_k is a path in T for k≥ 3m and m-1 ≤ i ≤ k-m, then T-v_iv_i+1 contains two vertex-disjoint paths of length m-1 that start at v_i and v_i+1, respectively. In other words, v_iv_i+1 is m-centred in T. Since the interval [m-1,k-m] has length k-2m+1>k+1/3, it follows that

    _3m(T) ≤ 3|{m-centred edges in T}|.


Conversely, we may choose an arbitrary root r in T and construct a system of vertex-disjoint paths in T greedily by taking the longest monotone (in the tree order) path that is disjoint from all previously included paths until no path of length ℓ is left. The resulting systems of paths will include all vertices that are incident to ℓ-centred edges in T. Thus, we have

    |{ℓ-centred edges in T}|≤_ℓ(T).


The following lemma will allow us to estimate the number of m-centred edges in a typical tree.



    There exist constants c_1, C_1>0 such that for all t∈ and m<t,
    
    |(t,m)| < C_1∑_k=m^t/2 t^t-1k^-3/2 e^-c_1m^2/k.

    Furthermore, there exist constants c_2, C_2>0 such that
    
    |(t,m)| > C_2∑_k=c_2 m^2^t/2 t^t-1k^-3/2.




    For m,t∈, S⊂ [t] and u∈ S let _m(S;u) be the set of trees on S rooted at u whose height is at least m-1. For v∈ [t]∖ S and a rooted tree T_v∈_m(S,v), we write T_u+T_v for the tree on [t] with edge set E(T_u)∪ E(T_v)∪{uv}. Note that uv is an m-centred edge of T_u+T_v so that (uv,T_u+T_v)∈(t,m). Thus the following map is well-defined.
    
    ϕ⋃_S⊂ [t]
     u∈ S
     v∈ [t]∖ S_m(S;u)×_m([t]∖ S;v)    →(t,m)      (T_u,T_v)    ↦ (uv,T_u + T_v).

    For each (uv,T)∈(t,m), if T_u and T_v are the components of T-uv rooted at u and v, respectively, then ϕ^-1(uv,T)={(T_u,T_v),(T_v,T_u)}. Thus, the domain of ϕ is exactly twice as large as its codomain (t,m), and since _m(S;u) is empty unless | S|≥ m, we have
    
    |(t,m)|   = 1/2∑_k=m^t-m∑_S∈ [t]^(k)
     u∈ S
     v∈ [t]∖ S|_m(S;u)|·|_m([t]∖ S;v)|
       =1/2∑_k=m^t-mtkk(t-k) |_m([k];1)|·|_m([t-k];1)|.

    To bound this quantity from above, note that since there are exactly k^k-2 trees on [k] overall, we may infer from <Ref> that
    
    |_m([k];1)|≪ k^k-2e^-cm^2/k.

    Inserting this into (<ref>), we find that
    
    |(t,m)|   ≪∑_k=m^t-mtkk^k-1(t-k)^t-k-1 e^-cm^2(1/k+1/(t-k))
       ≪∑_k=m^t/2tkk^k-1(t-k)^t-k-1 e^-cm^2/k
       =∑_k=m^t/2t!k^k-1(t-k)^t-k-1/k!(t-k)! e^-cm^2/k.

    By Stirling's formula (<Ref>), this can be bounded as
    
    |(t,m)|   ≪∑_k=m^t/2t^t+1/2/k^3/2(t-k)^3/2 e^-cm^2/k≪ t^t-1∑_k=m^t/2 k^-3/2 e^-cm^2/k,

    as desired.

    To bound |(t,m)| from below, we observe that by <Ref>,
    
    |_m([k];1) |≥ k^k-2 (1-Ce^-ck/m^2).

    In particular, there exists a constant c_2 such that |_m([k];1) |≥ k^k-2/2 when k>c_2 m^2. Therefore, we deduce from (<ref>) that
    
    |(t,m)|≫∑_k=c_2 m^2^t/2tkk^k-1(t-k)^t-k-1.

    As before, it follows from Stirling's formula that
    
    |(t,m)|   ≫  t^t-1∑_k=c_2 m^2^t/2 k^-3/2.





§ PROOF OF <REF>




    For every >0, there exists a unique μ=μ()∈ (0,1) such that μ e^-μ=(1+)e^-(1+). We choose _0 such that for all <_0, we have 1-μ()>/2 and 1+≤ e^ - ^2/3. Let δ∈ (0,1] and ∈ (0,_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 ℓ=δ/ covers at most D^2 δ^-2 n edges, for some absolute constant D > 0. Note that the claim is trivial if ℓ<100 so that we may assume that ℓ≥ 100. Here and throughout the proof, we ignore rounding unless it is critical to the correctness of the proof.
    
    Let 𝒞_1 be the largest connected component of G, let 𝒞^(2)_1 be the 2-core of 𝒞_1, and let 𝒞_1 ∖𝒞^(2)_1 be the graph obtained from 𝒞_1 by deleting the edges of 𝒞^(2)_1.
    Furthermore, we define the following random variables:
    
        
  * Let X_ℓ be the maximum number of edges covered by vertex-disjoint paths of length at least ℓ in components of G of size at most 20 log n/^2.
        
  * Let Y_ℓ be the maximum number of edges covered by vertex-disjoint paths of length at least ℓ in 𝒞_1.
        
  * Let Z_ℓ be the maximum number of edges covered by vertex-disjoint paths of length at least ℓ/3 in 𝒞_1 ∖𝒞^(2)_1.
    
    By <Ref>(b), we have that whp the number of edges of G covered by vertex-disjoint paths of length at least ℓ is at most X_ℓ+Y_ℓ.
    As in <cit.>, a simple counting argument shows that Y_ℓ≤ 6|𝒞^(2)_1|+6Z_ℓ, and hence by <Ref>(c), we have whp Y_ℓ≤ 12 ^2 n+6Z_ℓ. Therefore, to finish the proof, it suffices to prove that whp we have X_ℓ≪^2δ^-2 n and Z_ℓ≪^2δ^-2 n.
    We start by proving that X_ℓ≪^2 δ^-2 n whp.

    Let S⊂ [n] and set m=ℓ/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]∖ 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
    
    𝔼[X_S] ≤ |ℳ(t,m)|p^t-1 (1-p)^t(n-t).

    Indeed, |ℳ(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⊂ G[S], and (1-p)^t(n-t) is the probability that there are no edges between S and [n]∖ S.
    Since X_ℓ is bounded by the sum of all X_S for which S⊂ [n] has size between m and 20log n/^2, inserting the upper bound from <Ref> into (<ref>), yields
    
    [X_ℓ]    ≪∑_t=m^20/^2log nnt∑_k=m^t/2 t^t-1k^-3/2 e^-cm^2/k p^t-1 (1-p)^t(n-t)
       ≪∑_t=m^20/^2log nn!/t!(n-t)!∑_k=m^t/2 t^t-1k^-3/2 e^-cm^2/ke^(t-1)/n^t-1 e^-1+/nt(n-t).

    Simplifying and applying <Ref>, we obtain
    
    [X_ℓ]    ≪ n ∑_t=m^20/^2log nn^n-t+1/2/t^t+1/2(n-t)^n-t+1/2∑_k=m^t/2 t^t-1k^-3/2 e^-cm^2/k e^-t.

    Moreover, we have 
    
    n^n-t+1/2/(n-t)^n-t+1/2 = 1/(1-t/n)^n-t+1/2 = e^t+O(t^2/n)≪ e^t.

    Inserting (<ref>) into (<ref>), we obtain
    
    [X_ℓ]    ≪ n ∑_t=m^20/^2log n∑_k=m^t/2 k^-3/2t^-3/2 e^-cm^2/k
       ≪ n ∑_t=m^∞∑_k=m^t/2 k^-3/2t^-3/2 e^-cm^2/k
       ≪ n ∑_t=m^∞ t^-3/2∫_m^t/2 k^-3/2e^-cm^2/k k,

    where the integral comparison that yields the last inequality is valid because the integrand is positive and for all x,y≥ m ≥ 1 such that | x-y|≤ 1, we have
    
    x^-3/2e^-cm^2/x/y^-3/2e^-cm^2/y=(y/x)^3/2e^c( m^2/y-m^2/x)≤ 2^3/2 e^c.

Performing the substitution k=m^2/x^2, we obtain
    
    [X_ℓ]    ≪ nm^-1∑_t=m^∞ t^-3/2∫_√(2/t)m^√(m) e^-cx^2 x 
       ≪ nm^-1∑_t=m^∞ t^-3/2∫_0^√(m)x ≥√(2/t)m e^-cx^2 x
    
            ≪ nm^-1∫_0^√(m) e^-cx^2∑_t=max(2m^2/x^2, m)^∞ t^-3/2 x
       ≪ nm^-1∫_x=0^√(m) e^-cx^2∫_t=2m^2/x^2^∞ t^-3/2 t  x 
       ≪ nm^-1∫_x=0^√(m) e^-cx^2 (2m^2/x^2)^-1/2 x 
       ≪ nm^-2∫_0^∞ xe^-cx^2 x.

    Since the moments of a Gaussian random variable exist and are finite, we may insert the value of m to obtain [X_ℓ] ≪ n ^2δ^-2. An application of <Ref> gives the desired conclusion. 


    We now move on to bounding Z_ℓ. Let 0 < μ <1 be such that μ e^-μ=(1+)e^-(1+) and consider 2 ^2 n independent Poisson(μ)-Galton-Watson trees T_1, …, T_2^2 n. By <Ref>, to prove that Z_ℓ≪^2 δ^-2 n whp, it is enough to show that M_ℓ, the number of edges that can be covered by vertex-disjoint paths in T_1∪…∪ T_2^2 n of length at least ℓ/3, satisfies M_ℓ≪^2 δ^-2 n whp.

    To bound M_ℓ, we employ the second moment method, as was done in <cit.>. However, <Ref> will allow us to obtain better bounds once more.
    Set m=ℓ/9 and let T be a Poisson(μ)-Galton-Watson tree and let S_ℓ be the number of m-centred edges in T. Thus, [M_ℓ]≤ 6^2n [S_ℓ]. It is clear that
    
    [S_ℓ]    ≤ 3∑_t ≥ mℙ(|T|=t)||ℳ(t,m)|/t^t-2.

    Inserting <Ref> into the above, we obtain
    
    [S_ℓ]    ≪∑_t ≥ m1/t^t-2t^t-1(μ e^-μ)^t/μ t!∑_k=m^t/2 t^t-1k^-3/2 e^-cm^2/k
       ≪∑_t ≥ mt (1+)^te^-(1+)t/t!∑_k=m^t/2 t^t-1k^-3/2 e^-cm^2/k.

    Using that (1+)^t ≤ e^ t- ^2/3t and <Ref>, we have
    
    [S_ℓ]    ≪∑_t ≥ m∑_k=m^t/2 k^-3/2t^-1/2 e^-^2/3t e^-cm^2/k
       ≪∑_t ≥ m e^-^2/3t t^-1/2∫_k=m^t/2  k^-3/2e^-cm^2/k k.

    As for the computation of [X_ℓ], we substitute k=m^2/x^2 in the integral to obtain
    
    [S_ℓ]    ≪m^-1∑_t=m^∞ e^-^2/3t t^-1/2∫_√(2/t)m^√(m) e^-cx^2 x 
       ≪m^-1∑_t=m^∞∫_x=√(2/t)m^√(m)x ≥√(2/t)m e^-^2/3t t^-1/2 e^-cx^2 x 
       ≪m^-1∫_x=0^√(m) e^-cx^2∑_t=2m^2/x^2^∞  e^-^2/3t t^-1/2 x 
       ≪m^-1∫_x=0^√(m) e^-cx^2∫_t=2m^2/x^2^∞  e^-^2/3t t^-1/2 t  x.

    Performing the second substitution t=y^2/^2 in the integral, we obtain
    
    [S_ℓ]    ≪m^-1∫_x=0^√(m) e^-cx^2∫_y=√(2)m /x^∞e^-y^2/3/ y  x 
       ≪δ^-1∫_x=0^∞ e^-cx^2∫_y=0^∞  e^-y^2/3 y  x 
       ≪δ^-1,

    showing that [M_ℓ]≪^2δ^-1n.
    
    For the second moment, we use the same computation as <cit.>. Using <Ref>, which specifies the distribution of | T|, we can calculate that [| T|^2]=(1-μ)^-3. Thus,
    
    [M_ℓ] ≤ 18^2 n [S^2_ℓ] ≤ 18^2 n[|T|^2] =18^2 n/(1-μ)^3≤144n/,

    where the last inequality follows from 1-μ≥/2.
    Since [M_ℓ]≪^2δ^-1n and [M_ℓ] ≪ n^-1 as well, it follows from Chebyshev's inequality that M_ℓ≪^2 δ^-1 n whp, as desired.






§ PROOF OF <REF>





Recall that _ℓ(T) is the maximum number of vertices in T that can be covered by vertex-disjoint paths of length at least ℓ. We begin by estimating the expected value of _ℓ(T).


There exists a constant C such that for all integers 1 ≤ℓ≤ t, we have [_ℓ(T)]≤Ct/ℓ, where T is sampled uniformly at random from all trees on vertex set [t]. Furthermore, there exists a constant c>0 such that for all t∈ and 1≤ℓ<c√(t), we have [_ℓ(T)]≥ ct/ℓ.



    For a tree T on [t] and m≤ t, let X_m(T) be the number of pairs (e,T) in (t,m), i.e., the number of m-centred edges in T. Recall that by (<ref>), we have _3m(T)≤ 3X_m(T), while by (<ref>), we have X_ℓ(T)≤_ℓ(T). Observe further that since _ℓ'(T)≤_ℓ(T) for ℓ'>ℓ, it is enough to show the upper bound in the claim when ℓ is divisible by three. Thus, to prove the claim, it suffices to show that [X_m]=O(t/m) for 1≤ m≤ t, and that there exists c>0 such that [X_m]=Ω(t/m) for 1≤ m ≤ c√(t).
    
    To bound [X_m] from above, we make similar calculations to those in the proof of <Ref>. By <Ref>, we have
    
    [X_m(T)]    ≪ t∑_k=m^t/2 k^-3/2 e^-ct^2/k≪ t∫_m^t/2 k^-3/2 e^-ct^2/k k ≪ t∫_m^t/2 k^-3/2 e^-cm^2/k k.

    By substituting k=m^2/x^2, we obtain
    
    [X_m(T)]    ≪t/m∫_m/√(t)^√(m) e^-cx^2 x≪t/m,

    as desired.

    It remains to bound [X_m(T)] from below. By the lower bound in <Ref>, there exists a constant c_2 such that
    
    [X_m(T)] ≫ t∑_k=c_2ℓ^2^t/2 k^-3/2.

    Assuming that c_2m^2<t/4, this gives
    
    [X_m(T)] ≫ t ∫_c_2 m^2^t/2 k^-3/2 k ≫t/√(c_2 m^2)-t/√(t/2)≫t/m,

    as desired.


As a function of the edges of T, _ℓ(T) is continuous in the sense that changing a single edge can change _ℓ by at most 2ℓ. If ℓ is sufficiently small compared to t, we can use Talagrand's inequality (see <Ref>) to exploit this continuity to show that _ℓ is concentrated around its mean.


    For v∈ [t-1] let Ω_v=[t] and consider the product space Ω=∏_v=1^t-1Ω_v with uniform probability measure _ω. Each element ω∈Ω can be associated with a graph with vertex set [t] and edge set {uv:ω_u=vω_v=u}. In particular, each tree T on [t] is associated with the unique element ω∈Ω for which ω_v is the first vertex on the path from v to t. For ω∈Ω, we define _ℓ(ω) as _ℓ(G_ω) for the unique graph G_ω associated with ω.

    Observe that the random variable ω↦_ℓ(G_ω) is 2ℓ-Lipschitz. Furthermore, if G_ω has a system of vertex-disjoint paths of length at least ℓ that cover m vertices, then the m-1 edges of this path system certify that _ℓ(G_ω)≥ m. Hence, _ℓ is f-certifiable for f(s)=s-1. Therefore, we may apply <Ref> to see that for any α,μ >0,
    
    _ω(_ℓ(G_ω)≤μ -   αℓ√(μ)) _ω(_ℓ(G_ω)≥μ)≤ e^-α^2/4.

    Since the size of Ω is t^t-1 and there are t^t-2 trees on [t], the set {ω:G_ω is a tree} has density 1/t in Ω, it follows that for the uniform probability measure _T over all trees on [t], we have
    
    _T(_ℓ(T)≤μ -  α√(ℓ^2 μ)) _T(_ℓ(T)≥μ)≤ t^2e^-α^2/4.

    Let δ∈ (0,1). By <Ref>, there exists c>0 such that _T[_ℓ(T)]≥ ct/ℓ, independently of t as long as ℓ≪ c√(t). Thus, to bound _T(_ℓ(T)≥ (1+δ)_T[_ℓ(T)]), we may apply (<ref>) with μ=(1+δ)_T[_ℓ(T)] and
    
    α=δ/4√(_T[_ℓ(T)]/ℓ^2)≥δ/4√(ct/ℓ^3),

    so that 
    
    μ-α√(ℓ^2μ)=(1+δ)_T[_ℓ(T)]-δ/4√((1+δ)_T[_ℓ(T)]^2)≥ (1+δ/2)_T[_ℓ(T)].

    Inserting this into (<ref>), we obtain
    
    _T(_ℓ(T)≥ (1+δ)_T[_ℓ(T)])≤t^2e^-ctδ^2/64ℓ^3/_T(_ℓ(T)≤ (1+δ/2)_T[_ℓ(T)]).

    By Markov's inequality, the denominator is at least 1-1/(1+δ/2)≥δ/3 so that
    
    _T(_ℓ(T)≥ (1+δ)_T[_ℓ(T)])≤3t^2e^-ctδ^2/64ℓ^3/δ.


    On the other hand, if we let μ=_T[_ℓ(T)] and α=δ√(ct/ℓ^3) and denote _T(_ℓ(T)<(1-δ)_T[_ℓ(T)]) by q_δ, then
    
    _T(_ℓ(T)≥_T[_ℓ(T)])≤ t^2q_δ^-1e^-ctδ^2/ℓ^3.

    Since _ℓ(T) is bounded by t, _T[_ℓ(T)] can be bounded as
    
    _T[_ℓ(T)]   ≤ q_δ(1-δ)_T[_ℓ(T)]+(1-q_δ)_T[_ℓ(T)]+_T(_ℓ(T) > _T[_ℓ(T)])t
       ≤ (1-q_δδ)_T[_ℓ(T)] + t^3q_δ^-1e^-ctδ^2/ℓ^3,

    which implies that
    
    _T(_ℓ(T)<(1-δ)_T[_ℓ(T)])=q_δ≤(t^3/δ_T[_ℓ(T)]e^-ctδ^2/ℓ^3)^1/2≤ t√(ℓ/cδ) e^-ctδ^2/2ℓ^3.

    We may now apply a union bound for (<ref>) and (<ref>), and by renaming the constant c appropriately, we obtain the claim.


The fact that the absence or presence of a single edge can change _ℓ(T) by as much as 2ℓ prevents us from using Talagrand's inequality to show that _ℓ(T) is tightly concentrated when ℓ is larger than t^1/3. Nonetheless, we believe that ℓ=o(√(t)) is sufficient for tight concentration.


If ℓ=ℓ(t) is o(√(t)) as t approaches infinity, then |_ℓ(T) - [_ℓ]| < δ t/ℓ with high probability for all δ >0.




§ ACKNOWLEDGEMENTS

The first author was supported by the Slovenian Research and Innovation Agency (ARIS) under the grants Z1-50003, P1-0297, and N1-0285, and by the European Union (ERC, KARST, 101071836).
The second author is funded by EPSRC (Engineering and Physical Sciences Research Council) and by the Cambridge Commonwealth, European and International Trust.
The third author was funded through a Trinity External Researcher Studentship by Trinity College of the University of Cambridge.





§ PROOF OF <REF>



We first recall the following result.


    
    Let P=(V,E) be a path of length ℓ and let B ⊆ E, |B| ≤αℓ, where α≥1/ℓ. Let Q be a graph obtained from P by removing the edges from B. Then there exist vertex-disjoint subpaths {Q^j}_j ∈ J of Q such that each Q^j is of length at least 1/3 α and they cover at least (1/3 - α) ℓ vertices of V.



    By <Ref>, there exist D>1,_0'>0 such that for all δ∈ (0,1] and ∈ (0,_0') the following holds. With high probability, G∼ G(n,1+/n) contains no system of vertex-disjoint paths of length at least δ/3 that covers more than D^2 δ^-2 n vertices.
    
    For δ, q∈ (0,1],  let _0 be the minimum of _0' and q δ^2/192 D and let p=1+/n.
    Suppose that Alg is an adaptive algorithm that reveals a path of length ℓ≥δ/ with probability at least q by querying at most δ q ℓ/1152 D p pairs of vertices in a graph G ∼ G(n,p). 

    Let n' = (1 + 96 D ^2/q δ^2)n, and note that this is at most (1+/2)n, as ≤q δ^2/192 D. Let further V_0 = [n'], I_0 = ∅, and s = 96 D ^2 n/δ^2 q (ℓ + 1). We will now construct a sequence of sets V_0⊃ V_1⊃…⊃ V_s recursively, by repeating the following steps for i ∈{1, …, s}.
    
        
  * Sample an injection f_i [n]→ V_i-1 uniformly at random and sample G_i∼ G(V_i-1, p). We let f_i(G_i) denote the graph with vertex set [n] and edge set {uv∈ [n]^(2):f(uv)∈ E(G_i)}. We run Alg on f_i(G_i), noting that since f_i(G_i)∼ 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  was queried by Alg} (note that |E(L_i)| ≤q ℓδ/1152 D p), and let K_i ⊆ L_i be the intersection of L_i and G_i.
        
  * If K_i contains a path of length ℓ, then we fix one such path which we call P_i and let V_i = V_i-1∖ V(P_i) and I_i = I_i-1∪{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 ∈ [s], |V_i-1| ≥ |V_s| ≥ n' - (ℓ+1) s = n. 

    We now define a graph H on the vertex set V_0 so that {u,v}∈ E(H) if and only if {u,v}∈ E(L_i) for some i ∈ [s] and for the smallest such i_0 it holds that {u,v}∈ E(K_i_0). 
    For every e∈ [n']^(2), we have
    
    (e∈ E(H))≤1+/n = 1+/n'+1+/n'(n'/n-1)≤1+2/n',

    and while the presence of edges in H is not necessarily independent, one can check that for any distinct e_1,…,e_r∈ [n']^(2),
    
    (e_1,…,e_r ∈ E(H)) ≤(1+2/n')^r.
    
     Thus, since the property of having a family of vertex-disjoint paths with length at least ℓ that cover M vertices is monotone for all ℓ and M, the following holds. If H contains a set of vertex-disjoint paths with length at least δ/ that cover at least 4 D ^2 δ^-2 n' = D (2 )^2 δ^-2 n' vertices with probability at least q^2/4, the same holds with probability at least q^2/4 for G∼ G(n', 1+2/n').

    Thus, it is enough to prove that H has this property with probability at least q^2/4 since this will then be in contradiction with <Ref> for sufficiently large n. 

    For every i ∈ I_s let H_i be the graph on vertices V_i-1 with edges ( ⋃_j=1^i-1 E(L_j) ) ∩ V_i-1^(2).
    Observe that 
    
    |E(H_i)| ≤/6 δ|V_i-1|2.


    By definition, V_i-1∖ V_i is a path P_i in K_i for every i ∈ I_s. Thus, we can define B_i = E(P_i) ∩ 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) ⊆ E(H), and the graphs {Q_i}_i ∈ I_s are vertex-disjoint.

    Let I = {i ∈ I_s : |B_i| ≤/δℓ}. Applying <Ref> with α=δ/, we get that for every i ∈ I, there exist vertex-disjoint subpaths {Q_i^j}_j∈ J_i of Q_i such that each Q_i^j has length at least δ/3 and they cover at least (1/3 - /δ) ℓ≥1/4 (ℓ + 1) vertices of P_i, where the last inequality holds since <q δ^2/192 D, and thus, ℓ≥ 192.

    If |I| ≥sq/3, then {Q_i^j}_j ∈ J_i is a collection of paths of length at least δ/3 that cover at least 1/4 (ℓ+1) |I| ≥ 4 D ^2 δ^-2 n'. So it suffices to show that |I| ≥sq/3 with probability at least q^2/4. 

    Let I' = [s] ∖ I. For every i ∈ [s], we have 
    
    (i ∈ I')     = (i ∉ I_s) + (i ∈ I' | i ∈ I_s) (i ∈ I_s).

    Recall that (i ∈ I_s) is simply the success probability of Alg, which is at least q. For i ∈ I_s, consider the random embedding f_i [n]→ 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 (<ref>), that (e ∈ E(H_i)) ≤/6 δ for every e ∈ E(P_i). By the linearity of expectation we have that [|B_i|] = [|E(P_i) ∩ E(H_i)|] ≤/6 δℓ. Using Markov's inequality, we obtain that 
    
    (i ∈ I' | i ∈ I_s) = (|B_i| ≥/δℓ| i ∈ I_s) ≤[|B_i| | i ∈ I_s]//δℓ≤/6 δℓ//δℓ < 1/2.

     Using these inequalities in (<ref>) yields 
    (i ∈ I') ≤ 1 - (i ∈ I_s) + 1/2(i ∈ I_s) = 1 - 1/2(i ∈ I_s) ≤ 1 - q/2.
 

    Linearity of expectation now gives [|I'|] ≤ s (1 - q/2), and Markov's inequality implies that (|I'| ≥s/1 + q/2) ≤ 1 - q^2/4. Therefore, as q ∈ (0,1), 
    (|I| ≥sq/3) ≥(|I| ≥sq/2+q) = (|I'| ≤ s - sq/2+q) = (|I'| ≤s/1+q/2) ≥q^2/4,
 as desired.



