Limits of dense graph sequences
From MaRDI portal
Publication:859618
DOI10.1016/J.JCTB.2006.05.002zbMATH Open1113.05092OpenAlexW2082734581WikidataQ56503928 ScholiaQ56503928MaRDI QIDQ859618FDOQ859618
Authors: Balázs Szegedy, László Lovász 
Publication date: 16 January 2007
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We show that if a sequence of dense graphs has the property that for every fixed graph F, the density of copies of F in these graphs tends to a limit, then there is a natural ``limit object, namely a symmetric measurable 2-variable function on [0,1]. This limit object determines all the limits of subgraph densities. We also show that the graph parameters obtained as limits of subgraph densities can be characterized by ``reflection positivity, semidefiniteness of an associated matrix. Conversely, every such function arises as a limit object. Along the lines we introduce a rather general model of random graphs, which seems to be interesting on its own right.
Full work available at URL: https://arxiv.org/abs/math/0408173
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymptotic Enumeration of Spanning Trees
- Operations with structures
- Quasi-random graphs
- Quick approximation to matrices and applications
- Recurrence of distributional limits of finite planar graphs
- Tricks or Treats with the Hilbert Matrix
Cited In (only showing first 100 items - show all)
- The entropy of random-free graphons and properties
- Sparse random graphs with clustering
- Consistency under sampling of exponential random graph models
- Maximum likelihood estimation in the \(\beta\)-model
- On replica symmetry of large deviations in random graphs
- Community detection and stochastic block models: recent developments
- SVD, discrepancy, and regular structure of contingency tables
- INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
- Random graphs with a given degree sequence
- Testability and repair of hereditary hypergraph properties
- Hypergraph limits: A regularity approach
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- A measure-theoretic approach to the theory of dense hypergraphs
- Resolvent of large random graphs
- Generalizations of the removal lemma
- Dynamic network models and graphon estimation
- A characterization of functions with vanishing averages over products of disjoint sets
- Matrix estimation by universal singular value thresholding
- Edge coloring models and reflection positivity
- The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator
- The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
- From quasirandom graphs to graph limits and graphlets
- Time-varying network models
- On possible Turán densities
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Dynamic random networks and their graph limits
- Convergence of graphs with intermediate density
- On the asymptotics of constrained exponential random graphs
- Counting graph homomorphisms
- Modularity Maximization for Graphons
- Independence densities of hypergraphs
- A new bound for the 2/3 conjecture
- On the Fon-Der-Flaass interpretation of extremal examples for Turán's \((3,4)\)-problem
- Recurrence of planar graph limits
- A detailed investigation into near degenerate exponential random graphs
- σ-algebras for quasirandom hypergraphs
- Phase transitions in exponential random graphs
- Finitely forcible graphons with an almost arbitrary structure
- Multivariate Hawkes processes on inhomogeneous random graphs
- Chromatic roots and limits of dense graphs
- Poset limits can be totally ordered
- Moments of two-variable functions and the uniqueness of graph limits
- Structural limits and approximations of mappings
- Uniform linear embeddings of spatial random graphs
- First order convergence of matroids
- Weak regularity and finitely forcible graph limits
- On the variational problem for upper tails in sparse random graphs
- Estimating and understanding exponential random graph models
- A relative Szemerédi theorem
- Generalized quasirandom graphs
- Testing properties of graphs and functions
- Uniform linear embeddings of graphons
- Analysis and approximation of a fractional Laplacian-based closure model for turbulent flows and its connection to Richardson pair dispersion
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Extremal results in sparse pseudorandom graphs
- More on quasi-random graphs, subgraph counts and graph limits
- Model-based clustering of multiple networks with a hierarchical algorithm
- On limits of finite graphs
- Graph invariants in the spin model
- The large deviation principle for the Erdős-Rényi random graph
- Rate-optimal graphon estimation
- Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality
- Exchangeable graph-valued Feller processes
- Finitely forcible graph limits are universal
- Linear embeddings of graphs and graph limits
- A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems
- Interval graph limits
- Extremal graph theory and finite forcibility
- An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- Sparse graphs: metrics and random models
- Mixed Membership Estimation for Social Networks
- Why Are Big Data Matrices Approximately Low Rank?
- Limits of structures and the example of tree semi-lattices
- The phase transition in inhomogeneous random graphs
- Singularities in the entropy of asymptotically large simple graphs
- Multipodal structure and phase transitions in large constrained graphs
- Critical phenomena in exponential random graphs
- Finitely forcible graphons
- Compactness and finite forcibility of graphons
- Quasirandom permutations are characterized by 4-point densities
- Limits of mappings
- Poset limits and exchangeable random posets
- Limits of locally-globally convergent graph sequences
- Stability of twisted states in the Kuramoto model on Cayley and random graphs
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Undecidability of linear inequalities in graph homomorphism densities
- Limits of kernel operators and the spectral regularity lemma
- Quasi-random words and limits of word sequences
- Graph norms and Sidorenko's conjecture
- On the Caccetta-Häggkvist conjecture with forbidden subgraphs
- The automorphism group of a graphon
- Continuum limits for classical sequential growth models
- A large deviation principle for the Erdős-Rényi uniform random graph
- Testability of minimum balanced multiway cut densities
- Tilings in graphons
- The Kuramoto model on power law graphs: synchronization and contrast states
- Differential calculus on graphon space
- Books versus triangles
- Monotone graph limits and quasimonotone graphs
- Contractors and connectors of graph algebras
This page was built for publication: Limits of dense graph sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859618)
