Packing and finding paths in sparse random graphs

Let G G (n, p) be a (hidden) Erdos-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 = ( (1/) ) in G with high probability, one must query the adjacency of (p (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 (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/ 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.