{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R669",
  "content_hash": null,
  "slug": "rnfc9-claim-exact-beta-one-distribution",
  "type": "claim",
  "title": "Exactly 50,766,340,113 graphs have nonzero first homology",
  "summary": "The exact probability is 50,766,340,113 divided by 68,719,476,736, approximately 0.7387474777788157.",
  "relevance": "This records a result, observation, or conjecture used to assess the target problem.",
  "relevance_source": "derived",
  "body": "Among the \\(2^{36}=68{,}719{,}476{,}736\\) labeled graphs on nine vertices, exactly\n\\[\n50{,}766{,}340{,}113\n\\]\nhave \\(H_1(X(G);\\mathbb F_2)\\ne0\\). The fraction is already reduced because its numerator is odd:\n\\[\n\\Pr\\bigl(H_1(X(G);\\mathbb F_2)\\ne0\\bigr)\n=\\frac{50{,}766{,}340{,}113}{68{,}719{,}476{,}736}\n\\approx0.7387474777788157.\n\\]\n\nThe full labeled distribution of \\(\\beta_1\\) is\n\\[\n\\begin{array}{c|rrrrrrrrrrrrr}\n\\beta_1&0&1&2&3&4&5&6&7&8&9&10&11&12\\\\ \\hline\n\\#G&17{,}953{,}136{,}623&21{,}459{,}770{,}001&16{,}840{,}187{,}301&8{,}590{,}760{,}010&2{,}991{,}956{,}730&731{,}552{,}976&131{,}963{,}406&17{,}710{,}560&2{,}177{,}532&234{,}927&24{,}024&2{,}520&126.\n\\end{array}\n\\]\nThe entries sum to \\(2^{36}\\). The top value has a simple check: each labeled \\(K_{4,5}\\) has no triangles and has cycle rank \\(20-9+1=12\\), and there are \\(\\binom94=126\\) such graphs.\n\nThe computation generated all 274,668 isomorphism classes of nine-vertex simple graphs. For each representative \\(G\\), it computed \\(\\beta_1\\), then added the orbit weight \\(9!/|\\operatorname{Aut}(G)|\\) to the appropriate bin. The weights over all classes sum to \\(9\\)-vertex labeled graph count \\(2^{36}\\).",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "every simple graph on the fixed labeled vertex set {0,1,2,3,4,5,6,7,8}, with homology over F_2",
    "bounds": {
      "vertices": {
        "min": 9,
        "max": 9
      },
      "possible_edges": {
        "min": 36,
        "max": 36
      },
      "labeled_graphs": {
        "min": 68719476736,
        "max": 68719476736
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/math/0605536",
      "locator": "Exact certificate in rnfc9-artifact-nauty-orbit-boundary-rank"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/math/0605536",
    "locator": "Exact certificate in rnfc9-artifact-nauty-orbit-boundary-rank"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R668",
      "title": "First homology needs only edges, components, and triangle boundaries",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R665",
      "title": "Exact nauty orbit and triangle-boundary certificate",
      "object_type": "artifact",
      "relation": "reproduces",
      "direction": "incoming"
    },
    {
      "slug": "R667",
      "title": "The primary literature gives asymptotics rather than this finite table",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "random-nine-flag-complex-beta-one",
      "title": "random nine flag complex beta one",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}