Chain Covers in the Boolean Lattice

Abstract

For integers $1\le r\le n+1$, let $N(n,r)$ denote the least number of chains in the Boolean lattice $B_n=2^{[n]}$ that cover every strict $r$-term chain. The case $r=1$ is the classical chain-decomposition problem and is generalizing Dilworth's theorem and Sperner's theorem. We study two complementary regimes. First, when $r>1$ is fixed and $n\to \infty$. Let $$M(n,r):=\underset{\begin{array}{c}{a}_0+\cdots +a_r=n{a}_0,a_r\ge 0,a_i\ge 1(1\le i\le r-1)\end{array}}{\max }\left(\genfrac{}{}{0ex}{}{n}{a_0,\dots ,a_r}\right).$$ We prove that lower and upper bounds which differ only by a logarithmic factor: \[ M(n,r)\le N(n,r)\le \left(\frac r2+o(1)\right)\log n\cdot M(n,r). \] Second, we consider the near-maximal regime $N(n,n-t)$, where $t>0$ is fixed. We prove that \[ N(n,n-t)= (γ_{t-1}+o(1))n!, \] where ${\hat{I}}_d^3$ is the limit of the density of a minimum size subset of the hypercube $Q_n$ that meets all $d$-dimensional subcube.