The Kruskal–Katona theorem
ProvedFamousTheorems.kruskal_katonaThe Kruskal–Katona theorem. Among all families of -element subsets of , the initial segment of length in the colexicographic order has the smallest shadow. The shadow of a family is the set of all -subsets of its members. Concretely, if is -uniform and is a colex initial segment of -sets with , then .
It determines exactly which -vectors occur for simplicial complexes. It is the source of the Lovász version of the shadow bound and a standard route to the Erdős–Ko–Rado theorem.
Formalization note. Mathlib's Finset.kruskal_katona; Finset.shadow is the shadow and Finset.Colex.IsInitSeg 𝒞 r says 𝒞 is an initial segment of the colex order on r-sets.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem kruskal_katona {n r : ℕ} {𝒜 𝒞 : Finset (Finset (Fin n))} (h𝒜r : (𝒜 : Set (Finset (Fin n))).Sized r)
(h𝒞𝒜 : 𝒞.card ≤ 𝒜.card) (h𝒞 : Finset.Colex.IsInitSeg 𝒞 r) :
(Finset.shadow 𝒞).card ≤ (Finset.shadow 𝒜).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.kruskal_katona`. Proof here reduces to that Mathlib result.