On orthogonal symmetric chain decompositions

Abstract

The $n$-cube is the poset obtained by ordering all subsets of $\{1,\dots ,n\}$ by inclusion, and it can be partitioned into $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ chains, which is the minimum possible number. Two such decompositions of the $n$-cube are called orthogonal if any two chains of the decompositions share at most a single element. Shearer and Kleitman conjectured in 1979 that the $n$-cube has $\lfloor n/2\rfloor +1$ pairwise orthogonal decompositions into the minimum number of chains, and they constructed two such decompositions. Spink recently improved this by showing that the $n$-cube has three pairwise orthogonal chain decompositions for $n\ge 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for $n\ge 60$. We also construct five pairwise edge-disjoint chain decompositions of the $n$-cube for $n\ge 90$, where edge-disjointness is a slightly weaker notion than orthogonality.

Data and verification files are available on arXiv as ancillary files