In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur 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 )$.
@article{10_37236_3357,
author = {William B. Kinnersley and Dieter Mitsche and Pawe{\l} Pra{\l}at},
title = {A note on the acquaintance time of random graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3357},
zbl = {1295.05210},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3357/}
}
TY - JOUR
AU - William B. Kinnersley
AU - Dieter Mitsche
AU - Paweł Prałat
TI - A note on the acquaintance time of random graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3357/
DO - 10.37236/3357
ID - 10_37236_3357
ER -
%0 Journal Article
%A William B. Kinnersley
%A Dieter Mitsche
%A Paweł Prałat
%T A note on the acquaintance time of random graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3357/
%R 10.37236/3357
%F 10_37236_3357
William B. Kinnersley; Dieter Mitsche; Paweł Prałat. A note on the acquaintance time of random graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3357
