{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R175",
  "content_hash": null,
  "slug": "cubic20ising-claim-certified-interval-36-254658",
  "type": "claim",
  "title": "The certified interval is 36 through 254,658 ground states",
  "summary": "An explicit 3-connected cubic graph has 36 ground states, while a matching-partition-function theorem gives a universal upper bound of 254,658.",
  "relevance": "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.",
  "relevance_source": "recorded",
  "body": "Let \\(D_{20}\\) be the maximum in the question. The checked evidence gives\n\\[\n\\boxed{36\\leq D_{20}\\leq254{,}658}.\n\\]\nThe 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.\n\nFor 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,\n\\[\nM_G(1)\\leq34^{20/6}=34^{10/3}<127{,}330,\n\\]\nso the integer count satisfies \\(M_G(1)\\leq127{,}329\\), giving \\(D_{20}\\leq254{,}658\\).\n\nThe exact value still requires an isomorph-free sweep of the 396,150 relevant graph classes or a sharper structural argument.",
  "status": "open",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "simple 3-connected cubic graphs on exactly 20 vertices, with both members of each globally flipped spin pair counted",
    "bounds": {
      "vertices": {
        "min": 20,
        "max": 20
      },
      "degree": {
        "min": 3,
        "max": 3
      },
      "vertex_connectivity": {
        "min": 3,
        "max": 3
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1508.04675",
      "locator": "Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, Theorem 3 and its integrated matching-partition-function consequence"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1508.04675",
    "locator": "Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, Theorem 3 and its integrated matching-partition-function consequence"
  },
  "relations": [
    {
      "slug": "R176",
      "title": "A 3-connected cubic graph has exactly 36 ground states",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R177",
      "title": "Every connected cubic graph on 20 vertices has at most 254,658 ground states",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R174",
      "title": "The exact target remains a finite 396,150-class computation",
      "object_type": "attempt",
      "relation": "contextualizes",
      "direction": "incoming"
    },
    {
      "slug": "cubic-graph-twenty-ising-degeneracy",
      "title": "cubic graph twenty ising degeneracy",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}