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: 2019-01-15

Accepted: 2019-01-22

Published online: 2019-10-08

DOI: https://doi.org/10.5802/alco.63

Classification: 05C31

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

@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}, publisher = {MathOA foundation}, volume = {2}, number = {5}, year = {2019}, pages = {781-802}, doi = {10.5802/alco.63}, mrnumber = {4023566}, zbl = {07115041}, language = {en}, url = {alco.centre-mersenne.org/item/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/item/ALCO_2019__2_5_781_0/

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

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

[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 | Article | Zbl 1177.47041

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

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

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

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

[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 | Article | MR 2305888 | Zbl 1119.05075

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

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

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

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

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

[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 | Article | MR 2885427 | Zbl 1239.05096

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

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

[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 | Article | Zbl 1107.82013