A note on the acquaintance time of random graphs (Q396895)

Summary: We prove the conjecture of \textit{I. Benjamini}, \textit{I. Shinkar} and \textit{G. Tsur} [``Acquaintance time of a graph'', Preprint, \url{arXiv:1302.2787}] on the acquaintance time \(\mathcal{AC}(G)\) of a random graph \(G \in G(n,p)\). It is shown that asymptotically almost surely \(\mathcal{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 \(\mathcal{AC}(G) = O(n^2/\log n )\).