Packing and finding paths in sparse random graphs

Let G~ G(n,p) be a (hidden) Erd{o}s-R\'enyi 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 Ω(/p εlog(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.