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.
References
| [a1] | K. Engel, "Sperner theory" , Cambridge Univ. Press (1997) |
| [a2] | P. Frankl, "Extremal set systems" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , 2 , Elsevier (1995) pp. 1293–1329 |
| [a3] | J.B. Kruskal, "The number of simplices in a complex" , Mathematical Optimization Techniques , Univ. California Press (1963) pp. 251–278 |
| [a4] | G.O.H. Katona, "A theorem of finite sets" , Theory of Graphs. Proc. Colloq. Tihany , Akad. Kiadó (1966) pp. 187–207 |
Kruskal-Katona theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kruskal-Katona_theorem&oldid=22675