On the upper tail of star counts in random graphs
Let X count the number of r-stars in the random binomial graph G(n,p). We determine, for fixed r and ε>0, the asymptotics of logPX≥(1+ε)EX assuming only EX→∞ and p→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.
Authors
- Margarita Akhmejanova (ORCID: https://orcid.org/0000-0001-5688-7593)
- Matas Šileikis (ORCID: https://orcid.org/0000-0002-6353-9105)
Institutions
- Czech Academy of Sciences (CZ)
- Czech Academy of Sciences, Institute of Computer Science (CZ)
Publication Details
- Journal
- Electronic Journal of Probability
- Published
- 2025-01-01
- DOI
- https://doi.org/10.1214/25-ejp1345
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00