Thumbnail Image

On orthogonal symmetric chain decompositions

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

The n-cube is the poset obtained by ordering all subsets of {1,…,n} by inclusion, and it can be partitioned into (n⌊n/2⌋) 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 ⌊n/2⌋+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≥24. In this paper, we construct four pairwise orthogonal chain decompositions of the n-cube for n≥60. We also construct five pairwise edge-disjoint symmetric chain decompositions of the n-cube for n≥90, where edge-disjointness is a slightly weaker notion than orthogonality, improving on a recent result by Gregor, Jäger, Mütze, Sawada, and Wille.
Published in: The electronic journal of combinatorics, 10.37236/8531, EMIS ELibEMS