Speculative Posets

Posets

Speculative design. Open, not settled — thinking and proposals, not shipped behavior. See Roadmap for what's in flight.

Status: speculative (2026-11-04). Tracks BL-325, for BL-201. Adds finite posets as a combinatorial carrier so FindStat's Posets and Lattices collections (85 and 34 statistics in the crawl, none adopted) have somewhere to land. Graphs are out of scope; the last section says what carries over.

"Measured" below means I computed it from the crawl (~/Playground/@enumeratio/findstat-crawl) or from posets I generated in Python; "assumed" means reasoned, not run. I did not run node, so nothing here has been compiled through compute-engine.

Recommendation

Add one carrier, Poset, with plural Posets(n) listing unlabeled posets by canonical representative, in a new posets/ area of @enumeratio/combinatorics beside graphs/. Lattices(n) is a restriction of Posets(n), not a second carrier. A value is a naturally labeled list of lower covers, so statistics read it with no packed n. Canonical form is a TypeScript kernel (refinement plus a search over a few natural labelings) held to an Epsil definition that is plain brute force, and Posets(n) through n = 8 comes from a table generated at build by that kernel.

First slice: the carrier, Posets(n) through n = 7, the reader and crosscheck wiring, and the statistics that need only the order relation: 21 basic ones, 2 Möbius ones, plus St000104 (closed form) and the antichain and chain counts. That is about 28 of the 85, each checkable against complete crawl data through n = 6.

What exists

• @enumeratio/incidence (packages/symbols/algebras/incidence) has Chain(n), BooleanLattice(n), DivisorLattice(n), IncidenceAlgebra, PosetElements, PosetInterval, PosetSumDown, PosetZeta, MoebiusFunction, MoebiusInvert. They are held expressions over a TypeScript Poset interface in src/poset.ts; there is no Poset head or type. PosetElements, PosetSumDown and PosetZeta are typed to accept only those three expressions. So the names Poset and Posets are free, and the Poset* heads are incidence-algebra heads that we widen later, not collisions.
• @enumeratio/structures protocols PartialOrder (Compare, NaN when incomparable) and Lattice (GreatestLowerBound, LeastUpperBound) describe a type whose values are ordered (numbers, partitions by dominance). A poset as an object is the other thing: a structure whose elements are ordered. The protocols are not usable for the carrier. They are usable for building a Poset from an ordered collection (Poset(IntegerPartitions(5)) through Compare), a later constructor overload. Lattice is a protocol name, so no singular Lattice carrier.
• LinearExtensionCount (reference/LinearExtensionCount) is a tree statistic that happens to count linear extensions of the tree poset. No poset carrier is involved.
• Graph precedents: LabeledGraph is tuple<integer, list<list<integer>>> with carrierParams: 1 (graphs/src/carrier-data.ts); IsIsomorphicGraph is brute force over n! with a cheap prefilter and declines past 9 vertices; UnlabeledFreeTrees and RootedUnlabeledTrees are isomorphism-class collections, but they rank through counting tables specific to trees, which posets don't have.

1. What an object is

