On a Conjecture of Sokal Concerning Roots of the Independence Polynomial
| Autor: | Han Peters, Guus Regts |
|---|---|
| Přispěvatelé: | Analysis (KDV, FNWI), Algebra, Geometry & Mathematical Physics (KDV, FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Polynomial Conjecture Dynamical systems theory General Mathematics Existential quantification 82B20 010102 general mathematics Natural number Dynamical Systems (math.DS) 01 natural sciences 37F10 Graph Combinatorics Computer Science - Data Structures and Algorithms 0103 physical sciences FOS: Mathematics 05C31 Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) 010307 mathematical physics Mathematics - Dynamical Systems 0101 mathematics Mathematics |
| Zdroj: | The Michigan mathematical journal, 68(1), 33-55. University of Michigan Michigan Math. J. 68, iss. 1 (2019), 33-55 |
| ISSN: | 1945-2365 0026-2285 |
| Popis: | A conjecture of Sokal (2001) regarding the domain of non-vanishing for independence polynomials of graphs, states that given any natural number $\Delta \ge 3$, there exists a neighborhood in $\mathbb C$ 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. Comment: We have updated the file partly based on some comments from a referee. The file is now 20 pages and contains one figure. Accepted in Michigan Mathematical Journal |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|