On orthogonal symmetric chain decompositions

arXiv1810.09847MaRDI QIDQ6308652FDOQ6308652

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

Publication date 23 October 2018

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics of partially ordered sets (06A07)

Abstract: The $n$-cube is the poset obtained by ordering all subsets of $1,ldots,n$ by inclusion, and it can be partitioned into $$ 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 $lfloorn/2floor+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 $ngeq24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for $ngeq60$. We also construct five pairwise edge-disjoint chain decompositions of the $n$-cube for $ngeq90$, where edge-disjointness is a slightly weaker notion than orthogonality.

This page was built for publication: On orthogonal symmetric chain decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6308652)