2025/03/07 by Basak, Anirban, Karmakar, Shaibal · 1 citation
#05C80 #60C05 #60F10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2503.05311
We consider the upper tail large deviations of subgraph counts for irregular graphs H in \mathbbG(n,p), the sparse Erdős-Rényi graph on n vertices with edge connectivity probability p ∈ (0,1). For n-1/Δ ≪ p ≪ 1, where Δ is the maximum degree of H, we derive the upper tail large deviations for any irregular graph H. On the other hand, we show that for p such that 1 ≪ n^vH p^eH ≪ (log n)^α*H/(α*H-1), where vH and eH denote the number of vertices and edges of H, and α^*H denotes the fractional independence number, the upper tail large deviations of the number of unlabelled copies of H in \mathbbG(n,p) is given by that of a sequence of Poisson random variables with diverging mean, for any strictly balanced graph H. Restricting to the r-armed star graph we further prove a localized behavior in the intermediate range of p (left open by the above two results) and show that the mean-field approximation is asymptotically tight for the logarithm of the upper tail probability. This work further identifies the typical structures of \mathbbG(n,p) conditioned on upper tail rare events in the localized regime.