We generalize two main theorems of matching polynomials of undirected simple graphs, namely, real-rootedness and the Heilmann–Lieb root bound. Viewing the matching polynomial of a graph $G$ as the independence polynomial of the line graph of $G$, we determine conditions for the extension of these theorems to the independence polynomial of any graph. In particular, we show that a stability-like property of the multivariate independence polynomial characterizes claw-freeness. Finally, we give and extend multivariate versions of Godsil’s theorems on the divisibility of matching polynomials of trees related to $G$.

Revised:

Accepted:

Published online:

DOI: 10.5802/alco.63

Keywords: independence polynomial, real-stability, claw-free

^{1}; Ryder, Nick R.

^{1}

@article{ALCO_2019__2_5_781_0, author = {Leake, Jonathan D. and Ryder, Nick R.}, title = {Generalizations of the {Matching} {Polynomial} to the {Multivariate} {Independence} {Polynomial}}, journal = {Algebraic Combinatorics}, pages = {781--802}, publisher = {MathOA foundation}, volume = {2}, number = {5}, year = {2019}, doi = {10.5802/alco.63}, mrnumber = {4023566}, zbl = {07115041}, language = {en}, url = {http://www.numdam.org/articles/10.5802/alco.63/} }

TY - JOUR AU - Leake, Jonathan D. AU - Ryder, Nick R. TI - Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial JO - Algebraic Combinatorics PY - 2019 SP - 781 EP - 802 VL - 2 IS - 5 PB - MathOA foundation UR - http://www.numdam.org/articles/10.5802/alco.63/ DO - 10.5802/alco.63 LA - en ID - ALCO_2019__2_5_781_0 ER -

%0 Journal Article %A Leake, Jonathan D. %A Ryder, Nick R. %T Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial %J Algebraic Combinatorics %D 2019 %P 781-802 %V 2 %N 5 %I MathOA foundation %U http://www.numdam.org/articles/10.5802/alco.63/ %R 10.5802/alco.63 %G en %F ALCO_2019__2_5_781_0

Leake, Jonathan D.; Ryder, Nick R. Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial. Algebraic Combinatorics, Volume 2 (2019) no. 5, pp. 781-802. doi : 10.5802/alco.63. http://www.numdam.org/articles/10.5802/alco.63/

[1] Christoffel–Darboux type identities for independence polynomial (2014) (arXiv preprint https://arxiv.org/abs/1409.2527) | Zbl

[2] The Lee–Yang and Pólya-Schur programs. I. Linear operators preserving stability, Inventiones mathematicae, Volume 177 (2009) no. 3, pp. 541-569 | DOI | Zbl

[3] The Lee-Yang and Pólya-Schur programs. II. Theory of Stable Polynomials and Applications, Communications on Pure and Applied Mathematics, Volume 62 (2009) no. 12, pp. 1595-1631 | DOI | Zbl

[4] Polynomials with the half-plane property and matroid theory, Advances in Mathematics, Volume 216 (2007) no. 1, pp. 302-320 | DOI | MR | Zbl

[5] Distance-Regular Graphs, Springer-Verlag, 1989, p. 103-104,312 | Zbl

[6] Bounding the roots of the independence polynomials, Ars Combin., Volume 58 (2001), pp. 113-120 | MR | Zbl

[7] Homogeneous multivariate polynomials with the half-plane property, Advances in Applied Mathematics, Volume 32 (2004) no. 1-2, pp. 88-187 | DOI | MR | Zbl

[8] The roots of the independence polynomial of a clawfree graph, Journal of Combinatorial Theory, Series B, Volume 87 (2007) no. 3, pp. 350-357 | DOI | MR | Zbl

[9] Inequalites on Well-Distributed Points Sets on Circles, Journal of Inequalities in Pure and Applied Mathematics, Volume 8 (2007) no. 2, 34 | MR | Zbl

[10] Bounds on the largest root of the matching polynomial, Discrete Mathematics, Volume 110 (1992) no. 1-3, pp. 275-278 | DOI | MR | Zbl

[11] Dependence Polynomials, Discrete Mathematics, Volume 82 (1990) no. 3, pp. 251-258 | DOI | MR | Zbl

[12] Algebraic Combinatorics, CRC Press, 1993 | Zbl

[13] Theory of Monomer-Dimer Systems, Communications in Mathematical Physics, Volume 25 (1972) no. 3, pp. 190-232 | DOI | MR | Zbl

[14] Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs, Journal of Combinatorial Theory, Series B, Volume 102 (2012) no. 2, pp. 411-423 | DOI | MR | Zbl

[15] Interlacing families I: Bipartite Ramanujan graphs of all degrees, Annals of Mathematics, Volume 182 (2015) no. 1, pp. 307-325 | DOI | MR | Zbl

[16] Distance-Hereditary Graphs, Journal of Combinatorial Theory, Series B, Volume 41 (1986) no. 2, pp. 182-208 | MR | Zbl

[17] The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics, Volume 118 (2005) no. 5-6, pp. 1151-1261 | DOI | Zbl

*Cited by Sources: *