A NOTE ON THE ACQUAINTANCE TIME OF RANDOM GRAPHS

Abstract. In this short note, we prove a 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 − log n − log log n→ ∞ (that is, above the threshold for Hamiltonicity). 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). 1