Order Theory & Combinatorial Structure

← Back to Domain-Specific Families

Abstractions about lattices, order types, distributivity, well-quasi-ordering, cuts, combinatorial matrices, set systems, and ordered enumeration.

14 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Completely distributive lattice — A complete lattice in which arbitrary meets distribute over arbitrary joins according to the choice-function identity, equivalently satisfying the self-dual complete distributivity law.
• Dedekind cut — Represent a boundary in a linear order by a downward-closed lower part with no greatest element, constructing order completion and the real numbers from rational cuts.
• Distributivity (order theory) — A family of order-theoretic laws governing how infima and suprema interact, from finite lattice distributivity to complete and infinite distributive variants.
• Frink ideal — A subset I of a partially ordered set such that every common lower bound of the common upper bounds of each finite subset of I also belongs to I.
• Hadamard matrix — Arrange signs in a square matrix so every pair of distinct rows, and therefore columns, is orthogonal, equivalently satisfying the exact Gram identity \(HH^{\mathsf T}=nI\).
• Lah number — A signed or unsigned combinatorial coefficient converting rising factorials to falling factorials and counting partitions of n labeled elements into k nonempty linearly ordered lists.
• Law of trichotomy — The order principle that for every two elements exactly one of x<y, x=y or y<x holds, equivalently combining connectedness with asymmetry for a strict order.
• Order polynomial — The polynomial whose value at n counts order-preserving maps from a finite poset to an n-element chain.
• Order type — The isomorphism class of an ordered set under order-preserving bijection, capturing its ordering structure independently of element names.
• Overlap coefficient — A set-similarity measure equal to intersection size divided by the size of the smaller set, reaching one whenever either set contains the other.
• Perfect ruler — An integer-marked ruler for which every distance through a stated maximum occurs exactly once as a positive difference between two marks.
• Sauer–Shelah lemma — An extremal bound stating that a set family of VC dimension d on an n-element ground set has at most the sum of binomial(n,i) for i from zero through d members.
• Transseries — Formal generalized series built from nested powers, exponentials and logarithms and ordered by asymptotic dominance, supporting algebra, differentiation and solution of differential equations beyond ordinary power series.
• Well-quasi-ordering — A quasi-order in which every infinite sequence contains an earlier element below a later one, equivalently having neither infinite descending chains nor infinite antichains.