科研之友
微信
新浪微博
Facebook
分享链接
摘要
Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely AC(G) <= p(-1) log(O(1)) n for a random graph G is an element of G(n,p), provided that G is connected. Recently, Kinnersley, Mitsche, and Pralat made a major step toward this conjecture by showing that asymptotically almost surely AC(G) = O(logn/p), provided that G has a Hamiltonian cycle. In this paper, we finish the task by showing that the conjecture holds in the strongest possible sense, that is, it holds right at the time the random graph process creates a connected graph. Moreover, we generalize and investigate the problem for random hypergraphs.
- 出版日期2016
