Chemistry - 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 $\partial X$ 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,

$\partial A = \bigcup \{ \partial X \mid X \in A \}$ .

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

$m = {m_t \choose t} + {m_{t-1} \choose t-1} + ... + {m_{u} \choose u}$ ,

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

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

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

Categories: Combinatorics | Set families