Random Structures and Algorithms Прикладная математика

Extreme Local Statistics in Random Graphs: Maximum Tree Extension Counts

Pedro Araújo, Simon Griffiths, Matas Šileikis, Lutz Warnke
Wiley · 2026-11-16 · DOI 10.1002/rsa.70096

Аннотация

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.

Читать у издателя →