Benjamini-Schramm continuity of root moments of graph polynomials

DOI10.1016/J.EJC.2015.07.009zbMATH Open1327.05159arXiv1204.0463OpenAlexW1541384556MaRDI QIDQ896079FDOQ896079

Authors: Péter Csikvári, Péter E. Frenkel 

Publication date: 11 December 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Recently, M. Ab'ert and T. Hubai studied the following problem. The chromatic measure of a finite simple graph is defined to be the uniform distribution on its chromatic roots. Ab'ert and Hubai proved that for a Benjamini-Schramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. They also showed that the normalized log of the chromatic polynomial converges to a harmonic real function outside a bounded disc. In this paper we generalize their work to a wide class of graph polynomials, namely, multiplicative graph polynomials of bounded exponential type. A special case of our results is that for any fixed complex number $v_0$ the measures arising from the Tutte polynomial $Z_{G_n}(z,v_0)$ converge in holomorphic moments if the sequence $(G_n)$ of finite graphs is Benjamini--Schramm convergent. This answers a question of Ab'ert and Hubai in the affirmative. Even in the original case of the chromatic polynomial, our proof is considerably simpler.

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

Recommendations

• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• Chromatic roots and limits of dense graphs
• Chromatic zeros on hierarchical lattices and equidistribution on parameter space
• Chromatic Roots are Dense in the Whole Complex Plane
• Chromatic polynomials

zbMATH Keywords

Benjamini-Schramm convergent sequence of finite graphschromatic measure of a finite simple graph

Mathematics Subject Classification ID

Graph polynomials (05C31)

Cites Work

• Theory of monomer-dimer systems
• Asymptotic Enumeration of Spanning Trees
• Problems in algebraic combinatorics
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• On the theory of the matching polynomial
• Mergelyan's Theorem on Uniform Polynomial Approximation.
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• An introduction to chromatic polynomials
• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Left and right convergence of graphs with bounded degree
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Two remarks on the adjoint polynomial
• Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model)
• Set maps, umbral calculus, and the chromatic polynomial

Cited In (21)

• Characteristic power series of graph limits
• The Ising partition function: zeros and deterministic approximation
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Convergence of graphs with intermediate density
• Matchings in Benjamini-Schramm convergent graph sequences
• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• Integrating products of quadratic forms
• Chromatic roots and limits of dense graphs
• Rank and Bollobás-Riordan polynomials: Coefficient measures and zeros
• Statistical Matching Theory
• Random cluster model on regular graphs
• Evaluations of Tutte polynomials of regular graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Approximating permanents and hafnians
• Correlation decay and the absence of zeros property of partition functions
• Weighted counting of solutions to sparse systems of equations
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• Distribution of coefficients of rank polynomials for random sparse graphs

This page was built for publication: Benjamini-Schramm continuity of root moments of graph polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896079)