direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

List of all publications

On orthogonal symmetric chain decompositions
Citation key DaeubelJaegerMuetzeScheucher2019b
Author Däubel, Karl and Jäger, Sven and Mütze, Torsten and Scheucher, Manfred
Pages P3.64
Year 2019
ISSN 1077-8926
Journal Electronic Journal of Combinatorics
Volume 26
Number 3
Month 09
Note Full version
Abstract The n-cube is the poset obtained by ordering all subsets of 1,…,n by inclusion, and it can be partitioned into n choose ⌊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.
Link to original publication Download Bibtex entry

Zusatzinformationen / Extras