论文标题
弱饱和的随机图
Weakly saturated random graphs
论文作者
论文摘要
正如Bollobás所介绍的那样，如果完整的图$ k_n $是通过迭代完成$ h $减去边缘的副本，则图$ g $是微弱$ h $饱和的。对于所有图表$ h $，我们获得了关键阈值$ p_c $的渐近下限，此时erdős-rényi图$ {\ mathcal g} _ {n，p} $可能是弱$ h $ sy的。我们还证明了$ p_c $的上限，从某种意义上说，所有$ h $都严格平衡。特别是，我们以$ h = k_r $为Balogh，Bollob {á} S和Morris的上限提高了上限，我们认为这是敏锐的常数。
As introduced by Bollobás, a graph $G$ is weakly $H$-saturated if the complete graph $K_n$ is obtained by iteratively completing copies of $H$ minus an edge. For all graphs $H$, we obtain an asymptotic lower bound for the critical threshold $p_c$, at which point the Erdős--Rényi graph ${\mathcal G}_{n,p}$ is likely to be weakly $H$-saturated. We also prove an upper bound for $p_c$, for all $H$ which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollob{á}s and Morris for $H=K_r$, and we conjecture that this is sharp up to constants.
