A note on the acquaintance time of random graphs

Abstract

In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time $AC(G)$ of a random graph $G\in G(n,p)$. It is shown that asymptotically almost surely $AC(G)=O(\log n/p)$ for $G\in G(n,p)$, provided that $pn>(1+\epsilon )\log n$ for some $\epsilon >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 $K_n$ cannot be covered with $o(\log n/p)$ copies of a random graph $G\in G(n,p)$, provided that $pn>n^{1/2+\epsilon }$ and $p<1-\epsilon$ for some $\epsilon >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(n^2/\log n)$.

References in corpus (1)

• A Tight Upper Bound on Acquaintance Time of Graphs