{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R645",
  "content_hash": null,
  "slug": "r55-claim-public-graph-lower-bound-43",
  "type": "claim",
  "title": "The cited public graph certifies R(5,5) at least 43",
  "summary": "The checked 42-vertex graph certifies \\(R(5,5)\\ge43\\); the order-43 witness remains missing, so existence of a 43-vertex graph with clique and independence number at most four remains open.",
  "relevance": "For A 43-vertex graph for the diagonal Ramsey problem R(5,5), record r55-claim-public-graph-lower-bound-43 (“The cited public graph certifies R(5,5) at least 43”) records a bound, answer, status fact, or structural consequence. The record states: The checked 42-vertex graph certifies \\(R(5,5)\\ge43\\); the order-43 witness remains missing, so existence of a 43-vertex graph with clique and independence number at most four remains open.",
  "relevance_source": "recorded",
  "body": "The first record of `r55_42some.g6` decodes to a graph \\(G\\) on 42 vertices with 425 edges. Exhaustive enumeration of its\n\\[\n\\binom{42}{5}=850{,}668\n\\]\nfive-vertex subsets gives the induced-edge histogram\n\\[\n[0,6078,31577,99576,192531,225712,173847,87463,27923,5961,0].\n\\]\nThe entries at positions 0 and 10 vanish. Thus every five-set has at least one edge and at least one nonedge. The graph contains no \\(K_5\\), and its complement contains no \\(K_5\\).\n\nBy definition, \\(R(5,5)\\) is the least order at which every graph contains a \\(K_5\\) or an independent five-set. This 42-vertex witness proves\n\\[\nR(5,5)>42,\\qquad R(5,5)\\geq43.\n\\]\nA 43-vertex witness would instead prove \\(R(5,5)\\geq44\\). The candidate asks for that larger witness. Its cited graph and digest have order 42.",
  "status": "reproduced",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "the first graph6 record in McKay's public r55_42some.g6 collection",
    "bounds": {
      "vertex_count": {
        "min": 42,
        "max": 42
      },
      "edge_count": {
        "min": 425,
        "max": 425
      },
      "subset_size": {
        "min": 5,
        "max": 5
      },
      "five_subsets": {
        "min": 850668,
        "max": 850668
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://users.cecs.anu.edu.au/~bdm/data/r55_42some.g6",
      "locator": "Brendan McKay, Combinatorial Data, r55_42some.g6, first line; independently decoded and checked on 2026-07-24"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://users.cecs.anu.edu.au/~bdm/data/r55_42some.g6",
    "locator": "Brendan McKay, Combinatorial Data, r55_42some.g6, first line; independently decoded and checked on 2026-07-24"
  },
  "relations": [
    {
      "slug": "R643",
      "title": "Exhaustive certificate for the first public 42-vertex graph",
      "object_type": "artifact",
      "relation": "evidences",
      "direction": "incoming"
    },
    {
      "slug": "R644",
      "title": "The order-43 witness remains missing",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "ramsey-55-43-graph",
      "title": "ramsey 55 43 graph",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}