Extreme local statistics in random graphs: maximum tree extension counts
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_ | 1866915758152351744 |
|---|---|
| author | Araújo, Pedro Griffiths, Simon Šileikis, Matas Warnke, Lutz |
| author_facet | Araújo, Pedro Griffiths, Simon Šileikis, Matas Warnke, Lutz |
| contents | We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at vertex v. We determine the asymptotics of M_n when the random graph is not too sparse, specifically when the edge probability p=p(n) satisfies p(1-p)n \gg \log n. The problem is more difficult in the sparser regime 1 \ll pn \ll \log n, where we determine the asymptotics of M_n for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of M_n changes as we vary p=p(n), due to different mechanisms that can make the maximum large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11661 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extreme local statistics in random graphs: maximum tree extension counts Araújo, Pedro Griffiths, Simon Šileikis, Matas Warnke, Lutz Probability Combinatorics 05C80, 60G70, 60C05 We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = \max_v X_v where X_v counts the number of copies of a given tree in G_{n,p} rooted at vertex v. We determine the asymptotics of M_n when the random graph is not too sparse, specifically when the edge probability p=p(n) satisfies p(1-p)n \gg \log n. The problem is more difficult in the sparser regime 1 \ll pn \ll \log n, where we determine the asymptotics of M_n for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of M_n changes as we vary p=p(n), due to different mechanisms that can make the maximum large. |
| title | Extreme local statistics in random graphs: maximum tree extension counts |
| topic | Probability Combinatorics 05C80, 60G70, 60C05 |
| url | https://arxiv.org/abs/2310.11661 |