论文标题
随机子图中的大型完整未成年人
Large complete minors in random subgraphs
论文作者
论文摘要
令$ g $是至少$ k $的最低度的图表，让$ g_p $是通过使用概率$ p $独立保持每个边缘获得的$ g $的随机子图。当$ p = \ frac {1+ \ varepsilon} {k} $带有$ \ varepsilon> 0 $时，我们对$ g_p $包含的最大完整未成年人的大小感兴趣。我们表明，使用高概率$ g_p $包含一个完整的订单$ \tildeΩ（\ sqrt {k}）$，其中$ \ sim $隐藏了一个polylogarithmic因子。此外，如果$ g $的顺序在上面也以$ k $的恒定倍数为单位的情况下，我们表明可以删除此polyrogarithmic术语，从而使限制紧密。
Let $G$ be a graph of minimum degree at least $k$ and let $G_p$ be the random subgraph of $G$ obtained by keeping each edge independently with probability $p$. We are interested in the size of the largest complete minor that $G_p$ contains when $p = \frac{1+\varepsilon}{k}$ with $\varepsilon >0$. We show that with high probability $G_p$ contains a complete minor of order $\tildeΩ(\sqrt{k})$, where the $\sim$ hides a polylogarithmic factor. Furthermore, in the case where the order of $G$ is also bounded above by a constant multiple of $k$, we show that this polylogarithmic term can be removed, giving a tight bound.
