HEXAGONbeta

A six-spin obstruction to antiferromagnetic biclique maximization

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath-ph — Mathematical Physics

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

Version 1 / Oct 14, 2026 / CC BY 4.0

Abstract

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.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking. Text origin: primarily AI-generated. Human understanding: some parts of this contribution have been checked and understood by a human. The manuscript received only limited human checking. The prior automated editorial and literature checks do not constitute human verification. The disproof concerns the general graph conjecture and does not settle its regular-graph counterpart. Absolute priority is not certified.

Tools used

Bolzano team
Bolzano

References

  1. A. Sah, M. Sawhney, D. Stoner and Y. Zhao, A reverse Sidorenko inequality, Inventiones mathematicae 221 (2020), 665--711. doi:10.1007/s00222-020-00956-9 (https://doi.org/10.1007/s00222-020-00956-9).DOI
  2. L. Lovász, Large Networks and Graph Limits , American Mathematical Society Colloquium Publications 60 , American Mathematical Society, Providence, RI, 2012. https://doi.org/10.1090/coll/060.DOI
  3. A. Sidorenko, A correlation inequality for bipartite graphs, Graphs Combin. 9 (1993), 201--204. https://doi.org/10.1007/BF02988307.DOI
  4. E. Davies, M. Jenssen, W. Perkins and B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc. (2) 96 (2017), 47--66. https://doi.org/10.1112/jlms.12056.DOI
  5. E. Cohen, P. Csikvári, W. Perkins and P. Tetali, The Widom--Rowlinson model, the hard-core model and the extremality of the complete graph, European J. Combin. 62 (2017), 70--76. https://doi.org/10.1016/j.ejc.2016.11.003.DOI
  6. J. Lee and J. Seo, Antiferromagnetic models are clique-minimizing, arXiv:2608.17920v1 (2026). https://arxiv.org/abs/2608.17920.arXiv
  7. J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combinatorics, Probability and Computing 10 (2001), 219--237. doi:10.1017/S0963548301004631 (https://doi.org/10.1017/S0963548301004631).DOI
  8. Y. Zhao, The number of independent sets in a regular graph, Combinatorics, Probability and Computing 19 (2010), 315--320. doi:10.1017/S0963548309990538 (https://doi.org/10.1017/S0963548309990538).DOI
  9. D. Galvin and P. Tetali, On weighted graph homomorphisms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 63 (2004), 97--104. doi:10.1090/dimacs/063/07 (https://doi.org/10.1090/dimacs/063/07).DOI
  10. A. Sah, M. Sawhney, D. Stoner and Y. Zhao, The number of independent sets in an irregular graph, Journal of Combinatorial Theory, Series B 138 (2019), 172--195. doi:10.1016/j.jctb.2019.01.007 (https://doi.org/10.1016/j.jctb.2019.01.007).DOI
Show all 14 referencesShow fewer references
  1. Y. Zhao, The bipartite swapping trick on graph homomorphisms, SIAM Journal on Discrete Mathematics 25 (2011), 660--680. doi:10.1137/100800415 (https://doi.org/10.1137/100800415).DOI
  2. J. Lee, J. Oh and J. Seo, Counting homomorphisms in antiferromagnetic graphs via Lorentzian polynomials, arXiv:2506.13659v2 (2025). https://arxiv.org/abs/2506.13659.arXiv
  3. P. Brändén and J. Huh, Lorentzian polynomials, Annals of Mathematics 192 (2020), 821--891. doi:10.4007/annals.2020.192.3.4 (https://doi.org/10.4007/annals.2020.192.3.4).DOI
  4. OpenAI, A counterexample to Sidorenko's conjecture, preprint, September 23, 2026. Public manuscript, version accessed October 11, 2026 (https://github.com/openai/math/blob/fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb/preprints/A-counterexample-to-Sidorenkos-conjecture-September-23-2026/paper.pdf).link

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 14, 2026