Weakly saturated random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915619326132224 |
|---|---|
| author | Bartha, Zsolt Kolesnik, Brett |
| author_facet | Bartha, Zsolt Kolesnik, Brett |
| contents | As introduced by Bollobás, a graph $G$ is weakly $H$-saturated if the complete graph $K_n$ is obtained by iteratively completing copies of $H$ minus an edge. For all graphs $H$, we obtain an asymptotic lower bound for the critical threshold $p_c$, at which point the Erdős--Rényi graph ${\mathcal G}_{n,p}$ is likely to be weakly $H$-saturated. We also prove an upper bound for $p_c$, for all $H$ which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollob{á}s and Morris for $H=K_r$, and we conjecture that this is sharp up to constants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_14716 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Weakly saturated random graphs Bartha, Zsolt Kolesnik, Brett Probability Combinatorics 60K35 (Primary), 05C80, 82B43 (Secondary) As introduced by Bollobás, a graph $G$ is weakly $H$-saturated if the complete graph $K_n$ is obtained by iteratively completing copies of $H$ minus an edge. For all graphs $H$, we obtain an asymptotic lower bound for the critical threshold $p_c$, at which point the Erdős--Rényi graph ${\mathcal G}_{n,p}$ is likely to be weakly $H$-saturated. We also prove an upper bound for $p_c$, for all $H$ which are, in a sense, strictly balanced. In particular, we improve the upper bound by Balogh, Bollob{á}s and Morris for $H=K_r$, and we conjecture that this is sharp up to constants. |
| title | Weakly saturated random graphs |
| topic | Probability Combinatorics 60K35 (Primary), 05C80, 82B43 (Secondary) |
| url | https://arxiv.org/abs/2007.14716 |