FindStat spells a poset ([(0,1),(0,2)],3): cover relations (a,b) meaning a < b, on 0..n−1, then n. Measured: all 111,738 rows in the two collections parse that way, and the direction is a < b (a model of "minimal elements" matches St000068's 902 rows with n ≤ 7).

The spelling is FindStat's own labeling, not a canonical one we can recompute: 72,104 of the 111,738 rows (64.5%) have a cover (a,b) with a ≥ b, so it is not even a natural labeling. But each isomorphism class has exactly one spelling: I canonicalized every row with n ≤ 7 (1,598 classes across both collections) and found no class with two spellings, and no statistic with two rows in one class. Counts of classes seen are 1, 1, 2, 5, 16, 63, 318 for Posets n = 0..6 and 1, 1, 1, 1, 2, 5, 15, 53 for Lattices n = 0..7, which are the known counts.

Value. Poset is list<list<integer>>: entry i (elements are 1-based, like our other carriers' values) is the ascending list of elements that i covers, and every one is less than i (a natural labeling). n is the length. The 3-chain is [[],[1],[2]], the V is [[],[1],[1]], the antichain is [[],[],[]].

Why this and not (n, covers) like LabeledGraph:

• No packed params. Nothing in src/statistics reads a carrierParams carrier today (no graph statistic exists), so I can't say how CombinatorialStat hands a packed tuple to a definition. A single list is the shape set-partition statistics already use.
• Natural labeling means the down-set of i is the union of the down-sets of its lower covers, all with smaller index, so the order relation is one pass in index order rather than n rounds of closure. This is assumed to compile; not tried.
• Canonical form stays inside the carrier (below).

Risk: an empty inner list ([] for a minimal element) may type as list<never> and be declined. Set-partition blocks are never empty, so there's no precedent. Fallback is a one-element sentinel; probe this first.

valid checks: entries ascending, each below its index, and no cover implied by two others (transitively reduced). The constructor does not reduce; reducing an arbitrary relation is a conversion overload.

Isomorphism. A statistic is an invariant, so it never needs the canonical form. Four things do: rank in Posets(n), Unique-style statistics over derived posets, comparing a map's poset output with FindStat's, and matching the crawl in find-findstat.ts. Heads: CanonicalPoset(P) (Wolfram has CanonicalGraph) and IsIsomorphicPoset(P, Q) (follows IsIsomorphicGraph). Equality of values stays structural; two isomorphic values are not equal.

Canonical form. The strict order read as bits for pairs (1,2), (1,3), …, (n−1,n), first pair most significant, is the code; the canonical labeling is the natural labeling with the least code. The code is an invariant and determines the poset, so it is complete. It fits a double through n = 10 (45 bits).

The Epsil definition is brute force over natural labelings, correct and only usable to about n = 6. The kernel does color refinement first (down-set size, up-set size, then the multiset of neighbors' colors), collapses twins (elements with equal up- and down-sets), and searches the rest. Measured on all classes (generated, counts match 1, 2, 5, 16, 63, 318, 2045, 16999, 183231 for n = 1..9):

n	classes	labelings per class after refinement: mean / max	after twin collapse: mean / max
6	318	7.1 / 720	1.57 / 36
7	2045	7.7 / 5040	1.52 / 36
8	16999	7.8 / 40320	1.55 / 576

Brute force over all natural labelings averages 105 per class at n = 7 and 329 at n = 8 (their linear extension counts) but reaches n! on the antichain. A kernel is justified under the rule: the definition stays the meaning, the kernel is the verified fast path (agreement test through n = 6, then counts against A000112 and the crawl). Whether refinement can be written in Epsil without Sort is open; a color can be ranked by counting distinct smaller colors and a multiset of colors summed as Σ B^color with B = n+1, exact for n ≤ 13. That is assumed, not tried.

Cost in Python, single thread, unoptimized: building all classes through n = 9 by adding a maximal element to each class below (every poset has one, over each order ideal) and deduplicating by canonical form took 49 s. Canonical-form calls: 766, 5,439, 48,346, 550,338 for n = 6..9. This is the generation algorithm; the same kernel serves it.

2. Carrier and collections

• Poset, type poset, id poset, plural Posets (structures/src/carriers.ts Carrier record). Stub record reference/Poset/ with catalogCarrier: true as DecoratedPermutation and PerfectMatching have today.
• Posets(n): one canonical representative per isomorphism class, ordered by the code (numeric, as for cut sets and bit vectors). The antichain is first and the chain last. FindStat's and Sage's orders are not stable, so nothing is borrowed. Count is A000112: 1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231 (measured through n = 9); 2567284 at n = 10 is from memory.
• Rank, unrank, count, membership: the table of codes, sorted. Unrank is At; rank is IndexOf after CanonicalPoset; membership is valid plus "equals its own canonical code". The table is generated at build by the kernel, gitignored, and compared with the Epsil definition through n = 6 and with the counts above (AGENTS.md: derived data is built, not committed). Whether a family's tables can hold a large literal is untested; I found only expression-valued tables (collections/src/families/epsil.ts).
• Feasible n: Epsil definition through 6 (3,749 labelings across all 766 generation steps); table through 7 certainly, 8 (about 1 MB as FindStat-style spellings, 17K entries, measured: 991,794 characters; as integer codes it should be several times smaller, not measured). n = 9 is 183K entries and belongs in a lazily loaded record (#407), not core.
• Lattices. Lattices(n) restricts Posets(n) by IsLattice (every pair has a join and a meet) and takes the induced order, per the restriction ruling. Measured: filtering my generated posets gives 1, 1, 1, 2, 5, 15, 53, 222 for n = 1..8, equal to the crawl's complete rows. Past n = 8 the filter over Posets is too slow and the table carries its own lattice list. FindStat's Lattices maps to the Poset carrier with this restriction; there is no Lattice constructor.
• Labeled or naturally labeled as their own carriers. By the carrier-choice rule they qualify: they are counted (labeled posets 1, 3, 19, 219, 4231, 130023; naturally labeled 1, 2, 7, 40, 357, 4824; both measured n ≤ 6) and ordered. No crawl collection or statistic uses them, so they are LabeledPosets(n) and NaturallyLabeledPosets(n) as later restrictions of the same carrier, with Posets(n) the canonical-section restriction. Since the carrier value is already naturally labeled, only the first needs a wider valid.

3. Triage of the 85 Posets and 34 Lattices statistics

A regex pass over title, description and Sage code, then 32 hand corrections of misfires and refinements (it first put St000639, the relation count, under algebraic because the description mentions the incidence algebra). Buckets are by what the definition needs.

Bucket	Posets	Lattices	Examples
Order only (closure, local counts)	21	18 meet/join-local	St000068/069 extremal elements, 080 rank, 181 components, 189 size, 327 covers, 527 width, 528 height, 639 relations, 717/1268 ordinal summands, 1396–1398 incomparable triples, pairs and V's, 1717/1718 intervals, 1902 potential covers; lattices St001621 atoms, 1622 join-irreducibles, 1624 breadth, 550 modular elements, 1833 linear intervals
Subset families: chains, antichains, ideals	20	0	070 antichains, 071/909/910 maximal chains, 180 chains, 912 maximal antichains, 307/1782 rowmotion, 656 cuts, 680 Hackendot, 1709/1815 order-preserving maps
Möbius	2	1	914 sum of μ, 1890 max magnitude; lattice St001625
Linear extensions	10	0	100 count, 298 order dimension, 632 jump number, 848–850 balance, 1105/1106 greedy, 1510 evacuation, 1779 promotion
Order polytope, order complex	7	0	104, 151 facets, 1300/1301 order complex, 1532–1534 cone Poincaré
Algebraic (Coxeter, modules, quiver)	11	5	1472, 1634, 1635 Coxeter matrix, 1631–1633, 1636 modules (GAP/QPA), 1942 quiver loops; lattices 1630, 1875–1878
Automorphisms and endomorphisms	4	0	633, 634, 635, 1399
Isomorphism or the whole collection	10	2	1664, 1095, 1343, 640/641 (canonical form of derived posets); 524–526 (all posets of size n); 281/282 (preimage of a tree map); lattices 1619, 1666
Lattice sublattice enumeration	0	8	1620 sublattices, 1626, 1677/1679/1681 subsets with meet 0, 1754 tolerances, 1618 Frattini, 1881 factors

Totals check: Posets 21+20+2+10+7+11+4+10 = 85; Lattices 18+1+8+5+2 = 34.

Reading it:

• 43 of the 85 posets (basic, subset families, Möbius) and 19 of the 34 lattices (meet/join-local plus Möbius) need only the order relation and, at most, enumerating subsets. Subset enumeration is cheap at these sizes: order ideals per class average 23.6 (max 128) at n = 7 and 32.4 (max 256) at n = 8, measured, and linear extensions count by dynamic programming over ideals, so cost is ideals × n, not n!.
• Some geometric ones are closed forms. St000104 equals covers + minimal + maximal elements (Stanley); I checked it against all 405 rows. The others in that bucket (chain polytope facets, Betti numbers, cone polynomials) are not reached by a first batch.
• The algebraic bucket (16 across both) stays out. @enumeratio/quiver exists (not examined) and may reach St001942 later. Lattice St001630 and 1875–1878 carry no Sage code at all.
• The isomorphism bucket is the one that makes canonical form load-bearing, and the last two rows of the table are different: 524–526 need Posets(n) itself and an order polynomial or polytope per member, and 281/282 need the tree-to-poset maps.
• Hazard found while modeling: St000845 is titled "covered by an element" but its rows and Sage code (max out_degree) give the number of elements covering one. St000846 is the mirror. I modeled 14 statistics against every crawl row with n ≤ 7 (about 12,000 rows, from St000068 to St001397, Möbius sum included): all agree except 845, which agrees under the code's reading (1,249 of 1,249). Model against rows first, as the batch briefs already say.

4. Compile shape

Everything below is assumed; compute-engine was not run.

• Input is _x, the lower-cover lists. A statistic first builds the relation as a flat row-major list<integer> of n² 0/1 entries, one pass in index order. Flat because the fold typing rule accepts a list<integer> accumulator (collections/src/families/tables.ts, 6th argument), and a nested list<list<integer>> accumulator has no precedent here; set-partitions/src/statistics.ts builds its nested crossing matrix with Map, not a fold.
• No Sort, no bit operations (the CORE list in tests/statistics-core.test.ts has none): counting replaces both. Masks as integers would need Mod/Divide; avoid them.
• Chains and antichains: enumerate subsets of Range(1, 2^n) by digit extraction, or DP over ideals. n ≤ 8 is at most 256 ideals. The risk is And over partial operands and If branches of different shape, both on the 0.177 rules list.
• Walks over linear extensions (St000848–850, 1105, 1106, 1510, 1779) and order dimension (298) are heavier than the ideal DP: assumed to need per-pair DP or a search, and may decline.
• Recursion over ideals (St000680, the Grundy value) needs memoization the compiler does not have; likely interpreted.

5. Crosscheck wiring

Registered in three places that today all skip a collection silently when it's absent, which is the failure to design against.

• findstat/src/objects.ts: READERS.Poset parses ([(a,b),…],n), relabels to a natural labeling in TypeScript (no Sort needed at the boundary), and returns lower-cover lists; size is n. Add "Posets": "Poset" and "Lattices": "Poset" to COLLECTION_CARRIER.
• packages/reference/scripts/find-findstat.ts, CARRIERS.Poset: collection: "Posets"; sizes 1..6 and small 1..5 (sizes with complete crawl data; Lattices 1..7); objects from the table; box to the value. The FindStat domain id (Cc00xx) is not verified: the repo uses only Cc0001, 2, 5, 6, 9, 10, 21, and the API's collection listing (ids only, no names) has Cc0007, Cc0012–Cc0014 and Cc0017–Cc0030 besides.
• spell is the trap. findInCrawl looks up data.has(carrier.spell(object)). Our canonical labeling is not FindStat's, so every lookup misses, checkable.length < sweep.length * 0.9 fails, and every candidate is dropped with —. Fix: in crawl mode key the crawl by CanonicalCode(parse(spelling)) and spell ours the same way. The online finder (find) posts our spelling; whether FindStat canonicalizes it is unverified, so poset matching is crawl-mode only.
• findstat/tests/distribution-crosscheck.test.ts: needs COLLECTIONS.Poset = ["Posets", n => n] and the reader. The tally comparison needs no canonical form, because distinct spellings equal distinct classes (measured, n ≤ 7). Three silent skips to close:
  • COLLECTIONS[match.on] and COLLECTION_CARRIER[entry.collection] absent: continue, no trace. Add a floor: every adopted poset statistic must compare at least one size ≥ 5 or the test fails (the existing REPRESENTATIVE test already asserts this per head; add the poset heads).
  • A size with fewer rows than classes goes to skipped, which is printed only in deep mode. The crawl is complete through n = 6 for 70 of 79 Posets statistics with rows at n = 6 (and n = 7 for 32 of 33 Lattices statistics), never complete for n = 7 Posets (53 to 1,112 rows of 2,045). Say that in the test's header.
  • The committed snapshot cannot test posets. findstat/data/statistics.json keeps eight rows per statistic; for St000068 they are the antichains of sizes 1 to 8, so no size past the trivial ones is complete. The default run would compare almost nothing. For posets, sample by size: all rows through n = 5 is 87 per statistic, about 7,400 rows for 85 statistics (computed from the class counts, not written).
• Also add a per-object check next to the tally: evaluate our definition on each parsed crawl object and compare with its row. It needs no canonical form and catches a wrong statistic that a tally hides.
• Maps (31 in MapsDatabase touch posets or lattices). The map check reproduces FindStat's image text exactly; a poset-valued map such as Mp00125 (dual) or Mp00013 (tree to poset) yields our labeling, so compare CanonicalPoset of both sides.

6. Reference and display

Needed first: the stub record, Posets(n) with enumerate: and carrier: Poset, and one glyph: kind so the collection table (notatio-collection-table's glyph column) shows a picture. The existing kinds are in frontend/src/glyphs.ts and chosen by the record's glyph: field through scripts/build-glyphs.ts; treeLayout is the nearest layout. A Hasse diagram needs a layered layout: rows by height, order within a row by a barycenter pass, which is adequate at n ≤ 8 (not tried). A hasse glyph kind is the cheap route; GraphicsBox lowering for glyphs is parked (BL-152), so don't wait on it.

Can wait: a Show frame, interactive Hasse editing, Graph interop (Wolfram's Graph head is inert, Graph has no drawing today), and a lattice-specific picture.

7. External conventions

• Wolfram. No poset type in the built-ins. packages/wolfram/src/system-names.ts has TransitiveReductionGraph, TransitiveClosureGraph, TopologicalSort, AcyclicGraphQ, RelationGraph, CanonicalGraph, IsomorphicGraphQ, GraphAutomorphismGroup, and none of HasseDiagram, PartialOrderQ or LatticeQ. The Function Repository has HasseDiagram (a binary relation and a set, returning a Graph); I checked once and only that. Legacy Combinatorica has HasseDiagram, PartialOrderQ, MaximumAntichain, MinimumChainPartition (Combinatorica-Audit §1.7). So the oracle maps a Poset to a directed Graph of its covers, and CanonicalPoset has no Wolfram counterpart beyond CanonicalGraph of that.
• Sage. Poset, Posets(n), LatticePoset, cover_relations, hasse_diagram, canonical_label, is_isomorphic, chains, antichains, linear_extensions, order_ideals_lattice. Sage's Poset is the origin of FindStat's spelling. Posets(n) is a generator, not an ordered collection.
• Mathlib. PartialOrder, Lattice, Order.CovBy, IsChain, IsAntichain, Order.Ideal — names from memory, not checked. Mathlib has no unlabeled finite poset object.
• Names. Follow no-abbreviations: IsLattice, IsIsomorphicPoset, CanonicalPoset. Do not mint Chains/Antichains for subsets: Chain(n) already means the n-element chain poset. Extend the existing Poset* pattern (PosetChains, PosetAntichains, PosetOrderIdeals) or name them after what they list; this is an open question below.

8. Phases and rough cost

My estimates, in builder-lane batches, not measured.

1. Carrier and collection (one PR). posets/ area, carrier record, kernel (canonical code, generation), generated table through n = 8, Epsil definition through n = 6 with agreement test, counts against A000112, reader, find-findstat.ts and test wiring including the snapshot change, stub record, a hasse glyph. Largest risks: the empty-list typing and the table mechanism.
2. First statistics. The 21 basic and 2 Möbius ones, St000104, and the antichain and chain counts; a few Lattices statistics through IsLattice. Reuse MoebiusFunction from incidence only after the next phase, otherwise write μ inline.
3. Incidence bridge. incidence adds combinatorics to extends (no cycle seen: combinatorics extends structures, residues and groupalgebra, none of which extend incidence), Poset(Chain(4)) and friends as constructor overloads, and PosetElements, PosetZeta, MoebiusFunction accept poset.
4. Subset and linear-extension families, LabeledPosets, the isomorphism bucket (needs phase 1's kernel and CanonicalPoset on derived posets), poset-valued maps (dual, order ideals, tree to poset).
5. Lattices beyond the filter, n = 9 as a lazy record, algebraic bucket only if the quiver package helps.

What carries to Graphs. The crawl spells graphs the same way: ([(0,1),(0,2),(1,2)],3), and rows are complete through n = 7 (1, 2, 4, 11, 34, 156, 1044 classes, measured as distinct spellings; n = 8 is partial). What transfers: the CanonicalCode kernel (refinement, twin collapse, search; graphs use vertex addition and a symmetric adjacency code), crawl-mode matching by canonical key, the size-sampled snapshot, the silent-skip floors, generation by canonical augmentation, and IsIsomorphic…/Canonical… heads (IsIsomorphicGraph is the existing brute-force one and would be replaced by the kernel). What doesn't: the natural-labeling trick and the lower-cover shape. A graph has no linear extension to label it by, so its canonical code is the least adjacency code over all refinement-respecting labelings. Design the kernel on adjacency from the start with the natural-labeling constraint as a poset-only filter. Whether the unlabeled graph carrier is Graph or something else is unsettled and not decided here; Graph is already Wolfram's inert head.

9. Open questions for Dean

1. Value shape. Naturally labeled lower-cover lists (recommended), or (n, covers) like LabeledGraph. The deciding fact is that no statistic yet reads a packed carrier; probe both in phase 1 if you prefer the pair.
2. Order of Posets(n). Numeric on the canonical code (recommended), or by number of relations then code, which groups sparse posets first and reads better in a table. Either is a one-line change before the first release and a rename-sized break after.
3. Where the table starts and stops. Generated, gitignored, through n = 8 in core and n = 9 lazy (recommended), or n = 7 only. n = 8 is about 17K entries.
4. Names for subset families. Antichains(P), OrderIdeals(P), LinearExtensions(P) as collections of a poset (recommended, matching Sage), against the Poset prefix of the incidence heads. Chains(P) next to Chain(n) reads badly; I'd name it PosetChains for that reason alone.
5. Package edge. incidence extends combinatorics (recommended), or the carrier moves into incidence. The first keeps the carrier beside graphs and FindStat tooling.
6. Snapshot size for posets. Grow data/statistics.json to all rows through n = 5 for the 119 poset and lattice statistics (recommended, roughly 10K rows at 87 per statistic for Posets plus fewer for Lattices, not measured), or accept a deep-run-only check as the permutation snapshot effectively is.

Measured versus assumed

Measured: crawl coverage per size and class counts; the one-spelling-per-class result; 14 statistics against their rows; St000104 closed form; class and lattice counts n ≤ 9 and ≤ 8; canonical-form work counts; ideal and linear-extension statistics; labeled and naturally labeled counts to n = 6; the silent-skip paths and the snapshot's coverage (read from the code and data); the bucket counts.

Assumed or unverified: anything about compute-engine compilation and typing; the table mechanism in a family; Sort-free refinement in Epsil; FindStat's domain id and whether its finder canonicalizes input; the Mathlib names; Function Repository coverage beyond one search; counts past n = 9 (recalled); effort estimates; the layered layout.