The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs that can be used to derive facts about abstract simplicial complexes. For an n-element set X, define the shadow 
as the family of (n - 1)-element subsets of X, and for a family A of n-element subsets of a universe U (i.e., an n-hypergraph), define the shadow as the union of the shadows of the constituent sets,
-
.
The Kruskal–Katona theorem states that the size of 
is minimized when A consists of the | A | lexicographically first subsets of U. Denoting m = | A | , we can write m in the form
-
,
where 
, and thus
-
,
with equality if (but not, in general, only if) A consists of the m lexicographically first subsets of U. Symmetrically, if we define the upward shadow 
as the family of (n + 1)-element supersets of X, we have that 
is maximal when A consists of the m lexicographically last subsets of U.
The theorem was discovered in
- J.B. Kruskal: The number of simplices in a complex, Mathematical Optimization Techniques, R. Bellman (ed.), University of California Press, 1963.
- G.O.H. Katona: A theorem of finite sets, Theory of Graphs, P. Erdős and G. Katona (eds.), Akadémiai Kiadó and Academic Press, 1968.
For a proof via a more general theorem in discrete geometry, see