Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

DOI10.1016/j.aim.2008.07.008zbMath1213.05161arXivmath/0702004OpenAlexW2111754130WikidataQ105583577 ScholiaQ105583577MaRDI QIDQ952421

Vera T. Sós, Christian Borgs, Jennifer T. Chayes, Katalin Vesztergombi, László Lovász

Publication date: 12 November 2008

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0702004

zbMATH Keywords

sampling partition functions free energies graph sequences parameter testing cut metric Szemerédi partitions

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

Related Items

Complex networks: structure and functionality, Cut distance identifying graphon parameters over weak* limits, A problem of Erdős and Sós on 3-graphs, Finitely forcible graph limits are universal, Motif estimation via subgraph sampling: the fourth-moment phenomenon, Rare event asymptotics for exploration processes for random graphs, Bootstrapping exchangeable random graphs, Uniform estimation in stochastic block models is slow, On edge exchangeable random graphs, The local limit of the uniform spanning tree on dense graphs, Weighted exponential random graph models: scope and large network limits, Szemerédi's regularity lemma via martingales, On convergence for graphexes, A detailed investigation into near degenerate exponential random graphs, First order convergence of matroids, Densities in large permutations and parameter testing, Opinion dynamics on graphon: the piecewise constant case, Consensus and voting on large graphs: an application of graph limit theory, MAX $\kappa$-cut and the inhomogeneous Potts spin Glass, A noncommutative approach to the graphon Fourier transform, Large deviation for uniform graphs with given degrees, Estimating the number of connected components in a graph via subgraph sampling, Testing properties of graphs and functions, Replica symmetry in upper tails of mean-field hypergraphs, Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics, From quasirandom graphs to graph limits and graphlets, SVD, discrepancy, and regular structure of contingency tables, Independent sets, cliques, and colorings in graphons, First steps in combinatorial optimization on graphons: matchings, On the local approach to Sidorenko's conjecture, Estimating the distance to a hereditary graph property, Graph limits and hereditary properties, Compact orbit spaces in Hilbert spaces and limits of edge-colouring models, Stability of twisted states in the Kuramoto model on Cayley and random graphs, A short proof of the equivalence of left and right convergence for sparse graphs, Testability of minimum balanced multiway cut densities, Phase transitions in finite random networks, Recurrence of planar graph limits, Exponential Chebyshev inequalities for random graphons and their applications, Matrix and discrepancy view of generalized random and quasirandom graphs, Interval graph limits, Random graphs with a given degree sequence, Convergent sequences of dense graphs. II. Multiway cuts and statistical physics, Limits of randomly grown graph sequences, The large deviation principle for the Erdős-Rényi random graph, Quasi-random graphs and graph limits, The minimum size of 3-graphs without a 4-set spanning no or exactly three edges, Limits of kernel operators and the spectral regularity lemma, On possible Turán densities, Right-convergence of sparse random graphs, Relating the cut distance and the weak* topology for graphons, Finitely forcible graphons and permutons, Tilings in graphons, Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph, Network models: structure and function. Abstracts from the workshop held December 10--16, 2017, Quenched asymptotics for interacting diffusions on inhomogeneous random graphs, Bethe states of random factor graphs, Asymptotic distribution of Bernoulli quadratic forms, Graphon-valued stochastic processes from population genetics, On derivatives of graphon parameters, An $L^{p}$ theory of sparse graph convergence. II: LD convergence, quotients and right convergence, Chromatic roots and limits of dense graphs, A large deviation principle for the Erdős-Rényi uniform random graph, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Ensemble equivalence for dense graphs, The critical window for the classical Ramsey-Turán problem, Limits of $k$-dimensional poset sequences, Phase transitions in edge-weighted exponential random graphs: near-degeneracy and universality, Sparse maximum-entropy random graphs with a given power-law degree distribution, More on quasi-random graphs, subgraph counts and graph limits, Testing permutation properties through subpermutations, Limits of structures and the example of tree semi-lattices, Percolation on dense graph sequences, An analytic approach to stability, Finitely forcible graphons, Matching polytons, Sampling perspectives on sparse exchangeable graphs, Uniform linear embeddings of graphons, Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs, Flows on measurable spaces, On the typical structure of graphs in a monotone property, Mean-field and graph limits for collective dynamics models with time-varying weights, Large deviations of empirical neighborhood distribution in sparse random graphs, Consistent nonparametric estimation for heavy-tailed sparse graphs, Multigraph limits, unbounded kernels, and Banach space decorated graphs, Cut-norm and entropy minimization over $\text{weak}^{\ast}$ limits, Optimal graphon estimation in cut distance, Limits of sparse configuration models and beyond: graphexes and multigraphexes, Estimation of dense stochastic block models visited by random walks, Monochromatic subgraphs in randomly colored graphons, On coprime percolation, the visibility graphon, and the local limit of the GCD profile, Remarks on power-law random graphs, Compactness and finite forcibility of graphons, A reverse Sidorenko inequality, Approximating the rectilinear crossing number, Limit theorems for distributions invariant under groups of transformations, Fractional isomorphism of graphons, Matrix estimation by universal singular value thresholding, Spectral properties of modularity matrices, Singularities in the entropy of asymptotically large simple graphs, Local limits of spatial Gibbs random graphs, A counterexample to the Bollobás–Riordan conjectures on sparse graph limits, Perfect matchings, rank of connection tensors and graph homomorphisms, Universality of the mean-field for the Potts model, Random graphons and a weak Positivstellensatz for graphs, Complexity of distances: Theory of generalized analytic equivalence relations, Nonlinear large deviations, Moments of two-variable functions and the uniqueness of graph limits, Iterative Collaborative Filtering for Sparse Matrix Estimation, Graphons and renormalization of large Feynman diagrams, On replica symmetry of large deviations in random graphs, Hypergraph limits: A regularity approach, Connectivity of inhomogeneous random graphs, Upper tails and independence polynomials in random graphs, Decomposition of tournament limits, Multipodal structure and phase transitions in large constrained graphs, Uniqueness of Banach space valued graphons, Graphical Markov models for infinitely many variables, Limits of functions on groups, Modularity Maximization for Graphons, Locally common graphs, σ-algebras for quasirandom hypergraphs, A measure theoretic perspective on the space of Feynman diagrams, Transferability of graph neural networks: an extended graphon approach, Upper Tails for Edge Eigenvalues of Random Graphs, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Γ-limit of the cut functional on dense graph sequences, Continuum limit of the nonlocal p-Laplacian evolution problem on random inhomogeneous graphs, Approximating the Rectilinear Crossing Number, Poset limits and exchangeable random posets, Sparse Graphs Using Exchangeable Random Measures, First-Order Convergence and Roots, Asymptotic Structure of Graphs with the Minimum Number of Triangles, On the Lower Tail Variational Problem for Random Graphs, On Regularity Lemmas and their Algorithmic Applications, Classification on Large Networks: A Quantitative Bound via Motifs and Graphons (Research), Asymptotic behavior and distributional limits of preferential attachment graphs, Estimating and understanding exponential random graph models, On String Graph Limits and the Structure of a Typical String Graph, Regularity lemmas in a Banach space setting, Extremal results in sparse pseudorandom graphs, Small-world networks of Kuramoto oscillators, Co-clustering separately exchangeable network data, Semantic limits of dense combinatorial objects, Limits of locally-globally convergent graph sequences, The nonlinear heat equation on $W$-random graphs, Identifiability for Graphexes and the Weak Kernel Metric, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Perspectives on exponential random graphs, Sparse random graphs with clustering, Positive graphs, Optimal couplings between sparse block models, Non-Deterministic Graph Property Testing, Nonlocal $p$-Laplacian Evolution Problems on Graphs, Left and right convergence of graphs with bounded degree, An analytic approach to sparse hypergraphs: hypergraph removal, Graph fission in an evolving voter model, Unnamed Item, Sparse exchangeable graphs and their limits via graphon processes, Community Detection and Stochastic Block Models, Random Walks on Dense Graphs and Graphons, A New Bound for the 2/3 Conjecture, On the variational problem for upper tails in sparse random graphs, Unnamed Item, Resolvent of large random graphs, Testability and repair of hereditary hypergraph properties, On the asymptotics of constrained exponential random graphs, A note on permutation regularity, Sparse graphs: Metrics and random models, Modularity spectra, eigen-subspaces, and structure of weighted graphs, The cut metric, random graphs, and branching processes, Quasi-random words and limits of word sequences, Generalized quasirandom properties of expanding graph sequences, Asymptotic Structure for the Clique Density Theorem, On edge‐ordered Ramsey numbers, EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES, An introduction to large deviations for random graphs, First order limits of sparse graphs: Plane trees and path-width, Duality in inhomogeneous random graphs, and the cut metric, Local-global convergence, an analytic and structural approach, An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions, Generating Infinite Random Graphs, Unnamed Item, Weak regularity and finitely forcible graph limits, The Cut Metric for Probability Distributions, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, Book Review: Probabilistic symmetries and invariance principles, A note on random k-dimensional posets, Estimating parameters associated with monotone properties, Poset limits can be totally ordered, Emergent Structures in Large Networks, Harmonic analysis of symmetric random graphs, Graphon Mean Field Games and Their Equations, Limiting Crossing Numbers for Geodesic Drawings on the Sphere, Ground states for exponential random graphs, Linear embeddings of graphs and graph limits, Differential calculus on graphon space, A relative Szemerédi theorem, Action convergence of operators and graphs, Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers], Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon, Graph limits: An alternative approach to s‐graphons, Upper tail of the spectral radius of sparse Erdös-Rényi graphs, Graphon convergence of random cographs, Random cographs: Brownian graphon limit and asymptotic degree distribution, A limit theorem for small cliques in inhomogeneous random graphs, New Hilbert space tools for analysis of graph Laplacians and Markov processes, Fluctuations of subgraph counts in graphon based random graphs, Limits of multi-relational graphs, Fluctuations in mean-field Ising models, Approximating fractionally isomorphic graphons, Weisfeiler-Leman indistinguishability of graphons, Undecidability of polynomial inequalities in weighted graph homomorphism densities, Inference in Ising models on dense regular graphs, Long-term stability of interacting Hawkes processes on random graphs, Typical large graphs with given edge and triangle densities, Connectivity of Poissonian inhomogeneous random multigraphs, Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model, A sample-path large deviation principle for dynamic Erdős-Rényi random graphs, Propagation of chaos of forward-backward stochastic differential equations with graphon interactions, Learning sparse graphons and the generalized Kesten-Stigum threshold, Contagion in graphons, Distances and isomorphism between networks: stability and convergence of network invariants, Breaking of ensemble equivalence for dense random graphs under a single constraint, Existence of a symmetric bipodal phase in the edge-triangle model, Prominent examples of flip processes, Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons

Cites Work