On a conjecture of Sokal concerning roots of the independence polynomial

DOI10.1307/MMJ/1541667626MaRDI QIDQ2286792zbMATH OpenOpenAlexWikidataFDO

Authors Han Peters, Guus Regts

Publication date 22 January 2020

Published in Michigan Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.08049, https://projecteuclid.org/euclid.mmj/1541667626

zbMATH Keywords

complex dynamical systemsSokal's conjecture

Mathematics Subject Classification ID

Graph polynomials (05C31) Dynamics of complex polynomials, rational maps, entire and meromorphic functions; Fatou and Julia sets (37F10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: A conjecture of Sokal (2001) regarding the domain of non-vanishing for independence polynomials of graphs, states that given any natural number $Deltage3$, there exists a neighborhood in $mathbbC$ of the interval $[0,frac(Delta-1{)}^{Delta-1}(Delta-2{)}^{Delta})$ on which the independence polynomial of any graph with maximum degree at most $Delta$ does not vanish. We show here that Sokal's Conjecture holds, as well as a multivariate version, and prove optimality for the domain of non-vanishing. An important step is to translate the setting to the language of complex dynamical systems.

Recommendations

• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• On the stability of independence polynomials
• On the location of roots of independence polynomials
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• On the roots of expected independence polynomials

Cites work

• A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models
• Approximating permanents and hafnians
• Combinatorics and complexity of partition functions
• Computing the partition function for cliques in a graph
• Computing the partition function for graph homomorphisms
• Computing the partition function for graph homomorphisms with multiplicities
• Computing the permanent of (some) complex matrices
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Dynamics in One Complex Variable. (AM-160)
• FPTAS for \#BIS with degree bounds on one side
• scientific article; zbMATH DE number 5485444 (Why is no real title available?)
• scientific article; zbMATH DE number 739000 (Why is no real title available?)
• scientific article; zbMATH DE number 7204480 (Why is no real title available?)
• Improved FPTAS for multi-spin systems
• Inapproximability of the independent set polynomial in the complex plane
• Lee-Yang zeros for the DHL and 2D rational dynamics. I: Foliation of the physical cylinder
• Lee-Yang-Fisher zeros for the DHL and 2D rational dynamics. II: Global pluripotential interpretation
• On a problem of Spencer
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The roots of the independence polynomial of a clawfree graph
• Zero-free regions of partition functions with applications to algorithms and graph limits

Cited in

(48)

• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Polymer dynamics via cliques: new conditions for approximations
• The complexity of approximating the complex-valued Potts model
• Zeros and approximations of holant polynomials on the complex plane
• Algorithmic Pirogov-Sinai theory
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• Computing permanents of complex diagonally dominant matrices and tensors
• The interaction light cone of the discrete Bak-Sneppen, contact and other local processes
• Analyticity for classical gasses via recursion
• Bounding the roots of independence polynomials.
• On the monotone hook Hafnian conjecture
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• Lee-Yang zeros of the antiferromagnetic Ising model
• The complexity of approximating the complex-valued Potts model
• scientific article; zbMATH DE number 7559110 (Why is no real title available?)
• The complexity of approximating the matching polynomial in the complex plane
• Inapproximability of the independent set polynomial in the complex plane
• Fisher zeros and correlation decay in the Ising model
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• scientific article; zbMATH DE number 7650115 (Why is no real title available?)
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Absence of zeros implies strong spatial mixing
• Correlation decay and the absence of zeros property of partition functions
• Approximating the chromatic polynomial is as hard as computing it exactly
• On the location of chromatic zeros of series-parallel graphs
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• On the zeroes of hypergraph independence polynomials
• Potential-weighted connective constants and uniqueness of Gibbs measures
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Central limit theorems and the geometry of polynomials
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
• Zero-free regions for the independence polynomial on restricted graph classes
• Hypergraph independence polynomials with a zero close to the origin
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions
• Correlation decay and partition function zeros: algorithms and phase transitions
• The limit of the zero locus of the independence polynomial for bounded degree graphs
• Analyticity for locally stable hard-core gases via recursion
• Fast sampling via spectral independence beyond bounded-degree graphs
• Approximately counting independent sets of a given size in bounded-degree graphs
• Approximating the volume of a truncated relaxation of the independence polytope
• Improved mixing of critical hardcore model
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Chromatic zeros on hierarchical lattices and equidistribution on parameter space

This page was built for publication: On a conjecture of Sokal concerning roots of the independence polynomial

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