- Kruskal–Katona theorem
The Kruskal–Katona theorem is a combinatorial theorem about uniform hypergraphs. It can be used to derive facts about
abstract simplicial complex es. It is named forJoseph Kruskal andGyula 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 = igcup { 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 m_1 + 1, m_2 + 1, ... m_n+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 uge 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".
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, [http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz pre-fascicle 3a: Generating all combinations] , pp. 18–. "Contains a proof via a more general theorem indiscrete geometry ."
Wikimedia Foundation. 2010.