Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial
Algebraic Combinatorics, Volume 2 (2019) no. 5, p. 781-802

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.

Received : 2017-10-31
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},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_5_781_0}
}
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] Bencs, Ferenc Christoffel–Darboux type identities for independence polynomial (2014) (arXiv preprint https://arxiv.org/abs/1409.2527) | Zbl 1402.05105

[2] Borcea, Julius; Brändén, Petter 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] Borcea, Julius; Brändén, Petter 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] Brändén, Petter Polynomials with the half-plane property and matroid theory, Advances in Mathematics, Volume 216 (2007) no. 1, pp. 302-320 | MR 2353258 | Zbl 1128.05014

[5] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold Distance-Regular Graphs, Springer-Verlag (1989), p. 103-104,312 | Zbl 0747.05073

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

[7] Choe, Young-Bin; Oxley, James G; Sokal, Alan D; Wagner, David G 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] Chudnovsky, Maria; Seymour, Paul The roots of the independence polynomial of a clawfree graph, Journal of Combinatorial Theory, Series B, Volume 87 (2007) no. 3, pp. 350-357 | MR 2305888 | Zbl 1119.05075

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

[10] Fisher, David C.; Ryan, Jennifer 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] Fisher, David C.; Solow, Anita E. Dependence Polynomials, Discrete Mathematics, Volume 82 (1990) no. 3, pp. 251-258 | Article | MR 1059348 | Zbl 0721.05036

[12] Godsil, Chris Algebraic Combinatorics, CRC Press (1993) | Zbl 0784.05001

[13] Heilmann, Ole J.; Lieb, Elliott H. Theory of Monomer-Dimer Systems, Communications in Mathematical Physics, Volume 25 (1972) no. 3, pp. 190-232 | MR 297280 | Zbl 0228.05131

[14] Lass, Bodo 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 | MR 2885427 | Zbl 1239.05096

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

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

[17] Scott, Alexander; Sokal, Alan 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