Kruskal-Katona theorem

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 <math>\partial X<math> as the family of <math>(n-1)<math>-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,

<math>\partial A = \bigcup \{ \partial X \mid X \in A \}<math>.

The Kruskal–Katona theorem states that the size of <math>\partial A<math> is minimized when A consists of the <math>|A|<math> lexicographically first subsets of U. Denoting <math>m=|A|<math>, we can write m in the form

<math>m = {m_t \choose t} + {m_{t-1} \choose t-1} + ... + {m_{u} \choose u}<math>,

where <math>m_t>m_{t-1}>\dots>m_{u}\ge u\ge 1<math>, and thus

<math>|\partial A| \ge {m_t \choose t-1} + {m_{t-1} \choose t-2} + ... + {m_{u} \choose u-1}<math>,

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 <math>\partial_u X<math> as the family of <math>(n+1)<math>-element supersets of X, we have that <math>|\partial_u A|<math> 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–.