Random cliques in random graphs revisited
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910900999421952 |
|---|---|
| author | Morris, Robert Riordan, Oliver |
| author_facet | Morris, Robert Riordan, Oliver |
| contents | We study the distribution of the set of copies of some given graph $H$ in the random graph $G(n,p)$, focusing on the case when $H = K_r$. Our main results capture the 'leading term' in the difference between this distribution and the 'independent hypergraph model', where (in the case $H = K_r$) each copy is present independently with probability $π= p^{\binom{r}{2}}$. As a concrete application, we derive a new upper bound on the number of $K_r$-factors in $G(n,p)$ above the threshold for such factors to appear.
We will prove our main results in a much more general setting, so that they also apply to random hypergraphs, and also (for example) to the case when $p$ is constant and $r = r(n) \sim 2\log_{1/p}(n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00964 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random cliques in random graphs revisited Morris, Robert Riordan, Oliver Combinatorics Probability 05C80, 05C70, 05C65 We study the distribution of the set of copies of some given graph $H$ in the random graph $G(n,p)$, focusing on the case when $H = K_r$. Our main results capture the 'leading term' in the difference between this distribution and the 'independent hypergraph model', where (in the case $H = K_r$) each copy is present independently with probability $π= p^{\binom{r}{2}}$. As a concrete application, we derive a new upper bound on the number of $K_r$-factors in $G(n,p)$ above the threshold for such factors to appear. We will prove our main results in a much more general setting, so that they also apply to random hypergraphs, and also (for example) to the case when $p$ is constant and $r = r(n) \sim 2\log_{1/p}(n)$. |
| title | Random cliques in random graphs revisited |
| topic | Combinatorics Probability 05C80, 05C70, 05C65 |
| url | https://arxiv.org/abs/2504.00964 |