On orthogonal symmetric chain decompositions

Main Article Content

Karl Däubel Sven Jäger Torsten Mütze Manfred Scheucher

Abstract

The \textit{$n$-cube} is the poset obtained by ordering all subsets of $\{1,\ldots,n\}$ by inclusion, and it can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ chains, which is the minimum possible number.Two such decompositions of the $n$-cube are called \textit{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\geq 24$.In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for~$n\geq 60$.We also construct five pairwise \textit{edge-disjoint} symmetric chain decompositions of the $n$-cube for~$n\geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality, improving on a recent result by Gregor, J\"ager, M\"utze, Sawada, and Wille.

Article Details

How to Cite
Däubel, K., Jäger, S., Mütze, T., & Scheucher, M. (2019). On orthogonal symmetric chain decompositions. Acta Mathematica Universitatis Comenianae, 88(3), 611-618. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1203/701
Section
EUROCOMB 2019