math.CO — Combinatorics

A six-spin obstruction to antiferromagnetic biclique maximization

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

Sah, Sawhney, Stoner and Zhao conjectured that for every spin model whose interaction matrix has exactly one positive eigenvalue, the partition function of any graph is at most a product of biclique partition functions determined by its edge degrees. We disprove this conjecture with a strictly positive six-spin model on a triangle with three pendant edges; the violation persists on an open set of nonsingular models. The mechanism is a negative mixed covariance trace at vertices of degrees two, three and four: the triangle contributes a favourable cubic term, whereas all biclique corrections start at fourth order.