
























Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $ε>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\ge \frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-ε)|V(G)|$ vertices. We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\ge \frac{\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。