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

• D. Knuth: The Art of Computer Programming, pre-fascicle 3a: Generating all combinations, pp. 18–.