Extreme local statistics in random graphs: maximum tree extension counts

2023/10/18 by Araújo, Pedro, Griffiths, Simon, Šileikis, Matas +1
#05C80 #60C05 #60G70 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2310.11661

Abstract

We consider maximum rooted tree extension counts in random graphs, i.e., we consider M_n = max_v X_v where X_v counts the number of copies of a given tree in G_n,p rooted at vertex v. We determine the asymptotics of M_n when the random graph is not too sparse, specifically when the edge probability p=p(n) satisfies p(1-p)n ≫ log n. The problem is more difficult in the sparser regime 1 ≪ pn ≪ log n, where we determine the asymptotics of M_n for specific classes of trees. Interestingly, here our large deviation type optimization arguments reveal that the behavior of M_n changes as we vary p=p(n), due to different mechanisms that can make the maximum large.

Related

• Random enriched trees with applications to random graphs
• Maximum induced trees and forests of bounded degree in random graphs
• Greedy maximal independent sets via local limits
• Extremes on Trees
• Limiting probabilities for vertices of a given rank in rooted trees