Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-11745
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
Is Part Of: 10.14279/depositonce-10226
Language Code: en
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.
URI: https://depositonce.tu-berlin.de/handle/11303/12950
http://dx.doi.org/10.14279/depositonce-11745
Issue Date: 27-Sep-2019
Date Available: 7-Apr-2021
DDC Class: 510 Mathematik
Subject(s): chain decompositions
n -cube
orthogonal
License: https://creativecommons.org/licenses/by-nd/4.0/
Journal Title: The electronic journal of combinatorics
Publisher: EMIS ELibEMS
Publisher Place: Madralin
Volume: 26
Issue: 3
Article Number: P3.64
Publisher DOI: 10.37236/8531
EISSN: 1077-8926
ISSN: 1097-1440
Appears in Collections:FG Kombinatorische Optimierung und Graphenalgorithmen » Publications

Files in This Item:
Däubel_etal_orthogonal_2018.pdf
Format: Adobe PDF | Size: 598.67 kB
DownloadShow Preview
Thumbnail

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons