Please use this identifier to cite or link to this item:
For citation please use:
Main Title: On orthogonal symmetric chain decompositions
Author(s): Däubel, Karl
Jäger, Sven
Mütze, Torsten
Scheucher, Manfred
Type: Article
Abstract: 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.
Subject(s): chain decompositions
n -cube
Issue Date: 27-Sep-2019
Date Available: 7-Apr-2021
Is Part Of: 10.14279/depositonce-10226
Language Code: en
DDC Class: 510 Mathematik
Journal Title: The electronic journal of combinatorics
Publisher: EMIS ELibEMS
Volume: 26
Issue: 3
Article Number: P3.64
Publisher DOI: 10.37236/8531
EISSN: 1077-8926
ISSN: 1097-1440
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik » FG Kombinatorische Optimierung und Graphenalgorithmen
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 598.67 kB
DownloadShow Preview

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons