Independence polynomial I(G,x) = Σ s_k x^k. s_0=1, s_1=n, s_k = independent sets of size k. I(G,1) = total independent sets. Coefficients are log-concave for claw-free graphs (Chudnovsky-Seymour, 2007). Connected to partition function in statistical mechanics.
How to Use
Select graph:
- I(G,x): Polynomial
- s_k: k-ind sets
- Total: I(G,1)
Unimodality Conjectures
Are coefficients s_0,s_1,...,s_α unimodal? Not always! But for forests, claw-free graphs, and well-covered graphs: yes. The Alavi-Malde-Schwenk-Erdős conjecture: s_k is unimodal for trees. Proved by Levit-Mandrescu.
Statistical Mechanics
I(G,x) = partition function of hard-core model at fugacity x. Phase transitions occur at specific x values. The roots of I(G,x) determine analyticity of the free energy. Connects graph theory to physics.
Step-by-Step Instructions
- 1Select graph.
- 2Count s_k.
- 3Build polynomial.
- 4Evaluate I(G,1).
- 5Check unimodality.