Supercritical Site Percolation on Regular Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912974461992960 |
|---|---|
| author | Diskin, Sahar Krivelevich, Michael Markbreit, Itay |
| author_facet | Diskin, Sahar Krivelevich, Michael Markbreit, Itay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19038 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Supercritical Site Percolation on Regular Graphs Diskin, Sahar Krivelevich, Michael Markbreit, Itay Combinatorics Probability 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. |
| title | Supercritical Site Percolation on Regular Graphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2603.19038 |