Duality in inhomogeneous random graphs, and the cut metric

Abstract

The classical random graph model $G(n,\lambda /n)$ satisfies a `duality principle', in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric.

13 pages

References in corpus (3)

• The phase transition in inhomogeneous random graphs
• Percolation on dense graph sequences
• The cut metric, random graphs, and branching processes

Cited by in corpus (3)

• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Phase transitions for modified Erdös-Rényi processes
• Random minimum spanning tree and dense graph limits