A Kruskal-Katona type theorem for the linear lattice (Q1283308)

If \(L\) is the collection of all proper non-empty subspaces of \(\text{PG}(n,2)\) ordered by inclusion, where \(L_l\) is the set of all \(l\)-dimensional subspaces, and where for \(B\leq L_l\), \(l>0\), and \(k< l\), then \(\Delta^l_k(B)= \{a\in L_k\mid a\leq b\) for some \(b\in B\}\). The problem discussed is to minimize \(|\Delta^l_k(B)|\) among all \(m\)-subsets of \(L_l\), i.e., to find a \(\Delta^l_k\)-optimal \(m\)-subset of \(L_l\), and in particular to find a \(\Delta^l_k\)-optimal family \(\{A_m\}\) such that \(| A_m|= m\), \(A_{m-1}\leq A_m\), \(m= 1,2,\dots,| L|\), as an analog to the Kruskal-Katona Theorem for the problem with \(L\) replaced by the Boolean algebras \(B^n\). The key Theorem 2 provides formulas: (i) \(|\Delta^l_0(O^1_l(m))|\leq |\Delta^l_0(B)|\) for any \(B\leq L_l\), \(| B|= m\) and \(0<l\leq n-1\); (ii) \(|\Delta^{n-1}_k(O^2_{n- 1}(m))|\leq |\Delta^{n-1}_k(B)|\) for any \(B\leq L_{n-1}\), \(| B|= m\) and \(0\leq k<n-1\); where \(O^1\) and \(O^2\) are special partial orders of a lexicographic type, \(O^i_l\) is the restriction of \(O^i\) to \(L_l\), and \(O^i_l(m)\) is the initial segment of \(L_l\), in the order \(O^i\) of length \(m\). The proof of this interesting theorem is after several quite efficient rewritings into equivalent versions based on some geometric insight turned into combinatorial results leading to the conclusions given above. It is also noted that other cases than those handled by the main result to the extent that special situations have not been considered in an ad-hoc fashion are lacking a universal method to provide an equally universal solution.