



























We consider site (vertex) percolation on $d$-regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergence of the ``Erdős-Rényi component phenomenon" in the supercritical regime $p=\frac{1+ε}{d-1}$: namely, the appearance of a unique giant component of order $n/d$ in the percolated subgraph, with all other components being of size $O(\log n)$. Our main results apply both to the $d$-dimensional hypercube and to pseudo-random graphs, and resolve two open questions in these cases. We further discuss differences (and similarities) between bond (edge) percolation setting and site percolation setting.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。