Christoffel-Darboux Type Identities for the Independence Polynomial
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
A new Christoffel-Darboux type identity expresses differences like I(G−u)I(G−v)−I(G)I(G−{u,v}) as a signed sum over connected induced bipartite subgraphs, with weights given by color-class sizes; the proof uses bijections between product monomials and bipartite configurations. Consequences: claw-free ⇒ real-rooted independence polynomials via parity arguments, sector-free results (no roots in angle pi/κ where κ bounds color-class imbalance), and a divisibility via the self-avoiding walk tree that transfers tree zero-freeness to bounded-degree graphs.
AI-written summary · about