A dynamical approach to spanning and surplus edges of random graphs

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.