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
- On the maximum density of fixed strongly connected subtournaments
- Decomposition of tournament limits
- 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
- 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
- A noncommutative approach to the graphon Fourier transform
- 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
- A graphon counter example
- Asymptotic dynamics of non-autonomous fractional reaction-diffusion equations on bounded domains
- On the length of the shortest path in a sparse Barak-Erdős graph
- 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
- 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
- An analytic approach to stability
- Small-world networks of Kuramoto oscillators
- Pentagons in triangle-free graphs
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- Multigraph limit of the dense configuration model and the preferential attachment graph
- Multigraph limits and exchangeability
- Limits of randomly grown graph sequences
- Limits of Boolean functions on \(\mathbb{F}_p^n\)
- The inducibility of blow-up graphs
- The number of graphs and a random graph with a given degree sequence
- Connectivity of inhomogeneous random graphs
- Asymptotic Structure for the Clique Density Theorem
- Nonlocal \(p\)-Laplacian evolution problems on graphs
- Right-convergence of sparse random graphs
- Edge-reflection positivity and weighted graph homomorphisms
- An introduction to large deviations for random graphs
- Local-global convergence, an analytic and structural approach
- Thresholds for virus spread on networks
- Densities in large permutations and parameter testing
- Parabolic theory of the discrete \(p\)-Laplace operator
- Motif-based tests for bipartite networks
- Finitely forcible graphons and permutons
- Testing permutation properties through subpermutations
- Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
- Dense graph limits under respondent-driven sampling
- A note on permutation regularity
- An equation-free approach to coarse-graining the dynamics of networks
- A new lower bound based on Gromov's method of selecting heavily covered points
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)
