Extremal & Geometric Combinatorics

← Back to Domain-Specific Families

Abstractions about polytopes, set systems, Ramsey-type theorems, extremal graph quantities, tilings, packings, and combinatorial conjectures.

13 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.

• 0/1-polytope — A convex polytope whose vertices are selected binary vectors from a finite-dimensional hypercube.
• Ahlswede–Daykin inequality — A four-functions inequality on a finite distributive lattice that lifts a pointwise join–meet product bound to corresponding sums over subsets.
• Baranyai's theorem — The theorem that a complete uniform hypergraph can be decomposed into perfect matchings whenever the edge size divides the number of vertices.
• Cereceda's conjecture — The conjecture that sufficiently many-color proper colorings of a d-degenerate graph can be reconfigured into one another by quadratically many single-vertex recolorings.
• Gilbert–Pollak conjecture — The assertion, now a theorem under accepted proof, that a Euclidean minimum spanning tree is at most 2/√3 times as long as a Steiner minimum tree on the same planar terminals.
• Gomory–Hu tree — A weighted tree representing every pairwise minimum-cut value of an undirected capacitated graph through the minimum edge on the corresponding tree path.
• Hales–Jewett theorem — A Ramsey-theoretic theorem guaranteeing a monochromatic combinatorial line in every sufficiently high-dimensional finite word cube.
• Helly family — A set family in which global intersection follows whenever every sufficiently small subfamily has nonempty intersection.
• Independence system — A finite ground set paired with a downward-closed family of feasible subsets containing the empty set.
• N-flake — Generate a family of polygonal self-similar attractors by placing contracted copies of a regular n-gon at its vertices, optionally adding a convention-controlled central copy, and iterating the resulting similarity system.
• Paris–Harrington theorem — A strengthened finite Ramsey statement that is true in the standard natural numbers but not provable in first-order Peano arithmetic.
• Penrose tiling — Cover the plane nonperiodically with a finite set of prototiles and matching rules that forbid translational periodicity yet produce repetitive local patches, inflation symmetry and long-range fivefold order.
• Turán number — The minimum number of r-element blocks on n vertices needed so every k-element vertex subset contains at least one block.