Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
From MaRDI portal
Publication:313432
Abstract: We define the chromatic measure of a finite simple graph as the uniform distribution on its chromatic roots. We show that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. As a corollary, for a convergent sequence of finite graphs, we prove that the normalized log of the chromatic polynomial converges to an analytic function outside a bounded disc. This generalizes a recent result of Borgs, Chayes, Kahn and Lov'asz, who proved convergence at large enough positive integers and answers a question of Borgs. Our methods also lead to explicit estimates on the number of proper colorings of graphs with large girth.
Recommendations
- Benjamini-Schramm continuity of root moments of graph polynomials
- Convergence of graphs with intermediate density
- Chromatic roots and limits of dense graphs
- On limits of sparse random graphs
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- The continuum random tree is the scaling limit of unlabeled unrooted trees
- The concentration of the chromatic number of random graphs
- scientific article; zbMATH DE number 1380613
Cites work
- scientific article; zbMATH DE number 3094412 (Why is no real title available?)
- Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
- Asymptotic Enumeration of Spanning Trees
- Benjamini-Schramm continuity of root moments of graph polynomials
- Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Large networks and graph limits
- Left and right convergence of graphs with bounded degree
- On the foundations of combinatorial theory I. Theory of M�bius Functions
- Potts model on infinite graphs and the limit of chromatic polynomials
- Recurrence of distributional limits of finite planar graphs
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
- Transfer matrices and partition-function zeros for antiferromagnetic Potts models. V. Further results for the square-lattice chromatic polynomial
Cited in
(17)- Chromatic polynomials of \(K_m+P_n\), \(K_m+C_n\) and \(G\circ H\)
- Chromatic roots and limits of dense graphs
- CHROMATIC POLYNOMIALS OF n-CENTIPEDE AND TRIANGULAR SNAKE TSn GRAPHS
- scientific article; zbMATH DE number 7593849 (Why is no real title available?)
- Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Convergence of graphs with intermediate density
- Random cluster model on regular graphs
- The distribution of sandpile groups of random regular graphs
- Evaluations of Tutte polynomials of regular graphs
- Unimodular measures on the space of all Riemannian manifolds
- Statistical Matching Theory
- Characteristic power series of graph limits
- Matchings in Benjamini-Schramm convergent graph sequences
- Sidorenko's conjecture, colorings and independent sets
- Benjamini-Schramm continuity of root moments of graph polynomials
- Limits of locally-globally convergent graph sequences
This page was built for publication: Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313432)
