The cut metric, random graphs, and branching processes
From MaRDI portal
Publication:5961848
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.
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
Cites work
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 795107 (Why is no real title available?)
- Asymptotic equivalence and contiguity of some random graphs
- Bisecting sparse random 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
- Graph limits and exchangeable random graphs
- Large‐deviations/thermodynamic approach to percolation on the complete graph
- Limits of dense graph sequences
- Metrics for sparse graphs
- Moments of two-variable functions and the uniqueness of graph limits
- Percolation on dense graph sequences
- Quasi-random graphs
- Quick approximation to matrices and applications
- Ramanujan graphs
- Some large deviation results for sparse random graphs
- Sparse graphs: metrics and random models
- Sparse quasi-random graphs
- Sparse random graphs with clustering
- Standard representation of multivariate functions on a general probability space
- The phase transition in inhomogeneous random graphs
Cited in
(13)- Berry-Esseen bounds for generalized \(U\)-statistics
- Quasi-random graphs and graph limits
- Successive minimum spanning trees
- The phase transition in inhomogeneous random graphs
- Susceptibility in inhomogeneous random graphs
- Linear embeddings of graphs and graph limits
- Balanced cut approximation in random geometric graphs
- Sparse random graphs with clustering
- scientific article; zbMATH DE number 7651049 (Why is no real title available?)
- Sparse graphs: metrics and random models
- Duality in inhomogeneous random graphs, and the cut metric
- Poset limits and exchangeable random posets
- Norms of random matrices: local and global problems
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)
