Limits of dense graph sequences
From MaRDI portal
Publication:859618
DOI10.1016/J.JCTB.2006.05.002zbMATH Open1113.05092arXivmath/0408173OpenAlexW2082734581WikidataQ56503928 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
- Recurrence of distributional limits of finite planar graphs
- Asymptotic Enumeration of Spanning Trees
- Title not available (Why is that?)
- Quasi-random graphs
- Tricks or Treats with the Hilbert Matrix
- Quick approximation to matrices and applications
- Title not available (Why is that?)
- Operations with structures
Cited In (only showing first 100 items - show all)
- On the lower tail variational problem for random graphs
- Characteristic power series of graph limits
- Bethe states of random factor graphs
- On the maximum density of fixed strongly connected subtournaments
- Decomposition of tournament limits
- Graphon-valued stochastic processes from population genetics
- A discrete districting plan
- Complete positivity and distance-avoiding sets
- Two remarks on graph norms
- Interacting diffusions on random graphs with diverging average degrees: hydrodynamics and large deviations
- Minimizing the number of 5-cycles in graphs with given edge-density
- The cut metric for probability distributions
- Uniqueness of Banach space valued graphons
- Cut distance identifying graphon parameters over weak* limits
- Sampling perspectives on sparse exchangeable graphs
- Posterior contraction rates for stochastic block models
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Limits of \(k\)-dimensional poset sequences
- Reconstruction of line-embeddings of graphons
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Remarks on power-law random graphs
- Determination of the reaction coefficient in a time dependent nonlocal diffusion process
- Graphon mean field games and their equations
- Action convergence of operators and graphs
- Ground states for exponential random graphs
- An optimization parameter for seriation of noisy data
- Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
- Graphop mean-field limits for Kuramoto-type models
- Non-bipartite \(k\)-common graphs
- Cut norm discontinuity of triangular truncation of graphons
- Graphon convergence of random cographs
- A general framework for Bayes structured linear models
- Convex graphon parameters and graph norms
- Mean-field and graph limits for collective dynamics models with time-varying weights
- The large deviation principle for interacting dynamical systems on random graphs
- Asymptotic behavior of common connections in sparse random networks
- Relating the cut distance and the weak* topology for graphons
- Graph limits: An alternative approach to s‐graphons
- An infinite-dimensional metapopulation SIS model
- Measures on the square as sparse graph limits
- Optimal graphon estimation in cut distance
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- A unified approach to structural limits and limits of graphs with bounded tree-depth
- On the length of the shortest path in a sparse Barak-Erdős graph
- A note on permutation regularity
- Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Stability from graph symmetrisation arguments with applications to inducibility
- Sublinear-time quadratic minimization via spectral decomposition of matrices
- Higher-order fluctuations in dense random graph models
- Convergence and limits of finite trees
- Vlasov equations on digraph measures
- Limit theorems for distributions invariant under groups of transformations
- Random graph asymptotics for treatment effect estimation under network interference
- Fractional isomorphism of graphons
- Reduced basis methods for nonlocal diffusion problems with random input data
- On the boundary of the region defined by homomorphism densities
- 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
- Generalizations of the removal lemma
- Dynamic network models and graphon estimation
- A characterization of functions with vanishing averages over products of disjoint sets
- Identification of the diffusion parameter in nonlocal steady diffusion problems
- 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
- A problem of Erdős and Sós on 3-graphs
- Recurrence of planar graph limits
- An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
- 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
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)
