← All papers
First page of Lower bounds for multivariate independence polynomials and their generalisations

Lower bounds for multivariate independence polynomials and their generalisations

Joonkyung Lee, Jaehyeon Seo

math.CO Feb 2, 2026 · v2
Theorem 1.4, the semiproper colouring lower bound, is formalised in Lean 4 using Harmonic Aristotle, with Lean files in a GitHub repository.
In statistical physics, the multivariate hard-core model describes a system of particles, each of which receives its own fugacity. In graph-theoretic language, the partition function of the model translates to the multivariate independence polynomial, i.e., the multiaffine generalisation of the independence polynomial, defined by $Z_G(λ_1,\dots,λ_n) := \sum_{I\in\mathcal{I}(G)} \prod_{v\in I}λ_v$, where $\mathcal{I}(G)$ denotes the set of all independent sets in a graph $G$ on $[n]:=\{1,2,\dots,n\}$. We prove that for every simple graph $G$ on $[n]$ and $λ_1,\dots,λ_n\geq 0$, \[ Z_G(λ_1,\dots,λ_n) \geq \prod_{i=1}^n (1+(d_i+1)λ_i)^{1/(d_i+1)}, \] where $d_1,\dots,d_n$ is the degree sequence of $G$. This generalises a result of Sah, Sawhney, Stoner, and Zhao, who proved the univariate case $λ_1=\dots=λ_n=λ$. We further conjecture that our inequality should generalise to other antiferromagnetic models and give some evidence in support of it. In particular, for $λ_i,μ_i\geq 0$, $1\leq i\leq n$, we obtain a stronger inequality \[ \sum_{\substack{I,J\in \mathcal{I}(G) \\ I\cap J=\emptyset}} \prod_{v\in I}λ_v\prod_{u\in J}μ_u \geq \prod_{i=1}^n \left(1+(d_i+1)(λ_i+μ_i)+d_i(d_i+1)λ_iμ_i\right)^{1/(d_i+1)}, \] which proves our conjecture for a multiaffine generalisation of the semiproper colouring partition function with two proper colours. Our key technical steps for both theorems are obtained by using a custom mathematical research agent built on top of Gemini Deep Think, which can be seen as a benchmark demonstrating that the current state-of-the-art language models can, in part, assist with mathematical research.

The paper seeks lower bounds on the multivariate independence polynomial of a graph in terms of its degree sequence. This generalises the univariate result of Sah, Sawhney, Stoner and Zhao, and it also asks for analogous bounds for antiferromagnetic models such as semiproper colourings.

The proofs use induction on vertices via the vertex-deletion recurrence, reducing each bound to an analytic inequality involving clique partition functions. Key technical lemmas were obtained with a custom research agent built on Gemini Deep Think. The two-colour semiproper colouring theorem (Theorem 1.4) was formalised in Lean 4 using Harmonic Aristotle.

For every graph and nonnegative fugacities, Z_G(λ) ≥ ∏(1+(d_i+1)λ_i)^{1/(d_i+1)}, with equality characterised. A stronger inequality is proved for the two-colour semiproper colouring partition function. The general antiferromagnetic conjecture is proved for graphs with maximum degree at most 2.