Limits of dense graph sequences
From MaRDI portal
Publication:859618
DOI10.1016/J.JCTB.2006.05.002zbMATH Open1113.05092arXivmath/0408173OpenAlexW2082734581WikidataQ56503928 ScholiaQ56503928MaRDI QIDQ859618FDOQ859618
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)
- Graphop Mean-Field Limits for Kuramoto-Type Models
- An Optimization Parameter for Seriation of Noisy Data
- Simple graph density inequalities with no sum of squares proofs
- 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
- Cut distance identifying graphon parameters over weak* limits
- Power Network Dynamics on Graphons
- Posterior contraction rates for stochastic block models
- A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Reconstruction of line-embeddings of graphons
- Sparse maximum-entropy random graphs with a given power-law degree distribution
- Determination of the reaction coefficient in a time dependent nonlocal diffusion process
- Action convergence of operators and graphs
- Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
- 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 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
- On the Lower Tail Variational Problem for Random Graphs
- Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
- The Cut Metric for Probability Distributions
- Limits of sparse configuration models and beyond: graphexes and multigraphexes
- Stability from graph symmetrisation arguments with applications to inducibility
- 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
- Graphon Mean Field Games and Their Equations
- Compactness by Coarse-Graining in long-range lattice systems
- RELATIVELY EXCHANGEABLE STRUCTURES
- Bethe states of random factor graphs
- On the maximum density of fixed strongly connected subtournaments
- Finite reflection groups and graph norms
- Graphon-valued stochastic processes from population genetics
- Relational exchangeability
- A note on random \(k\)-dimensional posets
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Combinatorial Lévy processes
- Uniqueness of Banach space valued graphons
- Sampling perspectives on sparse exchangeable graphs
- The role of topology in large deviations
- A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
- Convergence and stability of generalized gradient systems by Łojasiewicz inequality with application in continuum Kuramoto model
- Limits of \(k\)-dimensional poset sequences
- Identifiability for Graphexes and the Weak Kernel Metric
- Ensemble equivalence for dense graphs
- 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
- Remarks on power-law random graphs
- Title not available (Why is that?)
- Flows on measurable spaces
- Generating hierarchial scale-free graphs from fractals
- Ground states for exponential random graphs
- A Rainbow Erdös--Rothschild Problem
- Regularity lemmas in a Banach space setting
- Using the bootstrap for statistical inference on random graphs
- Upper tails and independence polynomials in random graphs
- Graph limits and hereditary properties
- Consensus and voting on large graphs: an application of graph limit theory
- A continuous model for systems of complexity 2 on simple abelian groups
- A PROBABILISTIC FRIENDSHIP NETWORK MODEL
- Parameter testing in bounded degree graphs of subexponential growth
- Limit of a nonpreferential attachment multitype network model
- Spectral classes of regular, random, and empirical graphs
- 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
- On Sidorenko's conjecture for determinants and Gaussian Markov random fields
- Upper Tails for Edge Eigenvalues of Random Graphs
- A note on Fokker-Planck equations and graphons
- Population dynamics and statistical physics in synergy. Abstracts from the workshop held March 6--12, 2022
- Cycles of length three and four in tournaments
- A note on permutation regularity
- Graphons and renormalization of large Feynman diagrams
- First steps in combinatorial optimization on graphons: matchings
- Limits of functions on groups
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)
