Kruskal-Katona theorem

(Redirected from Kruskal–Katona theorem)

Let and , (cf. also Sperner property; Sperner theorem). The elements of can be linearly ordered in the following way: if the largest element in which and differ is in (cf. also Totally ordered set). If , , is the th element in this order, then (a1)

since  -element subsets of have maximal element smaller than , have maximal element but the second largest element smaller than , etc.. Equation (a1) is called the -representation of , (for , one takes , , ). This (unique) representation can be found directly by choosing maximal such that , maximal such that , etc..

For a family , the lower shadow of is defined by If is given as above, then the lower shadow of the family of the first elements in is the family of all -element subsets of having maximal element smaller than , of all -element subsets of having maximal element , but the second largest element smaller than , etc., i.e. the family of the first elements of where The Kruskal–Katona theorem states that in this way one obtains a lower shadow of minimum size, i.e., if is any -element family in and is given by (a1), then There exist generalizations to similar results for other partially ordered sets, like products of chains, products of stars, the partially ordered set of subwords of - -words, and the partially ordered set of submatrices of a matrix.

The following result of L. Lovász is weaker but numerically easier to handle: If and with some real , where , then The original papers by J.B. Kruskal and G.O.H. Katona are [a3], [a4].

According to [a2], p. 1296, the Kruskal–Katona theorem is probably the most important one in finite extremal set theory.