2013/05/07 by William B. Kinnersley, Kinnersley, W., Dieter Mitsche +3
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1305.1675
openalex publication_date 2013/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time AC(G) of a random graph G ∈ G(n,p). It is shown that asymptotically almost surely AC(G) = O(log n / p) for G ∈ G(n,p), provided that pn > (1+ε) log n for some ε> 0 (slightly above the threshold for connectivity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely Kn cannot be covered with o(log n / p) copies of a random graph G ∈ G(n,p), provided that pn > n1/2+ε and p < 1-ε for some ε>0. We conclude the paper with a small improvement on the general upper bound showing that for any n-vertex graph G, we have AC(G) = O(n2/log n).