{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R668",
  "content_hash": null,
  "slug": "rnfc9-claim-boundary-rank-formula",
  "type": "claim",
  "title": "First homology needs only edges, components, and triangle boundaries",
  "summary": "For a graph with n vertices, m edges, c components, and triangle-boundary rank r over F_2, beta one equals m minus n plus c minus r.",
  "relevance": "This records a result, observation, or conjecture used to assess the target problem.",
  "relevance_source": "derived",
  "body": "Let \\(B\\) be the edge-by-triangle matrix over \\(\\mathbb F_2\\). A triangle column has a one in each of its three edge rows. The graph boundary map \\(\\partial_1:C_1\\to C_0\\) has rank \\(n-c\\), so\n\\[\n\\dim\\ker\\partial_1=m-n+c.\n\\]\nThe image of \\(\\partial_2:C_2\\to C_1\\) is the column space of \\(B\\). Therefore\n\\[\n\\beta_1(X(G);\\mathbb F_2)=m-n+c-\\operatorname{rank}_{\\mathbb F_2}B.\n\\]\nCliques with four or more vertices add higher-dimensional simplices and do not change either map in this formula. The orbit computation stores every triangle boundary as a 36-bit word and performs exact Gaussian elimination with XOR.",
  "status": "established",
  "evidence_grade": "verified",
  "scope": {
    "kind": "universal",
    "statement": "the first homology over F_2 of the clique complex of any finite simple graph"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/math/0605536",
      "locator": "Standard simplicial chain-complex calculation; clique-complex model as defined in Matthew Kahle, Topology of random clique complexes, Discrete Mathematics 309 (2009), 1658-1671"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/math/0605536",
    "locator": "Standard simplicial chain-complex calculation; clique-complex model as defined in Matthew Kahle, Topology of random clique complexes, Discrete Mathematics 309 (2009), 1658-1671"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R669",
      "title": "Exactly 50,766,340,113 graphs have nonzero first homology",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "random-nine-flag-complex-beta-one",
      "title": "random nine flag complex beta one",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}