The sharp threshold for jigsaw percolation in random graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2018
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908761747095552 |
|---|---|
| author | Cooley, Oliver Kapetanopoulos, Tobias Makai, Tamás |
| author_facet | Cooley, Oliver Kapetanopoulos, Tobias Makai, Tamás |
| contents | We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected'. Bollobás, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $Θ\left( \frac{1}{n\ln n} \right)$. We show that this threshold is sharp, and that it lies at $\frac{1}{4n\ln n}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1809_01907 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | The sharp threshold for jigsaw percolation in random graphs Cooley, Oliver Kapetanopoulos, Tobias Makai, Tamás Combinatorics 05C80, 60K35, 60C05 We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected'. Bollobás, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $Θ\left( \frac{1}{n\ln n} \right)$. We show that this threshold is sharp, and that it lies at $\frac{1}{4n\ln n}$. |
| title | The sharp threshold for jigsaw percolation in random graphs |
| topic | Combinatorics 05C80, 60K35, 60C05 |
| url | https://arxiv.org/abs/1809.01907 |