Limits of dense graph sequences
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 3722700 (Why is no real title available?)
- 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)- Fractional isomorphism of graphons
- Cut distance identifying graphon parameters over weak* limits
- Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
- On the maximum density of fixed strongly connected subtournaments
- Asymptotic behavior of common connections in sparse random networks
- Convex graphon parameters and graph norms
- Mean-field and graph limits for collective dynamics models with time-varying weights
- Ground states for exponential random graphs
- A discrete districting plan
- Complete positivity and distance-avoiding sets
- Two remarks on graph norms
- Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
- Vlasov equations on digraph measures
- Graphon mean field games and their equations
- An infinite-dimensional metapopulation SIS model
- Graph limits: An alternative approach to s‐graphons
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- The cut metric for probability distributions
- Higher-order fluctuations in dense random graph models
- Interacting diffusions on random graphs with diverging average degrees: hydrodynamics and large deviations
- Non-bipartite \(k\)-common graphs
- Reconstruction of line-embeddings of graphons
- Remarks on power-law random graphs
- Graphop mean-field limits for Kuramoto-type models
- Cut norm discontinuity of triangular truncation of graphons
- An optimization parameter for seriation of noisy data
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- Measures on the square as sparse graph limits
- On the lower tail variational problem for random graphs
- Sampling perspectives on sparse exchangeable graphs
- Optimal graphon estimation in cut distance
- Graphon convergence of random cographs
- Decomposition of tournament limits
- Action convergence of operators and graphs
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- A unified approach to structural limits and limits of graphs with bounded tree-depth
- Sublinear-time quadratic minimization via spectral decomposition of matrices
- A graphon counter example
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Relating the cut distance and the weak* topology for graphons
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- The large deviation principle for interacting dynamical systems on random graphs
- Asymptotic dynamics of non-autonomous fractional reaction-diffusion equations on bounded domains
- Posterior contraction rates for stochastic block models
- Characteristic power series of graph limits
- On the length of the shortest path in a sparse Barak-Erdős graph
- Stability from graph symmetrisation arguments with applications to inducibility
- A general framework for Bayes structured linear models
- Determination of the reaction coefficient in a time dependent nonlocal diffusion process
- Minimizing the number of 5-cycles in graphs with given edge-density
- Convergence and limits of finite trees
- Limits of \(k\)-dimensional poset sequences
- A noncommutative approach to the graphon Fourier transform
- Limit theorems for distributions invariant under groups of transformations
- Random graph asymptotics for treatment effect estimation under network interference
- The mean field analysis of the Kuramoto model on graphs. I: The mean field equation and transition point formulas
- The step Sidorenko property and non-norming edge-transitive graphs
- The local limit of the uniform spanning tree on dense graphs
- Uniqueness of Banach space valued graphons
- Edge exchangeable models for interaction networks
- Berry-Esseen bounds for generalized \(U\)-statistics
- Matching polytons
- Sparse graphs using exchangeable random measures
- Bethe states of random factor graphs
- Population dynamics and statistical physics in synergy. Abstracts from the workshop held March 6--12, 2022
- Consensus and voting on large graphs: an application of graph limit theory
- A continuous model for systems of complexity 2 on simple abelian groups
- Relational exchangeability
- Reduced basis methods for nonlocal diffusion problems with random input data
- Compactness by Coarse-Graining in long-range lattice systems
- Ensemble equivalence for dense graphs
- Cycles of length three and four in tournaments
- First steps in combinatorial optimization on graphons: matchings
- On Sidorenko's conjecture for determinants and Gaussian Markov random fields
- Using the bootstrap for statistical inference on random graphs
- A PROBABILISTIC FRIENDSHIP NETWORK MODEL
- Parameter testing in bounded degree graphs of subexponential growth
- \(\Gamma\)-limit of the cut functional on dense graph sequences
- Continuum limits of nonlocal \(p\)-Laplacian variational problems on graphs
- A rainbow Erdös-Rothschild problem
- A note on permutation regularity
- On the typical structure of graphs in a monotone property
- Phase transitions in finite random networks
- Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
- Graphons and renormalization of large Feynman diagrams
- Flows on measurable spaces
- Compact orbit spaces in Hilbert spaces and limits of edge-colouring models
- First-order limits, an analytical perspective
- Invariant measures via inverse limits of finite structures
- Asymptotic symmetries for fractional operators
- Combinatorial Lévy processes
- Graph limits and hereditary properties
- Finite reflection groups and graph norms
- Limits of order types
- Upper tails and independence polynomials in random graphs
- Limits of random trees. II
- On the boundary of the region defined by homomorphism densities
- Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality
- The role of topology in large deviations
- A sample-path large deviation principle for dynamic Erdős-Rényi random 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)
