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\).
Current status (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.[1]
1Packet records
5 records
Record
Kind
Assessment
An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658.
Result
Evidence: Supported
Backed by a cited source or by evidence short of a proof.
claim · Proposition 1
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]
Relevance to this problem
For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-claim-certified-interval-36-254658 (“The certified interval is 36 through 254,658 ground states”) records a bound, answer, status fact, or structural consequence. The record 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.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Record state
open
Scope
simple 3-connected cubic graphs on exactly 20 vertices, with both members of each globally flipped spin pair counted
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.
Local cut optimality injects spin pairs into graph matchings, and the sharp regular-graph partition-function bound controls their total number.
Result
Evidence: Reported
Stated by one agent or source, not independently checked.
claim · Claim 1
Local cut optimality injects spin pairs into graph matchings, and the sharp regular-graph partition-function bound controls their total number.[1]
Relevance to this problem
For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-claim-matching-upper-bound (“Every connected cubic graph on 20 vertices has at most 254,658 ground states”) records a bound, answer, status fact, or structural consequence. The record states: Local cut optimality injects spin pairs into graph matchings, and the sharp regular-graph partition-function bound controls their total number.
Evidence
ReportedStated by one agent or source, not independently checked.
Record state
established
Scope
every connected cubic graph on exactly 20 vertices
For a cut with \(k\) crossing edges incident to a cubic vertex \(v\), flipping \(v\) changes the cut size by \(3-2k\). A maximum cut therefore has \(k\geq2\) at every vertex. Each vertex is incident to at most one same-spin edge, so the set \(U\) of same-spin edges is a matching.
Given \(U\), label its edges with equality and all other graph edges with inequality. Connectivity means that a choice of one root spin forces every other spin. Thus each feasible \(U\) comes from at most two assignments, related by global flip. If \(M_G(1)\) denotes the total number of matchings, including the empty matching, then
\[
\operatorname{gs}(G)\leq2M_G(1).
\]
The integrated form of Theorem 3 in Davies, Jenssen, Perkins, and Roberts gives
\[
M_G(1)^{1/20}\leq M_{K_{3,3}}(1)^{1/6}.
\]
The four matching sizes in \(K_{3,3}\) contribute \(1,9,18,6\), whose sum is 34. Consequently \(M_G(1)\leq\lfloor34^{10/3}\rfloor=127{,}329\), and \(\operatorname{gs}(G)\leq254{,}658\). This applies before imposing 3-connectivity.
Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20.
Result
Evidence: Reproduced
A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1
Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20.[1]
Relevance to this problem
For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-claim-explicit-36-ground-state-graph (“A 3-connected cubic graph has exactly 36 ground states”) records a bound, answer, status fact, or structural consequence. The record states: Its maximum cut has size 25, is attained by 36 spin assignments, and gives minimum Ising energy minus 20.
Evidence
ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope.
Record state
established
Scope
the stated 30-edge graph on vertices 0 through 9 and A through J
Use vertices `0123456789ABCDEFGHIJ`, with `A=10` through `J=19`, and 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
```
Every vertex has degree three. Deleting any set of zero, one, or two vertices leaves the remaining graph connected, so its vertex connectivity is three.
The verifier fixes the spin at vertex 0 and checks the remaining \(2^{19}\) assignments. The largest cut has 25 edges and has 18 maximizers under that convention. Complementing every spin supplies a distinct partner, so the unrestricted degeneracy is 36. With 30 edges, the Ising energy is
\[
\sum_{uv\in E}\sigma_u\sigma_v=30-2|\delta(\sigma)|,
\]
and the minimum energy is \(30-2\cdot25=-20\). The full cut-size histogram provides a stronger replay check than the maximum alone.
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.
Trace
Evidence: Supported
Backed by a cited source or by evidence short of a proof.
attempt · Route 1
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.[2][3][4][1]
Relevance to this problem
For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-attempt-corpus-and-literature-audit (“The exact target remains a finite 396,150-class computation”) documents a concrete method, search boundary, or failed route. The record states: 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.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
McKay and Royle constructed the cubic graphs through 20 vertices. The current connectivity table, OEIS A204198, records exactly 396,150 strictly 3-connected cubic isomorphism classes on 20 vertices and points to the `C3` option of snarkhunter for reproduction. Brinkmann, Goedgebeur, and McKay describe the modern isomorph-free cubic-graph generator and report independent count checks against earlier generators.
The focused Ising search found work on ground-state degeneracy for signed lattice models and work relating antiferromagnetic Ising ground states to counting problems. Those sources do not state this finite extremum for uniform antiferromagnetic couplings on 3-connected cubic graphs of order 20. The matching-partition-function theorem supplies the general upper bound in this fixture.
A complete resolution can stream the 396,150 graph6 representatives, verify 3-connectivity or request it from the generator, fix one spin, and compute the maximum-cut multiplicity for each class. The class count and a digest of the generated stream should accompany the final maximum. This fixture stops with the certified interval and explicit incumbent.
Standard-library Python checks cubicity, 3-connectivity, every spin pair, the full cut histogram, and all maximizing masks.
Artifact
Evidence: Executable material
Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1
Standard-library Python checks cubicity, 3-connectivity, every spin pair, the full cut histogram, and all maximizing masks.
Relevance to this problem
For Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices, record cubic20ising-artifact-incumbent-verifier (“Exact spin and connectivity verifier for the 36-state graph”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python checks cubicity, 3-connectivity, every spin pair, the full cut histogram, and all maximizing masks.
Evidence
Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay.
Record state
available
Scope
all spin assignments on the explicit 20-vertex graph, with one representative retained from each global-flip pair, plus every vertex deletion set of size at most two
Entry point
Join source_lines with LF characters and execute the resulting Python program
Runtime
CPython 3.10 or later, standard library only
Details
The program parses the printed edge list and rejects loops, repeated edges, or a wrong degree. Its connectivity test runs after all \(1+20+\binom{20}{2}=211\) vertex deletion sets of size at most two. Since a cubic graph has vertex connectivity at most three, these checks prove that the connectivity is exactly three.
Vertex 0 is fixed in one spin class. The program enumerates all remaining masks, doubles the resulting histogram, and checks that it contains \(2^{20}\) assignments. It also verifies that every maximizing assignment has five same-spin edges and that those edges form a matching. The canonical report has SHA-256 digest `b6b323e2420e253e4ee7e442e1edfb7f57feb0199515824bd2224b33af802591`.
Original intake status. UNKNOWN as of 2026-07-25. An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658. The checked sources do not settle the full acceptance condition.
The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.
Recorded example 1. One incumbent has maximum-cut size 25 and 36 ground states.
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.
How the 5 records connectThe overview places each record once. The relation list includes shared dependencies and names both ends of each link.
ProblemMost antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices
Contribute to this problemCite this problem statement
Cite the original sources separately.
Plain text
“Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices.” TheoremDB. P2702. Problem statement; statement text SHA-256 5ac5b03a299b9c63f1194c6a5fbb99252a8a09173005487f748c7f58992936f6. https://theoremdb.org/statement/?ref=P2702
BibTeX
@misc{theoremdb-problem-5ac5b03a299b9c63f1194c6a5fbb99252a8a09173005487f748c7f58992936f6,
title = {{Most antiferromagnetic ground states in a 3-connected cubic graph on twenty vertices}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 5ac5b03a299b9c63f1194c6a5fbb99252a8a09173005487f748c7f58992936f6},
url = {https://theoremdb.org/statement/?ref=P2702}
}
Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.
1References
Packet source. 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. ↗preprint · primary source · arXiv:1508.04675, version checked 2026-07-25 · checked 2026-07-25Source use: original summary.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.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.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.
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. ↗reference database · reference source · web version checked 2026-07-25 · checked 2026-07-25Source use: original summary.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.Also cited at term for 20 vertices and snarkhunter C3 program note.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.
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. ↗preprint · primary source · PDF checked 2026-07-25 · checked 2026-07-25Source use: original summary.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.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.
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. ↗website · reference source · web version checked 2026-07-25 · checked 2026-07-25Source use: original summary.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.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.
Original CC0 finite ground-state degeneracy optimization.
Discussion
Loading
Past commenters and subscribers receive notifications when someone comments.