On orthogonal symmetric chain decompositions
share
The n-cube is the poset obtained by ordering all subsets of {1,...,n} by inclusion. It is well-known that the n-cube 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 chain decompositions of the n-cube for n≥ 90, where edge-disjointness is a slightly weaker notion than orthogonality.
READ FULL TEXT