Full and maximal squashed flat antichains of minimum weight

Jerrold R. Griggs, Sven Hartmann, Thomas Kalinowski, Uwe Leck, Ian T. Roberts

A full squashed flat antichain (FSFA) in the Boolean lattice $B_n$ is a family $\mathcal{A}\cup\mathcal{B}$ of subsets of $[n]=\{1,2,\dots,n\}$ such that, for some $k\in [n]$ and $0\le m\le \binom n k$, $\mathcal{A}$ is the family of the first $m$ $k$-sets in squashed (reverse-lexicographic) order and $\mathcal{B}$ contains exactly those $(k-1)$-subsets of $[n]$ that are not contained in some $A\in\mathcal{A}$. If, in addition, every $k$-subset of $[n]$ which is not in $\mathcal{A}$ contains some $B\in\mathcal{B}$, then $\mathcal{A}\cup\mathcal{B}$ is a maximal squashed flat antichain (MSFA). For any $n,k$ and positive real numbers $\alpha,\beta$, we determine all FSFA and all MSFA of minimum weight $\alpha\cdot|\mathcal{A}|+\beta\cdot|\mathcal{B}|$. Based on this, asymptotic results on MSFA with minimum size and minimum BLYM value, respectively, are derived.

Knowledge Graph



Sign up or login to leave a comment