Percolation on High-dimensional Product Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910403913580544 |
|---|---|
| author | Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael |
| author_facet | Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael |
| contents | We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest component is of order logarithmic in the number of vertices. In the supercritical regime, our main result recovers the sharp asymptotic of the order of the largest component, and shows that all the other components are typically of order logarithmic in the number of vertices. In particular, we show that this phase transition is quantitatively similar to the one of the binomial random graph.
This generalises the results of Ajtai, Komlós, and Szemerédi and of Bollobás, Kohayakawa, and Łuczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_03722 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Percolation on High-dimensional Product Graphs Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael Combinatorics Probability 05C80, 60K35, 82B43 We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest component is of order logarithmic in the number of vertices. In the supercritical regime, our main result recovers the sharp asymptotic of the order of the largest component, and shows that all the other components are typically of order logarithmic in the number of vertices. In particular, we show that this phase transition is quantitatively similar to the one of the binomial random graph. This generalises the results of Ajtai, Komlós, and Szemerédi and of Bollobás, Kohayakawa, and Łuczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph. |
| title | Percolation on High-dimensional Product Graphs |
| topic | Combinatorics Probability 05C80, 60K35, 82B43 |
| url | https://arxiv.org/abs/2209.03722 |