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)- Non-bipartite \(k\)-common graphs
- Cut norm discontinuity of triangular truncation of graphons
- Limit theorems for exponential random graphs
- Poisson approximation of subgraph counts in stochastic block models and a graphon model
- Moments of two-variable functions and the uniqueness of graph limits
- Marked random graphs with given degree sequence: large deviations on the local topology and applications
- Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
- A general framework for Bayes structured linear models
- The number of graphs and a random graph with a given degree sequence
- Structural convergence and algebraic roots
- Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
- Forcing quasirandomness in a regular tournament
- Graphop mean-field limits for Kuramoto-type models
- Consensus and voting on large graphs: an application of graph limit theory
- A continuous model for systems of complexity 2 on simple abelian groups
- Graph similarity and homomorphism densities
- Convex graphon parameters and graph norms
- Mean-field and graph limits for collective dynamics models with time-varying weights
- Characterization of the asymptotic behaviour of U-statistics on row-column exchangeable matrices
- Poset limits can be totally ordered
- Graphon convergence of random cographs
- Estimating and understanding exponential random graph models
- Weak regularity and finitely forcible graph limits
- Parameter testing in bounded degree graphs of subexponential growth
- Superlogarithmic cliques in dense inhomogeneous random graphs
- On the variational problem for upper tails in sparse random graphs
- Connectivity of inhomogeneous random graphs
- Upper tail of the spectral radius of sparse Erdös-Rényi graphs
- Right-convergence of sparse random graphs
- Existence of a symmetric bipodal phase in the edge-triangle model
- The large deviation principle for interacting dynamical systems on random graphs
- Spectral classes of regular, random, and empirical graphs
- Edge-reflection positivity and weighted graph homomorphisms
- Limit of a nonpreferential attachment multitype network model
- A relative Szemerédi theorem
- A graphon perspective for fractional isomorphism
- Theory of limits of sequences of Latin squares
- A PROBABILISTIC FRIENDSHIP NETWORK MODEL
- Asymptotic behavior of common connections in sparse random networks
- 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
- An introduction to large deviations for random graphs
- On network-based epidemiological models: analysis, simulations, and continuum limit
- Asymptotic Structure for the Clique Density Theorem
- Nonlocal p-Laplacian evolution problems on graphs
- Testing properties of graphs and functions
- Densities in large permutations and parameter testing
- Generalized quasirandom graphs
- Relating the cut distance and the weak* topology for graphons
- Thresholds for virus spread on networks
- Parabolic theory of the discrete p-Laplace operator
- Local-global convergence, an analytic and structural approach
- An infinite-dimensional metapopulation SIS model
- Relatively exchangeable structures
- On sparsity, power-law, and clustering properties of graphex processes
- Restricted problems in extremal combinatorics
- Uniform linear embeddings of graphons
- Toward characterizing locally common graphs
- A limit theorem for small cliques in inhomogeneous random graphs
- Measures on the square as sparse graph limits
- Optimal graphon estimation in cut distance
- Finitely forcible graphons and permutons
- Locally common graphs
- Mean field limits of co-evolutionary signed heterogeneous networks
- Forcing generalised quasirandom graphs efficiently
- Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
- Tripodal structure in undersaturated random graphs
- Motif-based tests for bipartite networks
- A noncommutative approach to the graphon Fourier transform
- Graph limits: An alternative approach to s‐graphons
- On Sidorenko's conjecture for determinants and Gaussian Markov random fields
- Power network dynamics on graphons
- Cliques in rank-1 random graphs: the role of inhomogeneity
- Bayesian modeling of the structural connectome for studying Alzheimer's disease
- Testing permutation properties through subpermutations
- Analysis and approximation of a fractional Laplacian-based closure model for turbulent flows and its connection to Richardson pair dispersion
- Multigraph limits, unbounded kernels, and Banach space decorated graphs
- The GHP scaling limit of uniform spanning trees of dense graphs
- Normal to Poisson phase transition for subgraph counting in the random-connection model
- Classification on large networks: a quantitative bound via motifs and graphons (research)
- Quenched asymptotics for interacting diffusions on inhomogeneous random graphs
- Asymptotic behavior and distributional limits of preferential attachment graphs
- Model-based clustering of multiple networks with a hierarchical algorithm
- Extremal results in sparse pseudorandom graphs
- A note on Fokker-Planck equations and graphons
- Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
- Dense graph limits under respondent-driven sampling
- Conformal Prediction for Network-Assisted Regression
- More on quasi-random graphs, subgraph counts and graph limits
- On limits of finite graphs
- Prominent examples of flip processes
- Graph invariants in the spin model
- Population dynamics and statistical physics in synergy. Abstracts from the workshop held March 6--12, 2022
- An equation-free approach to coarse-graining the dynamics of networks
- A graphon counter example
- Asymptotic dynamics of non-autonomous fractional reaction-diffusion equations on bounded domains
- The large deviation principle for the Erdős-Rényi random graph
- Harmonic analysis of symmetric 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)
