A Kruskal-Katona type theorem for the linear lattice


Bezrukov, S. & Blokhuis, A. (1999). A Kruskal-Katona type theorem for the linear lattice. European Journal of Combinatorics, 20(2), 123-130. In Scopus Cited 4 times.

Read more: DOI      Medialink/Full text



We present an analog of the well-known Kruskal–Katona theorem for the poset of subspaces of PG(n,2) ordered by inclusion. For givenk,l (k <l) andmthe problem is to find a family of sizemin the set of l-subspaces of PG(n,2), containing the minimal number ofk-subspaces. We introduce two lexicographic type orders 1and 2on the set of l-subspaces, and prove that the firstmof them, taken in the order 1, provide a solution in the casek = 0 and arbitrary l > 0, and one taken in the order 2, provide a solution in the case l = n - 1 and arbitraryk <n - 1. Concerning other values ofkand l, we show that forn = 3 the considered poset is not Macaulay by constructing a counterexample in the case l = 2 andk = 1.

f1 Author to whom all correspondence should be addressed.