A Kruskal-Katona type theorem for the linear lattice

S. Bezrukov, A. Blokhuis

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)123-130
Number of pages8
JournalEuropean Journal of Combinatorics
Issue number2
Publication statusPublished - 1999


Dive into the research topics of 'A Kruskal-Katona type theorem for the linear lattice'. Together they form a unique fingerprint.

Cite this