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 as the independence polynomial of the line graph of , 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 .
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.63
Keywords: independence polynomial, real-stability, claw-free
Leake, Jonathan D. 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}, zbl = {07115041}, mrnumber = {4023566}, language = {en}, url = {https://alco.centre-mersenne.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 - https://alco.centre-mersenne.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 https://alco.centre-mersenne.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. https://alco.centre-mersenne.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, Paper no. 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: