Skip to content

Speculative Graphs

enumeratio edited this page Nov 16, 2026 · 8 revisions

Unlabeled graphs

Speculative. A proposal, not adopted.

Adds graphs up to isomorphism: a canonical form, the collection of canonical representatives, and what both unlock. FindStat lists graphs up to isomorphism and we list them labeled, so today nothing of ours can be compared with a FindStat graph except object by object, and no map with a graph for its image is adopted. Posets is the sibling design; this page is the graph half of what its last section promised.

"Measured" below means I computed it from the crawl (~/Playground/@enumeratio/findstat-crawl) or from graphs I generated in Python. "Assumed" means reasoned, not run. Nothing here has been run through compute-engine.

Recommendation

No new carrier. A graph up to isomorphism is the LabeledGraph whose rank in LabeledGraphs(n) is least among its relabelings, and UnlabeledGraphs(n) is the restriction of LabeledGraphs(n) to those, in the induced order. The 159 graph statistics apply to its members as they are.

  • CanonicalGraph(g) returns that labeling. Its Epsil definition is the least rank over all n! relabelings; a TypeScript kernel is the fast path.
  • The same kernel generates UnlabeledGraphs(n) through n = 8 (12,346 classes), because the canonical form is hereditary: a canonical graph with its first vertex removed is canonical (§2).
  • Comparing two graphs, or a map's graph image with FindStat's, is comparing canonical ranks.

The work, in order:

  1. The snapshot rule for graph statistics. A small change of its own, after the posets slice lands (§6). In CI the 159 statistics are held to FindStat on seven graphs without edges and one edge.
  2. The canonical form and the collection (one lane, §9): CanonicalGraph, the kernel, UnlabeledGraphs(n), IsIsomorphicGraph through the kernel. Built in #1380 (open); what the lane measured is under "As built" in §2.
  3. Graph-valued maps: 20 of the 24 unadopted maps that touch graphs have a graph, a poset or a lattice for an image. They have their own triage, a draft not yet on the wiki.
  4. Statistics the canonical form unlocks: 30 of the 154 unadopted ones (§4).

What exists

  • Two graph layers. Graph(…) is the Wolfram-style object (collections/src/graphs.ts): vertices and edges, directed or not, weights and options; GraphDistance, ConnectedComponents, IsIsomorphicGraph and the constructors (WheelGraph, …) work on it, and GraphPlot draws it (frontend/src/graph.ts). LabeledGraph is the combinatorial carrier (graphs/src/carrier-data.ts): Tuple(n, edges), type labeled_graph, with carrierParams: 1. Tournament is the other carrier there, of the same shape.
  • Collections. LabeledGraphs(n): "the edges present, ascending; edge k is present iff bit k − 1 of the rank is set", with the pairs (u < v) numbered 1..C(n, 2) in lex order (graphs/src/families/epsil.ts). LabeledGraphsByEdges(n, m) in colex order, with a fast kernel. Tournaments(n). No collection of graphs up to isomorphism, connected graphs, or any other class.
  • Unlabeled trees are the precedent for a class collection. UnlabeledFreeTrees(n) and RootedUnlabeledTrees(n) are their own carriers (trees/src/carrier-data.ts), a level sequence in a canonical order, listed so each class is hit once (trees/src/families/unlabeled-trees.ts, collections/src/families/exact-classes.ts).
  • Isomorphism. IsIsomorphicGraph(g, h) on Graph objects: every permutation after a filter on size, edge count and degree sequence, declining past 9 vertices (collections/src/graphs-2.ts, ISOMORPHISM_VERTEX_LIMIT). No CanonicalGraph, no automorphism head.
  • Statistics. 159 definitions on LabeledGraph (graphs/src/statistics.ts), each reading _x = Tuple(n, edges) through withGraph, each with an independent reading and a FindStat row. FindStat has 313 statistics on Graphs (measured); 154 are not adopted. The frontier list is empty (graphs/src/statistics.frontier.ts).
  • Maps. Four, all from a graph to a partition: Mp00037, Mp00251, Mp00275, Mp00276. FindStat has 28 maps touching Graphs (measured).
  • Crosscheck. Object by object (OBJECT_WISE.LabeledGraph = { standard: 5, deep: 7 } in findstat/tests/crosscheck-sweep.ts); READERS.LabeledGraph parses FindStat's spelling. The finder (packages/reference/scripts/find-findstat.ts) has no entry for graphs.

1. What an object is

FindStat spells a graph ([(0,1),(0,2)],3): edges on 0..n−1, then n. Measured on the 313 statistics:

  • Distinct spellings by n = 0..7: 1, 1, 2, 4, 11, 34, 156, 1044, the number of graphs (A000088). At n = 8 the crawl has 3,220 of 12,346.
  • Each class has exactly one spelling (canonicalized every row with n ≤ 7).
  • The spelling is not ours and not recomputable: 20 of the 1,251 spellings with 2 ≤ n ≤ 7 are the labeling of least rank.
  • Rows are complete through n = 6 for 281 of the 313 statistics. At n = 7 most have 992 of the 1,044 classes; four have all of them.

Value. A LabeledGraph, unchanged: Tuple(n, edges), vertices 1..n, edges [u, v] with u < v, ascending.

Canonical form. The canonical labeling of a graph is the relabeling whose rank in LabeledGraphs(n) is least. The rank is an integer below 2^C(n,2), so it fits a double through n = 10 (45 bits). It is an invariant and it determines the graph, so two graphs are isomorphic exactly when their canonical ranks are equal.

Why this code and not another:

  • It is a collection we have. The canonical representative, its rank among labeled graphs, and the order of the unlabeled collection are one definition, and a test can hold the induced order.
  • Posets §9 answer 2 leans to the same pair numbering for posets, so a naturally labeled poset's code is its comparability graph's rank here.
  • Sage's canonical_label and nauty's canonical form depend on the algorithm's choices and cannot be stated as a definition. The least rank can: the least over the n! relabelings.

What it looks like (measured, n ≤ 8): the graph without edges is first (rank 0), then one edge [1,2] (rank 1), then the path [1,2],[1,3] (rank 3); the complete graph is last, and before it the complete graph without the edge [n−1, n]. Edges gather on the low labels.

valid for a member of UnlabeledGraphs(n): a valid LabeledGraph that equals its own canonical form.

2. The kernel

The search. The pairs with first element a are a block of n − a bits, and blocks with larger a are more significant. So the least rank is found by choosing a vertex for label n, then n − 1, and so on down: at each level only the candidates whose block is least go on, and ties branch. Twins (two vertices with the same neighbours apart from each other) among the tied candidates are one branch. No refinement, no automorphism group.

Measured in Python against brute force over all n! labelings, on every class through n = 7: no disagreement. Search nodes per graph:

n classes nodes, mean nodes, max
5 34 34 111
6 156 88 306
7 1,044 212 1,065

Symmetric graphs past 8 vertices. A map's image can be larger and more regular than anything in the collection (a line graph, a clique graph). Search nodes, measured: the Petersen graph 4,360; the line graph of K5 2,920; the 12-cycle 69,984; the icosahedron 6,264; the Paley graph on 13 vertices 8,437; the 4 × 4 rook's graph on 16 vertices 92,704. So the search needs no automorphism pruning for these. Past 10 vertices the rank does not fit a double (66 bits at 12 vertices): the comparison is by the list of blocks, or by a big integer.

The form is hereditary. The pairs that contain vertex 1 are the low n − 1 bits, and the rest is the rank of the graph on vertices 2..n. So rank(G) = rank(G − 1) · 2^(n−1) + (the neighbours of vertex 1), and if G is canonical then G − 1 is: a smaller relabeling of G − 1 would lower the high bits. Measured: every canonical graph through n = 7 has a canonical graph above its low bits.

Generation. So the canonical graphs on n vertices are among the candidates h · 2^(n−1) + S, for h canonical on n − 1 vertices and S any of the 2^(n−1) neighbour sets, and a candidate is tested by the search, which stops at the first level where some labeling has a smaller block. Measured:

n candidates canonical nodes per test Python, whole size
6 1,088 156 72 0.1 s
7 9,984 1,044 170 1.3 s
8 133,632 12,346 381 37 s
9 3,160,576 274,668 (A000088) not run not run

The n = 8 run gave 12,346 classes and contains every n = 8 spelling in the crawl. In TypeScript the first UnlabeledGraphs(8) takes about 0.6 s (as built, below).

If the search needs to be faster. Colour refinement (degree, then the multiset of neighbours' colours) leaves many labelings on graphs, unlike posets: after refinement and twin collapse the classes at n = 8 average 41 labelings and 3,070 of the 12,346 keep more than one (posets at n = 8: 1.55). Refinement is not a canonical form by itself here, and it does not give the least rank, so it can only prune the search above, by proving two tied candidates equivalent. Not needed through n = 7.

Where the definition reaches. The Epsil definition of CanonicalGraph is n! ranks. The definition of the collection is every rank below 2^C(n,2) tested against n! relabelings: n ≤ 4 in the standard run (64 × 24), n = 5 in a deep one (1,024 × 120). Past that the kernel is held by the counts (A000088) and by the crawl's spellings, each of which must canonicalize into the list.

As built (#1380, open; the lane's measurements on a build box):

  • The search is depth-first with a best-so-far bound, on plain numbers. Level by level, as the prototype ran it, it ran out of memory on cycles.
  • The collection. UnlabeledGraphs(n) gives A000088 through 8 vertices, ascending, and stays unevaluated past 8. Brute force over all n! labelings agrees through 5 vertices. The first UnlabeledGraphs(8) in a fresh process takes about 0.62 s; the worst graph of each size through 8 canonicalizes in under 0.05 ms.
  • The definitions run over the ranks of the permutations, 0 .. n! − 1 unranked in lex order, not over Permutations(n): that collection holds permutation values and does not compile. Compiled, the collection's count takes 0.3 s at n = 5 and about 86 s at n = 6; interpreted, 3 s at n = 3. The kernel is held to the definition through n = 4 in the standard run and n = 5 in a deep one, as planned.
  • IsIsomorphicGraph answers by canonical form through 16 vertices, for LabeledGraph values and for Graph objects that are undirected, unweighted and without loops. The limit is set by the path on 16 vertices (1.5 million branches, 0.2 s), not by a strongly regular graph. Directed, weighted and looped graphs keep the permutation route and its limit of 9.
  • Open: a call that can hang. The CanonicalGraph kernel declines past 30 vertices or 2 million branches, and the definition then runs: n! relabelings. So a large call can run without end where it should stay unevaluated. A map's definition cannot decline, for the reason a statistic's cannot (Lattices, question 1).
  • Declared cost. The family's costs are declared polynomial. Declared enumerative with a work bound, the engine refused Count(UnlabeledGraphs(6)).
  • The verdict snapshot. A new family over LabeledGraph changes the compile samples, which makes every graph statistic's verdict row stale: all 159 were collected again (47 minutes) and agree. Editing a family's declared does the same to its own row.
  • Wolfram. CanonicalGraph's Wolfram row is marked domain and has not been scanned: the transpiler hands Wolfram a bare edge list. The next rescan decides it.

3. Carrier and collection

Two ways to hold the classes:

Restriction of LabeledGraph A carrier of its own, UnlabeledGraph
Value a LabeledGraph equal to its canonical form the same tuple under another type, or the rank alone
The 159 statistics apply as they are need the second type on every signature, or a conversion at every use
Order induced from LabeledGraphs(n) its own, which would be the same
Precedent Lattices(n) as a restriction of Posets(n); a section of a quotient is a restriction (the 2026-09-29 framing: set partitions as a section of set compositions) UnlabeledFreeTree, whose value is a level sequence with a shape of its own
Equality two isomorphic LabeledGraph values stay unequal; CanonicalGraph or IsIsomorphicGraph compares could be equality of values

Lean: the restriction. The carrier-choice rule makes a form a carrier when it is counted and ordered in its own right, and unlabeled graphs are counted. But the tree carriers earn theirs with a value of a different shape; here the value would be the same tuple, and a second type would cost every statistic an overload for nothing it computes differently.

  • UnlabeledGraphs(n), carrier LabeledGraph, carrierParams: 1. One member per class, in the induced order of LabeledGraphs(n): ascending rank. Count A000088: 1, 1, 2, 4, 11, 34, 156, 1044, 12346 (measured through n = 8), 274668, 12005168.
  • Rank, unrank, count, membership: the sorted list of canonical ranks for n, as for posets. Unrank is At; rank is the position of the graph's canonical rank; membership is valid.
  • Where the list comes from. The family's fast kernel generates size n from size n − 1 (§2) the first time it is asked and keeps the list for the process. The Epsil definition is the meaning; tests/fast-kernels.test.ts holds the two together where the definition reaches.
  • Feasible n. The kernel through 8. At 9 it declines with a message, until tables that load on demand exist (Data tables). Measured at n = 8: the 12,346 ranks are 12.9 KB delta-encoded, about a byte a rank, and 3.4 KB after gzip, so the 274,668 at n = 9 are likely a few hundred KB (assumed). n = 10 is 12 million and stays out.
  • Later restrictions, each a filter of this one in the induced order: connected graphs (A001349), trees as graphs, bipartite, regular. None is needed first. UnlabeledGraphsByEdges(n, m) would be a sibling in another order, as LabeledGraphsByEdges is.
  • Tournaments. The same search on a code over ordered pairs gives unlabeled tournaments. Not in the first slice; design the kernel's adjacency so a directed code is a second reading of it.

4. Triage of the 154 unadopted statistics

By what a definition needs, from title and Sage code. The buckets are a first pass; four of them were then modeled against rows (below).

Bucket Count Examples
Automorphisms 9 St000244 order of the group, 349 distinct adjacency matrices, 388 vertex orbits, 469 distinguishing number, 1783 odd automorphisms
The whole collection 15 1272 graphs with the same degree sequence, 1282 same chromatic polynomial, 1496/1518 same spectrum, 1570, 1575–1578 fewest edge changes to reach a class, 276/283 preimages of a tree map
Distinct up to isomorphism 6 86/87 subgraphs, 299 induced subtrees, 1349 graphs after removing an edge, 1834 minors, 1704 decks
Tutte and chromatic polynomial 8 267 spanning forests, 268 strongly connected orientations, 948, 1109, 1546, 1795, 1796
Colourings 18 172 Grundy number, 271 chromatic index, 1108–1112 dynamic, 1116/1117 game, 1580 acyclic, 1581 achromatic, 1725 harmonious
Vertex orders: patterns 10 1317, 1319, 1320, 1324–1329, 1334: the fewest occurrences of a pattern over all orders of the vertices; one helper serves all ten
Vertex orders: widths 8 272 treewidth, 536 pathwidth, 537 cutwidth, 1270 bandwidth, 1963 tree-depth
Exact spectrum 10 422, 454, 455, 718 integral eigenvalues; 773, 775 multiplicities; 1774–1776 degrees of minimal polynomials
Games and processes 12 258 burning, 482 zero forcing, 544 cops, 1056/1057 Grundy values, 1373 lights out, 1645 pebbling
Subsets and paths 41 636 hull number, 778 metric dimension, 822 Hadwiger, 1333–1340 isolating sets, 1792 arboricity, 1802 endomorphisms
Modular decomposition 4 1352–1354, 1356
Polytopes and commutative algebra 6 301, 1261, 1844, 1986–1988
Topological, or no code 7 322 skewness, 323 crossing number, 370 genus, 479 Ramsey, 741 Colin de Verdière, 1512 minimum rank

Totals: 154.

Reading it:

  • Modeled. The automorphism, distinct-up-to-isomorphism, pattern and polynomial rows (33 statistics) were each read from FindStat's definition in Python and compared with every crawl row. 31 agree on all rows. 26 of those need nothing this design adds: the nine automorphism ones and the ten patterns are a fold over the n! orders of the vertices (5,040 at n = 7), and seven of the polynomial ones are subset expansions. Three need CanonicalGraph (87, 299, 1349) and two need UnlabeledGraphs(n) (86, 1704). Left out: 1795, whose row for the single vertex contradicts its own code, and 1834.
  • Titles the rows contradict, found by modeling: 364 is the exponent of the automorphism group, not the description's least common multiple of orbit sizes (which is wrong on 143 of 1,200 rows); 1796 divides the number of spanning trees, 0 for a disconnected graph, not the Tutte value at (1, 1); 86 counts spanning subgraphs only.
  • No adopted graph statistic folds over Permutations(n) today, so that is the first thing a batch tries: 19 of the 26 depend on it. The canonical-form lane has since found that Permutations(n) does not compile and folded over the permutations' ranks instead (§2, as built).
  • Decided (Dean, 2026-11-15): the head names the triage proposes for the 26, and its recommended answers. AutomorphismGroupSize joins the existing tree head as an overload; the ten patterns are Minimum…PatternOccurrenceCount through one helper; the folds decline past a cap on n and the polynomial ones past a cap on edges; 1795 and 1834 stay out; the five that need the canonical form or the collection wait for it.
  • "The whole collection" (not modeled) needs UnlabeledGraphs(n) itself and a statistic per member: 1,044 members at n = 7, each compared with the argument. Likely interpreted, with a cap.
  • The subsets, colourings and orders rows are the same kind of work as the adopted 159 (bitmask folds, a fold over Permutations(n)), only costlier. They are batches of their own and do not wait on this.
  • The last three rows stay out.

5. Maps

Of the 28 FindStat maps that touch Graphs, four are adopted. The other 24 (measured from the crawl's domains and codomains): 13 from graphs to graphs (complement, line graph, square, cone, core, …), 7 into graphs (from binary and ordered trees, posets, permutations, compositions, lattices), and 4 from graphs elsewhere (two to compositions, one to posets, one to lattices).

The map check compares our image with FindStat's by JSON.stringify (findstat/tests/map-findstat.test.ts). A graph image is our labeling against FindStat's, so both sides go through CanonicalGraph first. That is the first use of the canonical form outside the collection, and the reason it is in the first lane.

All 24 were then modeled in Python, each reading compared with every crawl row up to isomorphism, and every reading agrees with its rows:

  • Ready, 16: complement, Ore closure, square, line graph, connected complement, cone, de-duplicate, clique graph, vertex addition, delete endpoints, block-cut tree, the graph of a binary tree and of an ordered tree, the graph of inversions, the threshold graph of a composition, and the chromatic difference sequence (a composition image, so it needs no canonical form).
  • Need the poset carrier, 5: the graph and the incomparability graph of a poset, the zero-divisor graph of a lattice, and the two with a poset or lattice for an image, which need CanonicalPoset.
  • Hard, 3: the core (graph homomorphisms; brute force reaches 6 vertices), the dual on components (planarity and faces), Laplacian multiplicities (exact eigenvalues).
  • Readings that the rows rule out: the Ore closure with the graph's order as its threshold; the zero-divisor graph by joins, as its title says, where the rows use meets.
  • Images reach 12 vertices and more, which is why the comparison cannot be a double (§2).

Names, and the order of the new vertices where a map creates them, are in the maps triage.

Decided (Dean, 2026-11-15): the names the triage proposes and its recommended answers. One UnderlyingGraph head over binary trees, ordered trees and posets; LineGraph as an overload of the head that exists; GraphComplement and GraphSquare; both sides of every comparison through the canonical form, by the search of §2 (the triage asked for a refinement kernel before §2's measurements on symmetric images, which make it unnecessary); the finder's comparison changes in the same lane; the core waits.

6. Crosscheck, snapshot and finder

  • The snapshot is weak for graphs, as it was for posets. The standard run reads findstat/data/statistics.json, which keeps the eight shortest spellings of each statistic (smallest(raw.StatisticData, 8) in packages/reference/scripts/collect-findstat-data.ts). Measured: for 222 of the 313 graph statistics those are the graphs without edges on 1 to 7 vertices and the single edge; for 49 more, six without edges and two with one edge. Almost any definition passes on those. The whole crawl is read only in a deep run with FINDSTAT_CRAWL set, which no workflow sets.
  • The rule posets take applies here (Posets §9 answer 6, decided): a collection compared object by object keeps every row up to a size. For graphs through n = 5 that is 51 rows a statistic and 15,834 rows in all, about 530 KB on a file of 949 KB (measured as JSON pairs). Through n = 4 it is 18 rows a statistic and 127 KB, but a statistic that first differs on a 5-cycle or on K5 passes. OBJECT_WISE already compares through 5 in the standard run, so n = 5 makes the standard run do what its table says.
  • A larger sample may fail. The 159 definitions passed the crawl in someone's deep run, on some engine. If a row disagrees on the larger snapshot, it is a finding: the definition or the reading is fixed, never the row dropped.
  • Done in #1377 (open; the lane's numbers). The snapshot keeps every Graphs row through 5 vertices for all 313 statistics: 2,504 graph rows before, 15,834 after, and statistics.json grows from 1.27 MB to 1.95 MB (it had already grown with the poset rows). The standard crosscheck reads 8,084 objects against 996 before and finds no disagreement, in 11.5 s against 8.2 s. So the adopted definitions do pass the larger sample. The collector reads the crawl from --crawl <folder>, not from FINDSTAT_CRAWL.
  • The finder. find-findstat.ts has no graph carrier. With the collection it gets one: collection: "Graphs", objects from UnlabeledGraphs(n) for n ≤ 6 (complete in the crawl), and in crawl mode the crawl keyed by canonical rank, since our spelling never equals FindStat's (Posets §5, "spell is the trap"). FindStat's collection id for graphs is not verified.
  • A tally by size becomes possible with the collection and adds nothing the object-wise check lacks, since each class has one spelling.

7. Heads and names

  • CanonicalGraph(g): Wolfram's name (packages/wolfram/src/system-names.ts has CanonicalGraph, IsomorphicGraphQ, GraphAutomorphismGroup). On a LabeledGraph it returns a LabeledGraph. On a Graph object it can return a Graph later; Wolfram's canonical labeling is not ours, so the oracle compares by IsomorphicGraphQ, not by value.
  • IsIsomorphicGraph(g, h) keeps its name and answers by comparing canonical ranks. For LabeledGraph arguments this is new; for Graph objects it replaces the search over all permutations, and the 9-vertex limit moves to what a measurement supports. Directed and weighted Graph objects keep today's path until the kernel reads a directed code.
  • UnlabeledGraphs(n), not Graphs(n). A plural head is the collection of what its singular builds, and Graph(…) builds the Wolfram-style object, not a member of this collection. UnlabeledFreeTrees and LabeledGraphs are the pattern. FindStat's Graphs and Sage's graphs(n) go in the record's crosswalk.
  • No predicate head for "is canonical": it is CanonicalGraph(g) == g.
  • Sage: canonical_label, is_isomorphic, automorphism_group, graphs(n) (a generator through nauty's geng, in its own order). OEIS: A000088, A001349 (connected). From memory, not checked: Mathlib has SimpleGraph.Iso and no canonical form.

8. Questions, with their answers

All seven are decided as recommended (Dean, 2026-11-15). The names of the statistics and the maps are not among them.

  1. Carrier. Decided: none new; UnlabeledGraphs(n) restricts LabeledGraphs(n) (§3).
    • What would change it: wanting equality of values to mean isomorphism. Then a carrier whose value is the canonical graph, with LabeledGraph values converted by its constructor.
  2. Name. Decided: UnlabeledGraphs(n) (§7).
    • Graphs(n) is shorter and is what FindStat, Sage and the OEIS say. It would make Graph and Graphs unrelated heads.
    • Posets differ, and that is consistent: Poset is the carrier's own constructor, so Posets(n) is its plural.
  3. The canonical form is the least rank in LabeledGraphs(n). Decided: yes (§1).
    • It fixes the order of the collection for good: At(UnlabeledGraphs(n), k) is the k-th canonical rank. A different code later is a different collection.
    • The alternative with the most prior art is the greatest code with the last vertex's pairs most significant (Read's and Faradzev's orderly generation). It is hereditary in the same way and is not a collection we have.
  4. Where the list stops. Decided: the kernel through n = 8, declining at 9; measure the first UnlabeledGraphs(8) in TypeScript before deciding anything else.
    • If it takes more than about a second: prune ties by refinement, or build n = 8 as a table, which waits on the data-tables design. Measured: about 0.62 s, so neither.
  5. The snapshot for graph statistics. Decided: every row through n = 5, for all 313 statistics.
    • The cost is about 530 KB in a committed file of 949 KB. Keeping the larger sample only for adopted statistics halves that and makes the collector read our adoption list; the finder then sees less for the rest.
  6. IsIsomorphicGraph's limit. Decided: raise it only to what a grid measures on the kernel, hard cases included (strongly regular graphs, where ties are widest), and keep declining past it. Measured: 16, set by the path (§2, as built).
  7. Unlabeled tournaments. Decided: later, as a second reading of the same kernel; not in the first lane.

9. Slices

Estimates in builder lanes, not measured.

  1. Snapshot (#1377; small; after posets slice 1 merges, since it adds the per-collection rule to the collector): Graphs through n = 5 in collect-findstat-data.ts, the snapshot regenerated, the standard graph crosscheck run on it. Any disagreement is written up, not fixed in the same change unless it is one line.
  2. Canonical form and collection (#1380, open; one lane, one pull request):
    • the kernel: the block search, checked against all n! labelings through n = 6 and against the crawl through n = 7;
    • CanonicalGraph with its Epsil definition and the kernel as its fast path, and its record;
    • UnlabeledGraphs(n): the family with its Epsil definition and a fast kernel that generates by §2, counts against A000088 through 8, every crawl spelling through n = 8 canonicalizing into the list, the record with enumerate:, a graph glyph;
    • IsIsomorphicGraph on LabeledGraph values by canonical rank; the Graph-object path only if it falls out;
    • a helper the map check can call to compare two graph images up to isomorphism, with one test, unused until the maps batch;
    • timings: the first UnlabeledGraphs(7) and (8), and CanonicalGraph on the worst graph of each size.
  3. Graph maps, first batch.
  4. Statistics: automorphisms and distinct-up-to-isomorphism first (15), then the whole-collection ones with a cap, then the ordinary batches by bucket.
  5. The finder's graph carrier; unlabeled tournaments; n = 9 once tables load on demand.

Measured versus assumed

Measured (Python, on the crawl and on generated graphs): the statistic and map counts; the spellings per size and one spelling per class; that the crawl's labeling is not the least rank; the search against brute force through n = 7 and its node counts; heredity through n = 7; the candidate and class counts of the generation through n = 8, and its Python time; the labelings left by refinement and twins; the shape of the eight shortest spellings; the row counts and sizes of a snapshot through n = 4, 5 and 6.

Measured by the canonical-form lane (#1380): the times in TypeScript, that the Epsil definitions compile and how far they reach (§2, as built).

Assumed: the size of an n = 9 table; the triage buckets, which come from titles and code and were not modeled against rows; that the 159 adopted definitions pass a larger snapshot.

Not checked: whether IsIsomorphicGraph accepts a LabeledGraph value today; FindStat's collection id for graphs; which 52 classes most statistics lack at n = 7.

Home

Project

Working

Design: every design page, by subject

Clone this wiki locally