Antiferromagnetic models are clique-minimizing

Abstract

An edge-weighted graph $H$, possibly with loops, is antiferromagnetic if its adjacency matrix is entrywise nonnegative and has at most one positive eigenvalue, counted with multiplicity. We show that, for any graph $G$ with $d_v:=\operatorname{deg}_G(v)$, $$\operatorname{hom}(G,H) \ge \prod_{v\in V(G)} \operatorname{hom}(K_{d_v+1},H)^{\frac{1}{d_v+1}},$$ whenever $H$ is antiferromagnetic. In fact, we prove a vertex-inhomogeneous strengthening of this inequality, allowing a different fugacity vector at each vertex of $G$. This gives a common generalization of the lower-bound inequalities of Sah, Sawhney, Stoner, and Zhao for independent sets, of Csikvári for $q$-colorings, and of the authors for semiproper colorings with at most two proper colors. Furthermore, it confirms recent conjectures of the authors and of Davies and LeBlanc. A key ingredient, of independent interest, is a strengthening of the delete-one form of Shearer's inequality for Lorentzian measures, which provides a new approach to graph homomorphism inequalities.

Disclosure

“ion invoked, without proof, a version of the relative entropy contraction. It then also produced a proof of the claimed entropy inequality, though we made extra queries to relate the argument to [AOV21; Ana+22]. Second, we iteratively used GPT-5.5 Thinking Extended to investigate technical details and possible generalizations, leading first to proofs for antiferromagnetic 2-spin models and for Kq◦ with the loop weight restricted to a certain range. Comparing the resulting model-spec”

PDF page 22

Classification

Substantial proof generation

Multiplier

10

Verified

2026-08-23T05:22:48.052273Z

Structural counts