Lower bounds for multivariate independence polynomials and their generalisations

Abstract

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({\lambda }_1,\dots ,{\lambda }_n):={\sum }_{I\in \mathcal{I}(G)}{\prod }_{v\in I}{\lambda }_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 ${\lambda }_1,\dots ,{\lambda }_n\ge 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 ${\lambda }_1=\cdots ={\lambda }_n=\lambda$. We further conjecture that our inequality should generalise to other antiferromagnetic models and give some evidence in support of it. In particular, for ${\lambda }_i,{\mu }_i\ge 0$, $1\le i\le 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.

17 pages. Clarify Section 3 and add a Lean formalisation of Theorem 1.4. See https://github.com/thegreatseo/multivar-indep-formalize for the GitHub repo