Convergent sequences of dense graphs. II. Multiway cuts and statistical physics

DOI10.4007/ANNALS.2012.176.1.2zbMath1247.05124OpenAlexW2137365113WikidataQ105584519 ScholiaQ105584519MaRDI QIDQ447926

Christian Borgs, Katalin Vesztergombi, Vera T. Sós, Jennifer T. Chayes

Publication date: 30 August 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4007/annals.2012.176.1.2

zbMATH Keywords

regularity lemma statistical physics graph limits left and right convergence of graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42)

Related Items (only showing first 100 items - show all)

Complex networks: structure and functionality ⋮ Local limits of spatial Gibbs random graphs ⋮ A problem of Erdős and Sós on 3-graphs ⋮ Universality of the mean-field for the Potts model ⋮ Finitely forcible graph limits are universal ⋮ Compactness by Coarse-Graining in long-range lattice systems ⋮ Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ Rare event asymptotics for exploration processes for random graphs ⋮ Nonlinear large deviations ⋮ On edge exchangeable random graphs ⋮ Weighted exponential random graph models: scope and large network limits ⋮ On convergence for graphexes ⋮ A detailed investigation into near degenerate exponential random graphs ⋮ First order convergence of matroids ⋮ Graphons and renormalization of large Feynman diagrams ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ Densities in large permutations and parameter testing ⋮ Hypergraph limits: A regularity approach ⋮ 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 ⋮ Connectivity of inhomogeneous random graphs ⋮ Upper tails and independence polynomials in random graphs ⋮ Decomposition of tournament limits ⋮ Replica symmetry in upper tails of mean-field hypergraphs ⋮ Uniqueness of Banach space valued graphons ⋮ Graphical Markov models for infinitely many variables ⋮ Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics ⋮ Maximum spread of graphs and bipartite graphs ⋮ A measure theoretic perspective on the space of Feynman diagrams ⋮ Graph limits: An alternative approach to s‐graphons ⋮ Transferability of graph neural networks: an extended graphon approach ⋮ Graphon convergence of random cographs ⋮ Upper Tails for Edge Eigenvalues of Random Graphs ⋮ Graph limits and hereditary properties ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Γ-limit of the cut functional on dense graph sequences ⋮ A short proof of the equivalence of left and right convergence for sparse graphs ⋮ Poset limits and exchangeable random posets ⋮ Convergence of graphs with intermediate density ⋮ Exponential Chebyshev inequalities for random graphons and their applications ⋮ Matrix and discrepancy view of generalized random and quasirandom graphs ⋮ First-Order Convergence and Roots ⋮ On the Lower Tail Variational Problem for Random Graphs ⋮ Classification on Large Networks: A Quantitative Bound via Motifs and Graphons (Research) ⋮ Random graphs with a given degree sequence ⋮ Asymptotic behavior and distributional limits of preferential attachment graphs ⋮ Estimating and understanding exponential random graph models ⋮ Co-clustering separately exchangeable network data ⋮ Right-convergence of sparse random graphs ⋮ Relating the cut distance and the weak* topology for graphons ⋮ Finitely forcible graphons and permutons ⋮ Limits of locally-globally convergent graph sequences ⋮ Identifiability for Graphexes and the Weak Kernel Metric ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Perspectives on exponential random graphs ⋮ 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 ⋮ Sparse random graphs with clustering ⋮ Left and right convergence of graphs with bounded degree ⋮ Asymptotic distribution of Bernoulli quadratic forms ⋮ An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence ⋮ Ensemble equivalence for dense graphs ⋮ More on quasi-random graphs, subgraph counts and graph limits ⋮ Limits of structures and the example of tree semi-lattices ⋮ Percolation on dense graph sequences ⋮ On the asymptotics of constrained exponential random graphs ⋮ Sampling perspectives on sparse exchangeable graphs ⋮ Sparse graphs: Metrics and random models ⋮ A transportation approach to the mean-field approximation ⋮ Modularity spectra, eigen-subspaces, and structure of weighted graphs ⋮ Uniform linear embeddings of graphons ⋮ Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs ⋮ Flows on measurable spaces ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ 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 ⋮ An introduction to large deviations for random graphs ⋮ First order limits of sparse graphs: Plane trees and path-width ⋮ Local-global convergence, an analytic and structural approach ⋮ An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions ⋮ Measures on the square as sparse graph 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 ⋮ Weak regularity and finitely forcible graph limits ⋮ Monochromatic subgraphs in randomly colored graphons ⋮ The Cut Metric for Probability Distributions ⋮ Remarks on power-law random graphs ⋮ Compactness and finite forcibility of graphons ⋮ Fractional isomorphism of graphons ⋮ Matrix estimation by universal singular value thresholding ⋮ Cycles of a given length in tournaments ⋮ Graphon Mean Field Games and Their Equations ⋮ Ground states for exponential random graphs ⋮ Linear embeddings of graphs and graph limits ⋮ Differential calculus on graphon space ⋮ New Hilbert space tools for analysis of graph Laplacians and Markov processes

Cites Work

This page was built for publication: Convergent sequences of dense graphs. II. Multiway cuts and statistical physics