Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs

DOI10.1007/S00493-014-3066-7zbMATH Open1363.05118arXiv1201.3861OpenAlexW2009398469MaRDI QIDQ313432FDOQ313432

Authors: Miklós Abért, Tamás Hubai 

Publication date: 9 September 2016

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

weak convergencegirthBenjamini-Schramm convergencechromatic measure

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Large networks and graph limits
• Asymptotic Enumeration of Spanning Trees
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Title not available (Why is that?)
• Potts model on infinite graphs and the limit of chromatic polynomials
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. V. Further results for the square-lattice chromatic polynomial
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Left and right convergence of graphs with bounded degree
• Benjamini-Schramm continuity of root moments of graph polynomials

Cited In (17)

• Unimodular measures on the space of all Riemannian manifolds
• Characteristic power series of graph limits
• Zero-free regions of partition functions with applications to algorithms and graph limits
• The distribution of sandpile groups of random regular graphs
• Convergence of graphs with intermediate density
• Matchings in Benjamini-Schramm convergent graph sequences
• Chromatic roots and limits of dense graphs
• Chromatic polynomials of \(K_m+P_n\), \(K_m+C_n\) and \(G\circ H\)
• Benjamini-Schramm continuity of root moments of graph polynomials
• Statistical Matching Theory
• Title not available (Why is that?)
• Random cluster model on regular graphs
• Evaluations of Tutte polynomials of regular graphs
• Sidorenko's conjecture, colorings and independent sets
• CHROMATIC POLYNOMIALS OF n-CENTIPEDE AND TRIANGULAR SNAKE TSn GRAPHS
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• 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)