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)- Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality
- Poset limits and exchangeable random posets
- Glauber dynamics for Ising model on convergent dense graph sequences
- Stability of twisted states in the Kuramoto model on Cayley and random graphs
- Identifiability for graphexes and the weak kernel metric
- Limits of locally-globally convergent graph sequences
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- Upper tails for edge eigenvalues of random graphs
- Optimal investment in a large population of competitive and heterogeneous agents
- The entropy of random-free graphons and properties
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Propagation of chaos of forward-backward stochastic differential equations with graphon interactions
- Consistency under sampling of exponential random graph models
- Maximum likelihood estimation in the -model
- Gadget construction and structural convergence
- Sparse random graphs with clustering
- Characteristic power series of graph limits
- Compactness by Coarse-Graining in long-range lattice systems
- Semantic limits of dense combinatorial objects
- On the lower tail variational problem for random graphs
- Undecidability of linear inequalities in graph homomorphism densities
- On graph norms for complex‐valued functions
- Long-term stability of interacting Hawkes processes on random graphs
- Positive graphs
- SVD, discrepancy, and regular structure of contingency tables
- On replica symmetry of large deviations in random graphs
- Continuum limit of the nonlocal \(p\)-Laplacian evolution problem on random inhomogeneous graphs
- Limits of kernel operators and the spectral regularity lemma
- Random graphs with a given degree sequence
- Bethe states of random factor graphs
- On the maximum density of fixed strongly connected subtournaments
- Community detection and stochastic block models: recent developments
- Stochastic Block Smooth Graphon Model
- Simple graph density inequalities with no sum of squares proofs
- Infinite horizon LQG graphon mean field games: explicit Nash values and local minima
- Finite reflection groups and graph norms
- Decomposition of tournament limits
- Graphon-valued stochastic processes from population genetics
- Testability and repair of hereditary hypergraph properties
- The dimension of the feasible region of pattern densities
- INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
- Graph sequences sampled from Robinson graphons
- Sparse Monte Carlo method for nonlocal diffusion problems
- Natural quasirandomness properties
- On the continuum limit of epidemiological models on graphs: convergence and approximation results
- Quasi-random words and limits of word sequences
- Hypergraph limits: A regularity approach
- Mean-field limit of non-exchangeable systems
- Graph norms and Sidorenko's conjecture
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- A measure-theoretic approach to the theory of dense hypergraphs
- Complete positivity and distance-avoiding sets
- Two remarks on graph norms
- A discrete districting plan
- The automorphism group of a graphon
- The devil's staircase for chip-firing on random graphs and on graphons
- Interacting diffusions on random graphs with diverging average degrees: hydrodynamics and large deviations
- Generalizations of the removal lemma
- Exchangeability, prediction and predictive modeling in Bayesian statistics
- On the Caccetta-Häggkvist conjecture with forbidden subgraphs
- Relational exchangeability
- Weak randomness in graphons and theons
- A note on random k-dimensional posets
- A characterization of functions with vanishing averages over products of disjoint sets
- Resolvent of large random graphs
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator
- Dynamic network models and graphon estimation
- Minimizing the number of 5-cycles in graphs with given edge-density
- Matrix estimation by universal singular value thresholding
- Combinatorial Lévy processes
- The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
- Spectral properties for the Laplacian of a generalized Wigner matrix
- The large deviation principle for W-random spectral measures
- From quasirandom graphs to graph limits and graphlets
- Edge coloring models and reflection positivity
- Testability of minimum balanced multiway cut densities
- The cut metric for probability distributions
- Continuum limits for classical sequential growth models
- A large deviation principle for the Erdős-Rényi uniform random graph
- Cut distance identifying graphon parameters over weak* limits
- Uniqueness of Banach space valued graphons
- Rooting algebraic vertices of convergent sequences (extended abstract)
- Forcing generalized quasirandom graphs efficiently (extended abstract)
- The dimension of the feasible region of pattern densities (extended abstract)
- The role of topology in large deviations
- First-Order Convergence and Roots
- Sampling perspectives on sparse exchangeable graphs
- Limits of random trees. II
- Sampling random graph homomorphisms and applications to network data analysis
- Tilings in graphons
- The Kuramoto model on power law graphs: synchronization and contrast states
- Posterior contraction rates for stochastic block models
- Bounds on the mod 2 homology of random 2-dimensional determinantal hypertrees
- Time-varying network models
- Probability-graphons: limits of large dense weighted graphs
- Consensus formation in first-order graphon models with time-varying topologies
- On possible Turán densities
- Typical large graphs with given edge and triangle densities
- Random homomorphisms into the orthogonality graph
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)
