×

On a conjecture of Sokal concerning roots of the independence polynomial. (English) Zbl 1433.05164

Summary: A conjecture of A. D. Sokal [Markov Process. Relat. Fields 7, No. 1, 21–38 (2001; Zbl 0999.82021)], regarding the domain of nonvanishing 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,(\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 the optimality for the domain of nonvanishing. An important step is to translate the setting to the language of complex dynamical systems.

MSC:

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

Citations:

Zbl 0999.82021
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] A. Barvinok, Computing the permanent of (some) complex matrices, Found. Comput. Math. (2014), 1-14. · Zbl 1347.65082
[2] A. Barvinok, Computing the partition function for cliques in a graph, Theory Comput. 11 (2015), 339-355, Article 13. · Zbl 1351.05212
[3] A. Barvinok, Approximating permanents and hafnians of positive matrices, Discrete Anal. (2017), no. 2, 34pp. · Zbl 1404.15008
[4] A. Barvinok, Combinatorics and complexity of partition functions, Algorithms Combin., 30, Springer, Cham, Switzerland, 2017. · Zbl 1367.05002
[5] A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms with multiplicities, J. Combin. Theory Ser. A 137 (2016), 1-26. · Zbl 1325.05114
[6] A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms, Combinatorica 37 (2017), 633-650. · Zbl 1399.05209
[7] M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali, Simple deterministic approximation algorithms for counting matchings, Proceedings of the thirty-ninth annual ACM symposium on theory of computing, pp. 122-127, ACM, 2007. · Zbl 1232.68179
[8] I. Bezakóva, A. Galanis, L. A. Goldberg, and D. Štefankovič, Inapproximability of the independent set polynomial in the complex plane, Proceedings of the 50th annual ACM SIGACT symposium on theory of computing 1234-1240, ACM, 2018 and arXiv preprint, 2018 Feb 18, arXiv:1711.00282. · Zbl 1427.68229
[9] P. Bleher, M. Lyubich, and R. Roeder, Lee-Yang-Fisher zeros for DHL and 2D rational dynamics, II. Global pluripotential interpretation, preprint, 2011, available online at arXiv:1107.5764, 36 pages. · Zbl 1437.82003
[10] P. Bleher, M. Lyubich, and R. Roeder, Lee-Yang zeros for DHL and 2D rational dynamics, I. Foliation of the physical cylinder, J. Math. Pures Appl. 107 (2017), 491-590. · Zbl 1372.82011
[11] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007), 350-357. · Zbl 1119.05075
[12] A. Douady, Does a Julia set depend continuously on the polynomial? Complex dynamical systems, Cincinnati, OH, 1994, Proc. Sympos. Appl. Math., 49, pp. 91-138, Amer. Math. Soc., Providence, RI, 1994. · Zbl 0934.30023
[13] A. Galanis, L. A. Goldberg, and D. Štefankovič, Inapproximability of the independent set polynomial below the Shearer threshold, LIPIcs-Leibniz international proceedings in informatics, 80, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017, and arXiv preprint, 2016 Dec 17, arXiv:1612.05832. · Zbl 1441.68180
[14] D. Gamarnik and D. Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, J. Discrete Algorithms 12 (2012), 29-47. · Zbl 1241.05049
[15] P. Lavaurs, Systèmes dynamiques holomorphiques: explosion des points périodiques, PhD Thesis, Univesité Paris-Sud, 1989.
[16] J. Liu and P. Lu, FPTAS for # BIS with degree bounds on one side, Proceedings of the forty-seventh annual ACM on symposium on theory of computing, 2015 Jun 14, pp. 549-556, ACM. · Zbl 1321.05185
[17] P. Lu and Y. Yin, Improved FPTAS for multi-spin systems, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, pp. 639-654, Springer, Berlin Heidelberg, 2013. · Zbl 1405.68446
[18] J. Milnor, Dynamics in one complex variable, Third edition, Ann. of Math. Stud., 160, Princeton University Press, Princeton, NJ, 2006. · Zbl 1085.30002
[19] V. Patel and G. Regts, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, SIAM J. Comput. 46 (2017), 1893-1919. · Zbl 1383.68099
[20] G. Regts, Zero-free regions of partition functions with applications to algorithms and graph limits, Combinatorica 38 (2018), 987-1015. · Zbl 1424.05236
[21] A. D. Scott and A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys. 118 (2005), 1151-1261. · Zbl 1107.82013
[22] J. B. Shearer, On a problem of Spencer, Combinatorica 5 (1985), 241-245. · Zbl 0587.60012
[23] A. Sly and N. Sun, Counting in two-spin models on d-regular graphs, Ann. Probab. 42 (2014), 2383-2416. · Zbl 1311.60117
[24] A. Sokal, A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models, Markov Process. Related Fields 7 (2001), 21-38. · Zbl 0999.82021
[25] D. Weitz, Counting independent sets up to the tree threshold, Proceedings of the thirty-eighth annual ACM symposium on theory of computing, STOC 06, pp. 140-149, ACM, New York, NY, USA, 2006. · Zbl 1301.68276
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.