2024/09/04 by Vesna Iršič, Iršič, Vesna, Julien Portier +3
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2409.02812
openalex publication_date 2024/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω((ℓ)/(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.