ALGEBRAIC COMBINATORICS

no. 5
Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial
Leake, Jonathan D.1; Ryder, Nick R.1
1 University of California, Berkeley Dept. of mathematics Berkeley CA 94709, USA
Algebraic Combinatorics, Volume 2 (2019) no. 5, pp. 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:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.63
Classification: 05C31
Keywords: independence polynomial, real-stability, claw-free
Leake, Jonathan D. 1; Ryder, Nick R. 1

1 University of California, Berkeley Dept. of mathematics Berkeley CA 94709, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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] Bencs, Ferenc Christoffel–Darboux type identities for independence polynomial (2014) (arXiv preprint https://arxiv.org/abs/1409.2527) | Zbl

[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 | DOI | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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, Paper no. 34 | MR | Zbl

[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 | DOI | MR | Zbl

[11] Fisher, David C.; Solow, Anita E. Dependence Polynomials, Discrete Mathematics, Volume 82 (1990) no. 3, pp. 251-258 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | Zbl

Cited by Sources: