On the maximum number of common neighbours in dense random regular graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912137621798912 |
|---|---|
| author | Isaev, Mikhail Zhukovskii, Maksim |
| author_facet | Isaev, Mikhail Zhukovskii, Maksim |
| contents | We derive the distribution of the maximum number of common neighbours of a pair of vertices in a dense random regular graph.The proof involves two important steps. One step is to establish the extremal independence property: the asymptotic equivalence with the maximum component of a vector with independent marginal distributions. The other step is to prove that the distribution of the number of common neighbours for each pair of vertices can be approximated by the binomial distribution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15370 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the maximum number of common neighbours in dense random regular graphs Isaev, Mikhail Zhukovskii, Maksim Combinatorics 05C80 We derive the distribution of the maximum number of common neighbours of a pair of vertices in a dense random regular graph.The proof involves two important steps. One step is to establish the extremal independence property: the asymptotic equivalence with the maximum component of a vector with independent marginal distributions. The other step is to prove that the distribution of the number of common neighbours for each pair of vertices can be approximated by the binomial distribution. |
| title | On the maximum number of common neighbours in dense random regular graphs |
| topic | Combinatorics 05C80 |
| url | https://arxiv.org/abs/2312.15370 |