The cut metric, random graphs, and branching processes

DOI10.1007/S10955-010-9982-ZzbMATH Open1197.82056arXiv0901.2091OpenAlexW3103290611MaRDI QIDQ5961848FDOQ5961848

Béla Bollobás, Svante Janson, Oliver Riordan

Publication date: 16 September 2010

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: In this paper we study the component structure of random graphs with independence between the edges. Under mild assumptions, we determine whether there is a giant component, and find its asymptotic size when it exists. We assume that the sequence of matrices of edge probabilities converges to an appropriate limit object (a kernel), but only in a very weak sense, namely in the cut metric. Our results thus generalize previous results on the phase transition in the already very general inhomogeneous random graph model we introduced recently, as well as related results of Bollob'as, Borgs, Chayes and Riordan, all of which involve considerably stronger assumptions. We also prove corresponding results for random hypergraphs; these generalize our results on the phase transition in inhomogeneous random graphs with clustering.

Full work available at URL: https://arxiv.org/abs/0901.2091

zbMATH Keywords

phase transitionrandom graphbranching process

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• The phase transition in inhomogeneous random graphs
• Graph limits and exchangeable random graphs
• Title not available (Why is that?)
• Moments of two-variable functions and the uniqueness of graph limits
• Asymptotic equivalence and contiguity of some random graphs
• Quasi-random graphs
• Ramanujan graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Diameters and Eigenvalues
• Quick approximation to matrices and applications
• Sparse random graphs with clustering
• Some large deviation results for sparse random graphs
• Sparse graphs: Metrics and random models
• Sparse quasi-random graphs
• Percolation on dense graph sequences
• Large‐deviations/thermodynamic approach to percolation on the complete graph
• Title not available (Why is that?)
• Metrics for sparse graphs
• Standard representation of multivariate functions on a general probability space
• Bisecting sparse random graphs

Cited In (11)

• Sparse random graphs with clustering
• Title not available (Why is that?)
• Successive minimum spanning trees
• Duality in inhomogeneous random graphs, and the cut metric
• Sparse graphs: Metrics and random models
• Balanced cut approximation in random geometric graphs
• Quasi-random graphs and graph limits
• Linear embeddings of graphs and graph limits
• Berry-Esseen bounds for generalized \(U\)-statistics
• Norms of random matrices: local and global problems
• Poset limits and exchangeable random posets

   Recommendations

• Duality in inhomogeneous random graphs, and the cut metric 👍 👎
• A probabilistic result for the max-cut problem on random graphs 👍 👎
• Random walks and local cuts in graphs 👍 👎
• Cutoff phenomena for random walks on random regular graphs 👍 👎
• On the maximal cut in a random hypergraph 👍 👎
• Cutoff for nonbacktracking random walks on sparse random graphs 👍 👎
• Extremal cuts of sparse random graphs 👍 👎
• The \(k\)-cut model in deterministic and random trees 👍 👎
• An axiomatic approach to the cut-off phenomenon for random walks on large distance-regular graphs 👍 👎

This page was built for publication: The cut metric, random graphs, and branching processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961848)