Combinatorics · existing Mathlib declaration

Kruskal–Katona Theorem

Take a finite family 𝒜 whose sets all have the same size, and a colex initial segment 𝒞 with no more members. Delete one element from every member and keep the distinct results. The colex family produces no more distinct one-step deletions than 𝒜 does.

extremal set theory
uniform set families
colex order
immediate shadows
set-family compression

The theorem at a glance

Kruskal–Katona Theorem at a glance

A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.

An ivory extremal-set-theory poster compares an r-uniform family with a colex initial segment, places the inequalities |C| at most |A| and |shadow(C)| at most |shadow(A)| in the central theorem panel, and follows a four-stage compression route to the exact one-step scope. — Among the compared finite r-uniform families, a colex initial segment of no greater cardinality has no larger immediate shadow.

Formal orientation

Statement map

This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.

Inspected at original pixels. The Scientific diagram keeps C and A as separate peer lanes with no inclusion or transformation arrow between them. It accurately shows the premise |C| ≤ |A|, one vertical immediate-shadow operator per lane, the exact membership definition T ∈ ∂F iff some S ∈ F has T ⊆ S and |S \ T| = 1, and the dominant conclusion |∂C| ≤ |∂A|. The four-to-three bead deletion icons remove exactly one marked element. The IMMEDIATE SHADOW ONLY footer, typography, margins, and line work pass; there is no iterated, binomial, equality-case, or decorative false-semantic content. — In this finite model, the four-set colex initial segment has six immediate-shadow members, no more than the comparison family’s nine.

Complementary intuition

A mathematical landmark

Kruskal–Katona is a foundational sharp extremal theorem for uniform set families. It identifies colex initial segments as canonical shadow minimizers and its Mathlib source exposes a particularly teachable route through compressions, a strictly decreasing family measure, and a terminal colex family.

The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.

Authoritative formal type

Exact Mathlib statement

theorem Finset.kruskal_katona {n r : ℕ} {𝒜 𝒞 : Finset (Finset (Fin n))} (h𝒜r : (𝒜 : Set (Finset (Fin n))).Sized r) (h𝒞𝒜 : #𝒞 ≤ #𝒜) (h𝒞 : Finset.Colex.IsInitSeg 𝒞 r) : #(∂ 𝒞) ≤ #(∂ 𝒜)

Selected evidence declaration text

theorem Finset.kruskal_katona {n r : ℕ} {𝒜 𝒞 : Finset (Finset (Fin n))} (h𝒜r : (𝒜 : Set (Finset (Fin n))).Sized r) (h𝒞𝒜 : #𝒞 ≤ #𝒜) (h𝒞 : Finset.Colex.IsInitSeg 𝒞 r) : #(∂ 𝒞) ≤ #(∂ 𝒜)

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.

Claim boundary

No new theorem is claimed

This page indexes Mathlib’s colex-initial-segment form of the Kruskal–Katona theorem for finite families of subsets of Fin n. The comparison family 𝒜 is r-uniform, 𝒞 is a colex initial segment of the r-subsets, and #𝒞 may be smaller than #𝒜. The selected endpoint compares only the cardinalities of their immediate one-element-deletion shadows. It is not the later iterated-shadow theorem, the Lovász/binomial formulation, an equality-case classification, a uniqueness theorem, or an algorithm.

ProofAtlas did not originate the Kruskal–Katona theorem or Mathlib’s declaration.
The selected declaration compares immediate shadows, not iterated shadows.
It is not the Lovász or closed binomial-expansion formulation.
It does not classify equality cases or assert a unique minimizing family.
The generated explanation and visuals are not proof evidence.

Provenance

Origin and evidence stay separate

Existing declaration: Finset.kruskal_katona in mathlib
Relationship: The checked artifact is the upstream declaration itself
Preferred checked artifact: artifact.library.mathlib.kruskal-katona-theorem.v001
Source handling: Verified upstream reference; no mirrored source package