Kruskal–Katona theorem

From Wikipedia, the free encyclopedia

The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. It can be used to derive facts about abstract simplicial complexes. It is named for Joseph Kruskal and Gyula O. H. Katona.

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 | co-lexicographically first subsets of size n of U. Denoting m = | A | , and the m+1'th element of the colexicographical order as {m1 + 1,m2 + 1,...mn + 1}, we have

m = {m_n \choose n} + {m_{n-1} \choose n-1} + ... + {m_{u} \choose u},

where m_n>m_{n-1}>\dots>m_{u}\ge u\ge 1, u being the first integer for which m_u \ge u, and thus

|\partial A| \ge {m_n \choose n-1} + {m_{n-1} \choose n-2} + ... + {m_{u} \choose u-1},

with equality if (but not, in general, only if) A consists of the m co-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 minimal when A consists of the m co-lexicographically last subsets of U.

[edit] References

  • 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.
  • D. Knuth: The Art of Computer Programming, pre-fascicle 3a: Generating all combinations, pp. 18–. Contains a proof via a more general theorem in discrete geometry.