Coordination three heals, coordination four is hard: the antiferromagnetic Potts model with a costly third state
Abstract
We study the ground states of the antiferromagnetic three-state Potts model in which the third state carries a single-ion energy cost D3, on arbitrary lattices, and show that the difficulty of the ground-state problem is controlled by the maximum coordination Δ alone; on planar lattices with Δ≤5 it is classified completely. On lattices with coordination at most three the third state heals frustrated bonds one for one: every graph of maximum degree three other than K4 has an independent set of sites that meets every odd cycle and whose size equals the number fr of frustrated bonds of the Ising ground state. This identity also follows from known results on the chromatic vertex stability of graphs; we give a constructive proof. Hence E0 (D3)=min(D3,1) fr for all D3, computable in polynomial time on planar lattices. In graph-theoretic terms, independent odd cycle transversal is solvable in polynomial time on planar subcubic graphs. On planar lattices with maximum coordination four, in contrast, deciding the ground-state energy is NP-complete for every fixed 0≤ D3<2 and polynomial for D3≥2. The boundary is set by a local principle: a site of coordination d in the third state relieves at most ⌊ d/2⌋ frustrated bonds, so the third state is useless once D3≥⌊Δ/2⌋; this threshold is sharp for every Δ≥3 and reproduces the triangular-lattice point D3*=3 of the equivalent spin-1 Blume--Capel antiferromagnet. From a single Ising ground state the proof builds an exact ground state in polynomial time, which for quasicrystalline, foam-like and defective lattices with thousands of sites takes seconds to minutes.
Related
- Three formulas for the Ising and Potts invariants of a knot or link
- Three-Phase Unbalance Mitigation via DSO-FRA Coordination: A GNB-Based Chance-Constrained Model Considering PV Uncertainty
- Optimal Annuitization, Consumption, and Investment with Costly Capital Injections
- Finite-horizon Optimal Consumption and Investment with Costly Income Adjustment
- Adaptive Sampling of Costly Outcomes in Randomized Clinical Trials
BibTeX
@misc{choi2026coordination,
title = {{Coordination three heals, coordination four is hard: the antiferromagnetic Potts model with a costly third state}},
author = {Jeehoon Choi and Suhwan Yoo and Chaeyeon Kim and Hee Young Kwon and Changyeon Won},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41277},
eprint = {2610.41277},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41277},
}
RIS
TY - UNPB
TI - Coordination three heals, coordination four is hard: the antiferromagnetic Potts model with a costly third state
AU - Jeehoon Choi
AU - Suhwan Yoo
AU - Chaeyeon Kim
AU - Hee Young Kwon
AU - Changyeon Won
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41277
UR - https://arxiv.org/abs/2610.41277
AB - We study the ground states of the antiferromagnetic three-state Potts model in which the third state carries a single-ion energy cost D_3, on arbitrary lattices, and show that the difficulty of the ground-state problem is controlled by the maximum coordination Δ alone; on planar lattices with Δ≤5 it is classified completely. On lattices with coordination at most three the third state heals frustrated bonds one for one: every graph of maximum degree three other than K_4 has an independent set of sites that meets every odd cycle and whose size equals the number fr of frustrated bonds of the Ising ground state. This identity also follows from known results on the chromatic vertex stability of graphs; we give a constructive proof. Hence E_0 (D_3)=min(D_3,1) fr for all D_3, computable in polynomial time on planar lattices. In graph-theoretic terms, independent odd cycle transversal is solvable in polynomial time on planar subcubic graphs. On planar lattices with maximum coordination four, in contrast, deciding the ground-state energy is NP-complete for every fixed 0≤ D_3<2 and polynomial for D_3≥2. The boundary is set by a local principle: a site of coordination d in the third state relieves at most ⌊ d/2⌋ frustrated bonds, so the third state is useless once D_3≥⌊Δ/2⌋; this threshold is sharp for every Δ≥3 and reproduces the triangular-lattice point D_3^*=3 of the equivalent spin-1 Blume--Capel antiferromagnet. From a single Ising ground state the proof builds an exact ground state in polynomial time, which for quasicrystalline, foam-like and defective lattices with thousands of sites takes seconds to minutes.
ER -