{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R665",
  "content_hash": null,
  "slug": "rnfc9-artifact-nauty-orbit-boundary-rank",
  "type": "artifact",
  "title": "Exact nauty orbit and triangle-boundary certificate",
  "summary": "A C++ checker enumerates 274,668 graph classes, computes beta one by XOR elimination, and recovers the full labeled distribution.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "The checker uses tinygraph commit `97665350689943d64b90ca1501b3291db0538a0a`, whose generator is backed by nauty 2.6r6. `Graph::enumerate(9, ...)` visits one representative of every isomorphism class. `numLabeledGraphs()` supplies \\(9!/|\\operatorname{Aut}(G)|\\).\n\nFor each representative, union-find gives the component count. Lexicographic edge indices identify each triangle boundary with a 36-bit word. Highest-pivot XOR elimination gives its exact rank over \\(\\mathbb F_2\\). The resulting beta value receives the full labeled orbit weight.\n\nThe run found 196,389 positive classes and a labeled favorable weight of 50,766,340,113. All orbit weights sum to 68,719,476,736. The unlabeled beta histogram sums to 274,668, and its labeled counterpart sums to \\(2^{36}\\).\n\nThe generation-order serialization hashes, for every class, its graph6 record, a zero byte, eight little-endian bytes of orbit weight, then one byte each for component count, edge count, triangle count, boundary rank, and beta one. Its FNV-1a 64-bit checksum is `5771132747119421409`. The executed source has SHA-256 `d82620acd91bea3cf11f20f91aedb8c05cd7b7ec054fd3501f524b5a636d7289`. The four-line standard output has SHA-256 `f9f953771ea551bb9b2cdf126ded76fe31eaea090a32a7d41f38a8a3fb8e491b`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all isomorphism classes of nine-vertex simple graphs, weighted by 9!/|Aut(G)| after exact F_2 elimination of the triangle-boundary matrix",
    "bounds": {
      "vertices": {
        "min": 9,
        "max": 9
      },
      "unlabeled_graphs": {
        "min": 274668,
        "max": 274668
      },
      "labeled_weight_sum": {
        "min": 68719476736,
        "max": 68719476736
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp14_orbit_computation",
    "entrypoint": "Join source_lines with LF characters, compile against tinygraph Graph.o, Set.o, geng.o and its nauty objects, then run the executable",
    "runtime": "C++14, tinygraph commit 97665350689943d64b90ca1501b3291db0538a0a, and nauty 2.6r6",
    "citation": {
      "url": "https://github.com/falk-hueffner/tinygraph/tree/97665350689943d64b90ca1501b3291db0538a0a",
      "locator": "C++14 computation executed against tinygraph 9766535 and nauty 2.6r6 on 2026-07-25"
    },
    "outputs": "unlabeled=274668 labeled=68719476736 positive_unlabeled=196389 positive_labeled=50766340113\nbeta_unlabeled=0:78279,1:82775,2:64285,3:32469,4:12292,5:3369,6:929,7:190,8:58,9:16,10:4,11:1,12:1\nbeta_labeled=0:17953136623,1:21459770001,2:16840187301,3:8590760010,4:2991956730,5:731552976,6:131963406,7:17710560,8:2177532,9:234927,10:24024,11:2520,12:126\nrecords_fnv64=5771132747119421409\n",
    "inline_source": [
      "#include \"Graph.hh\"",
      "#include <array>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <map>",
      "",
      "struct H { int c, e, t, r, b; };",
      "",
      "H h1(const Graph& g) {",
      "    std::array<int,9> p;",
      "    for (int i=0;i<9;++i) p[i]=i;",
      "    auto root = [&](int x) {",
      "        while (p[x]!=x) { p[x]=p[p[x]]; x=p[x]; }",
      "        return x;",
      "    };",
      "    int ei[9][9], k=0;",
      "    for (int u=0;u<9;++u) for (int v=u+1;v<9;++v) {",
      "        ei[u][v]=ei[v][u]=k++;",
      "        if (g.hasEdge(u,v)) {",
      "            int a=root(u), b=root(v);",
      "            if (a!=b) p[a]=b;",
      "        }",
      "    }",
      "    int c=0;",
      "    for (int u=0;u<9;++u) if (root(u)==u) ++c;",
      "    std::array<uint64_t,36> basis{};",
      "    int rank=0, triangles=0;",
      "    for (int a=0;a<9;++a) for (int b=a+1;b<9;++b) {",
      "        if (!g.hasEdge(a,b)) continue;",
      "        for (int d=b+1;d<9;++d) {",
      "            if (!g.hasEdge(a,d)||!g.hasEdge(b,d)) continue;",
      "            ++triangles;",
      "            uint64_t x=(UINT64_C(1)<<ei[a][b])|",
      "                       (UINT64_C(1)<<ei[a][d])|",
      "                       (UINT64_C(1)<<ei[b][d]);",
      "            while (x) {",
      "                int q=63-__builtin_clzll(x);",
      "                if (basis[q]) x^=basis[q];",
      "                else { basis[q]=x; ++rank; break; }",
      "            }",
      "        }",
      "    }",
      "    int e=g.m(), beta=e-9+c-rank;",
      "    return {c,e,triangles,rank,beta};",
      "}",
      "",
      "int main() {",
      "    uint64_t nu=0,nl=0,pu=0,pl=0,fnv=UINT64_C(14695981039346656037);",
      "    std::map<int,uint64_t> hu,hl;",
      "    Graph::enumerate(9,[&](const Graph& g){",
      "        ++nu;",
      "        uint64_t w=g.numLabeledGraphs();",
      "        H x=h1(g);",
      "        nl+=w; hu[x.b]++; hl[x.b]+=w;",
      "        if(x.b){++pu;pl+=w;}",
      "        std::string s=g.graph6();",
      "        for(unsigned char q:s){fnv^=q;fnv*=UINT64_C(1099511628211);}",
      "        fnv^=0;fnv*=UINT64_C(1099511628211);",
      "        for(int i=0;i<8;++i){fnv^=(w>>(8*i))&255;fnv*=UINT64_C(1099511628211);}",
      "        for(int q:{x.c,x.e,x.t,x.r,x.b}){fnv^=q;fnv*=UINT64_C(1099511628211);}",
      "    });",
      "    auto out=[](auto h){bool f=true;for(auto x:h){if(!f)std::cout<<',';f=false;std::cout<<x.first<<':'<<x.second;}std::cout<<'\\n';};",
      "    std::cout<<\"unlabeled=\"<<nu<<\" labeled=\"<<nl<<\" positive_unlabeled=\"<<pu<<\" positive_labeled=\"<<pl<<\"\\n\";",
      "    std::cout<<\"beta_unlabeled=\";out(hu);",
      "    std::cout<<\"beta_labeled=\";out(hl);",
      "    std::cout<<\"records_fnv64=\"<<fnv<<\"\\n\";",
      "}"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://github.com/falk-hueffner/tinygraph/tree/97665350689943d64b90ca1501b3291db0538a0a",
    "locator": "C++14 computation executed against tinygraph 9766535 and nauty 2.6r6 on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R669",
      "title": "Exactly 50,766,340,113 graphs have nonzero first homology",
      "object_type": "claim",
      "relation": "reproduces",
      "direction": "outgoing"
    },
    {
      "slug": "R666",
      "title": "Independent labeled boundary-rank regression at six vertices",
      "object_type": "artifact",
      "relation": "cross_checks",
      "direction": "incoming"
    },
    {
      "slug": "random-nine-flag-complex-beta-one",
      "title": "random nine flag complex beta one",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}