# P2702: Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices

- ID: `P2702`
- Reference: `cubic-graph-twenty-ising-degeneracy`
- Page: https://theoremdb.org/statements/P2702
- Record maturity: Reviewed problem with recorded work

## Problem

Among simple \(3\)-connected cubic graphs \(G\) on \(20\) labeled vertices, determine the largest number of assignments \(\sigma\in\{-1,1\}^{20}\) that minimize \(\sum_{uv\in E(G)}\sigma_u\sigma_v\).

### Remarks

- **Remark.** Ground states are exactly the spin assignments whose two spin classes define a maximum cut.
- **Remark.** Both sigma and -sigma are counted, and labeled copies of the same graph have the same degeneracy.

### What counts as a solution

- Give a 3-connected cubic graph attaining the maximum degeneracy and a complete isomorph-free enumeration with exact ground-state counts.

## Status

An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658. [1](#reference-1)

## Work

### Evidence for the current status

**Proposition 1 (The certified interval is 36 through 254,658 ground states).** An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658.

Let \(D_{20}\) be the maximum in the question. The checked evidence gives
\[
\boxed{36\leq D_{20}\leq254{,}658}.
\]
The lower endpoint is reproduced by the exact spin sweep in this fixture. It checks an explicit graph, proves vertex connectivity three, and examines all \(2^{19}=524{,}288\) assignments with one spin fixed. The graph has maximum cut 25 and 18 fixed-spin maximizers, hence 36 ground states after global flips are restored.

For the upper endpoint, local optimality forces the same-spin edges of every ground state to form a matching. On a connected graph, that matching determines the spin assignment up to global flip. The total number of ground states is therefore at most twice the total number of matchings. Davies, Jenssen, Perkins, and Roberts prove that the normalized matching partition function of a \(d\)-regular graph is maximized by \(K_{d,d}\). Since \(K_{3,3}\) has 34 matchings in total,
\[
M_G(1)\leq34^{20/6}=34^{10/3}<127{,}330,
\]
so the integer count satisfies \(M_G(1)\leq127{,}329\), giving \(D_{20}\leq254{,}658\).

The exact value still requires an isomorph-free sweep of the 396,150 relevant graph classes or a sharper structural argument.

### Background and intake notes

The current certified lower bound is 36 ground states.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this exact graph order and connectivity restriction.
- Enumerate unlabeled cubic graphs and reject vertex connectivity below 3 before solving maximum cut. Canonical labels prevent repeating isomorphic graphs.
- A graph with a slightly smaller maximum-cut value can have higher degeneracy, so cut size cannot be used as the primary objective.
- Fixing one spin removes the global flip symmetry and halves the 2^20 exact count.

- Recorded example: One incumbent has maximum-cut size 25 and 36 ground states.

### Other known results

- **Theorem 1** (established): Local cut optimality injects spin pairs into graph matchings, and the sharp regular-graph partition-function bound controls their total number. [1](#reference-1)
- **Computation 1** (reproduced): Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): Published generators settle the corpus size, while the checked Ising and matching papers provide context and a universal bound rather than the order-20 extremum. [3](#reference-3) [4](#reference-4) [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks cubicity, 3-connectivity, every spin pair, the full cut histogram, and all maximizing masks.

### Computational notes

- Five hundred seeded random cubic graphs were filtered for 3-connectivity and every spin assignment was checked with one spin fixed. The best graph had edges 03,0E,0G,12,19,1E,26,27,35,39,48,4B,4J,57,5E,6G,6J,7D,89,8B,AC,AH,AI,BH,CD,CI,DF,FH,FJ,GI, where A=10 through J=19. Exact enumeration found maximum-cut size 25 and 18 fixed-spin maximizers, hence 36 ground states.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `cubic-graph-twenty-ising-degeneracy`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, “Independent Sets, Matchings, and Occupancy Fractions”. DOI 10.1112/jlms.12056. arXiv:1508.04675 (2015). Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, Theorem 3 and its integrated matching-partition-function consequence; Davies, Jenssen, Perkins, and Roberts, Theorem 3; the local-optimality reduction is proved in this record https://arxiv.org/abs/1508.04675
   - Also cited at Theorem 3
   - Also cited at Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, Theorem 3 and its integrated matching-partition-function consequence
   - Also cited at Davies, Jenssen, Perkins, and Roberts, Theorem 3; the local-optimality reduction is proved in this record
   - Also cited at Exact certificate in cubic20ising-artifact-incumbent-verifier, reproduced on 2026-07-25
   - preprint; reference source; arXiv:1508.04675, version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices: The certified interval is 36 through 254,658 ground states. An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658. Every connected cubic graph on 20 vertices has at most 254,658 ground states. Local cut optimality injects spin pairs into graph matchings, and the sharp regular-graph partition-function bound controls their total number. The exact target remains a finite 396,150-class computation. Published generators settle the corpus size, while the checked Ising and matching papers provide context and a universal bound rather than the order-20 extremum.
   - Source named by the research packet.
2. <a id="reference-2"></a>Gunnar Brinkmann, Jan Goedgebeur, and Brendan D. McKay, Generation of Cubic Graphs. dmtcs.episciences.org checked 2026-08-01. DMTCS 13(2) (2011), pages 69-80 https://dmtcs.episciences.org/551/pdf
   - website; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices: The exact target remains a finite 396,150-class computation. Published generators settle the corpus size, while the checked Ising and matching papers provide context and a universal bound rather than the order-20 extremum.
3. <a id="reference-3"></a>OEIS A204198; Brendan D. McKay and Gordon F. Royle, Constructing the Cubic Graphs on up to 20 Vertices, Ars Combinatoria 21A (1986), 129-140; Gunnar Brinkmann, Jan Goedgebeur, and Brendan D. McKay, Generation of Cubic Graphs, DMTCS 13(2) (2011), 69-80. OEIS A204198; Brendan D. McKay and Gordon F. Royle, Constructing the Cubic Graphs on up to 20 Vertices, Ars Combinatoria 21A (1986), 129-140; Gunnar Brinkmann, Jan Goedgebeur, and Brendan D. McKay, Generation of Cubic Graphs, DMTCS 13(2) (2011), 69-80; term for 20 vertices and snarkhunter C3 program note https://oeis.org/A204198
   - Also cited at term for 20 vertices and snarkhunter C3 program note
   - reference_database; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices: The exact target remains a finite 396,150-class computation. Published generators settle the corpus size, while the checked Ising and matching papers provide context and a universal bound rather than the order-20 extremum.
4. <a id="reference-4"></a>Brendan D. McKay and Gordon F. Royle, Constructing the Cubic Graphs on up to 20 Vertices. users.cecs.anu.edu.au checked 2026-08-01. Ars Combinatoria 21A (1986), pages 129-140 https://users.cecs.anu.edu.au/~bdm/papers/Gobstoppers.pdf
   - website; reference source; PDF checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices: The exact target remains a finite 396,150-class computation. Published generators settle the corpus size, while the checked Ising and matching papers provide context and a universal bound rather than the order-20 extremum.