Critical threshold for regular graphs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910777441517568 |
|---|---|
| author | Bhadoo, Ishaan |
| author_facet | Bhadoo, Ishaan |
| contents | In this article, we study the critical percolation threshold $p_c$ for $d$-regular graphs. It is well-known that $p_c \geq \frac{1}{d-1}$ for such graphs, with equality holding for the $d$-regular tree. We prove that among all quasi-transitive $d$-regular graphs, the equality $p_c(G) = \frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00635 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Critical threshold for regular graphs Bhadoo, Ishaan Probability Combinatorics In this article, we study the critical percolation threshold $p_c$ for $d$-regular graphs. It is well-known that $p_c \geq \frac{1}{d-1}$ for such graphs, with equality holding for the $d$-regular tree. We prove that among all quasi-transitive $d$-regular graphs, the equality $p_c(G) = \frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption. |
| title | Critical threshold for regular graphs |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2412.00635 |