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

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

László Lovász, 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

New Hilbert space tools for analysis of graph Laplacians and Markov processes, Fluctuations of subgraph counts in graphon based random graphs, Fluctuations in mean-field Ising models, 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, 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, Distances and isomorphism between networks: stability and convergence of network invariants, Subgraph densities in Markov spaces, Breaking of ensemble equivalence for dense random graphs under a single constraint, 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

Cites Work