Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts
ABSTRACT We consider maximum rooted tree extension counts in random graphs, that is, we consider where counts the number of copies of a given tree in rooted at vertex . We determine the asymptotics of when the random graph is not too sparse, specifically when the edge probability satisfies . The problem is more difficult in the sparser regime , where we determine the asymptotics of for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of changes as we vary , due to different mechanisms that can make the maximum large.
Authors
- Lutz Warnke (ORCID: https://orcid.org/0000-0002-1109-3957)
- Matas Šileikis (ORCID: https://orcid.org/0000-0002-6353-9105)
Institutions
- Vilnius University (LT)
- Czech Academy of Sciences (CZ)
- Universidade Federal de Pernambuco (BR)
- Pontifícia Universidade Católica do Rio de Janeiro (BR)
- University of California San Diego (US)
- Vilnius University of Applied Sciences (LT)
- Czech Academy of Sciences, Institute of Computer Science (CZ)
Publication Details
- Journal
- Random Structures and Algorithms
- Published
- 2026-11-16
- DOI
- https://doi.org/10.1002/rsa.70096
- Citations
- 2
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Grantová Agentura České Republiky
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- Akademie Věd České Republiky
- Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro