Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts
Random Structures & Algorithms · 2026-12 · 69 (4)
DOI: 10.1002/rsa.70096 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 16.11.2026. Verfasst von Pedro Araújo und 3 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: Czech Science Foundation, FAPERJ, CNPq.
Abstract (Originalsprache)
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.
Förderung
- Czech Science Foundation
- FAPERJ
- CNPq
Zitieren
APA
Araújo, P., Griffiths, S., Šileikis, M., & Warnke, L. (2026). Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts. Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70096
Vancouver
Araújo P, Griffiths S, Šileikis M, Warnke L. Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts. Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70096
BibTeX
@article{Arajo2026,
author = {Araújo, Pedro and Griffiths, Simon and Šileikis, Matas and Warnke, Lutz},
title = {Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {69},
number = {4},
doi = {10.1002/rsa.70096}
}
EUVIMED