Packing and finding paths in sparse random graphs

Abstract

Let $G\sim G(n,p)$ be a (hidden) Erdős-Rényi random graph with $p=(1+\epsilon )/n$ for some fixed constant $\epsilon >0$. Ferber, Krivelevich, Sudakov, and Vieira showed that to reveal a path of length $\ell =\Omega \left(\frac{\log (1/\epsilon )}{\epsilon }\right)$ in $G$ with high probability, one must query the adjacency of $\Omega \left(\frac{\ell }{p\epsilon \log (1/\epsilon )}\right)$ 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/\epsilon )$ in both $\ell$ 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 $\ell =o\left((t/\log t{)}^{1/3}\right)$, the maximum number of vertices covered by edge-disjoint paths of length at least $\ell$ in a random labelled tree of size $t$ is $\Theta (t/\ell )$ with high probability.

18 pages