A dynamical approach to spanning and surplus edges of random graphs

2023/05/08 by Corujo, Josué, Limic, Vlada
#05C80 #60C05 #60J90 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2305.04716

Abstract

Consider a finite inhomogeneous random graph running in continuous time, where each vertex has a mass, and the edge that links any pair of vertices appears with a rate equal to the product of their masses. The simultaneous breadth-first-walk introduced by Limic (2019) is extended in order to account for the surplus edge data in addition to the spanning edge data. Two different graph-based representations of the multiplicative coalescent, with different advantages and drawbacks, are discussed in detail. A canonical multi-graph from Bhamidi, Budhiraja and Wang (2014) naturally emerges. The presented framework will facilitate the understanding of scaling limits with surplus edges for near-critical random graphs in the domain of attraction of general (not necessarily standard) eternal augmented multiplicative coalescent.

Related

• A playful note on spanning and surplus edges
• The standard augmented multiplicative coalescent revisited
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: The continuum graphs
• A novel approach to the giant component fluctuations