Same-phase stability for graph polynomials
The multivariate independence polynomial of a finite graph is same-phase stable exactly when the graph is claw-free.
Results
A multivariate polynomial $P$ is same-phase stable if $P(w_1x,\dotsc,w_nx)$ is real-rooted in $x$ for every choice of nonnegative weights $w_i$.
Theorem (Leake–Ryder). For a finite graph $G$, the multivariate independence polynomial $\sum_S\prod_{v\in S}x_v$, summed over the independent sets $S$, is same-phase stable if and only if $G$ is claw-free. In particular the independence polynomial of a claw-free graph is real-rooted (the Chudnovsky–Seymour theorem, obtained by setting every variable equal to $x$).
Theorem (weights). If the weighted independence polynomial $\sum_S\prod_{v\in S}w_v\,x^{|S|}$ is real-rooted for every choice of nonnegative vertex weights $w$, then $G$ is claw-free. Weights $1$ on a claw and $0$ elsewhere give $1+4x+3x^2+x^3$, which has non-real roots.
Theorem (matchings). The edge-variable matching polynomial $\sum_M\prod_{e\in M}x_e$, summed over the matchings $M$ of $G$, is same-phase stable.
References
The first theorem is due to Leake and Ryder [LR19]. See also the discussion of same-phase stability on symmetricfunctions.com.
- [LR19] Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial. Algebraic Combinatorics, 2(5), 781-802, 2019.
BibTeX
@article{LeakeRyder2019, 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={alco.centre-mersenne.org/item/ALCO_2019__2_5_781_0/} }