On the upper tail of star counts in random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917905467179008 |
|---|---|
| author | Akhmejanova, Margarita Šileikis, Matas |
| author_facet | Akhmejanova, Margarita Šileikis, Matas |
| contents | Let $X$ count the number of $r$-stars in the random binomial graph $\mathbb{G}(n,p)$. We determine, for fixed $r$ and $\varepsilon > 0$, the asymptotics of $\log \mathbb{P}(X \ge (1 + \varepsilon)\mathbb{E} X)$ assuming only $\mathbb{E} X \to \infty$ and $p \to 0$ thus giving a first class of irregular graphs for which the upper tail problem for subgraph counts (stated by Janson and Ruciński in 2004) is solved in the sparse setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_03404 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the upper tail of star counts in random graphs Akhmejanova, Margarita Šileikis, Matas Combinatorics Probability 05C80, 60C05, 60F10 Let $X$ count the number of $r$-stars in the random binomial graph $\mathbb{G}(n,p)$. We determine, for fixed $r$ and $\varepsilon > 0$, the asymptotics of $\log \mathbb{P}(X \ge (1 + \varepsilon)\mathbb{E} X)$ assuming only $\mathbb{E} X \to \infty$ and $p \to 0$ thus giving a first class of irregular graphs for which the upper tail problem for subgraph counts (stated by Janson and Ruciński in 2004) is solved in the sparse setting. |
| title | On the upper tail of star counts in random graphs |
| topic | Combinatorics Probability 05C80, 60C05, 60F10 |
| url | https://arxiv.org/abs/2501.03404 |