Name
Abstract | ||
|---|---|---|
The $n$-cube is the poset obtained by ordering all subsets of ${1,ldots,n}$ by inclusion. It is well-known that the $n$-cube can be partitioned into $binom{n}{lfloor n/2rfloor}$ 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 $lfloor n/2rfloor+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 $ngeq 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for $ngeq 60$. We also construct five pairwise edge-disjoint chain decompositions of the $n$-cube for $ngeq 90$, where edge-disjointness is a slightly weaker notion than orthogonality. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.37236/8531 | arXiv: Combinatorics |
Field | DocType | Volume |
Discrete mathematics,Pairwise comparison,Combinatorics,Orthogonality,Mathematics,Partially ordered set | Journal | abs/1810.09847 |
Issue | Citations | PageRank |
3 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Karl Däubel | 1 | 0 | 0.34 |
| Sven Jäger | 2 | 0 | 0.34 |
| Torsten Mütze | 3 | 43 | 12.88 |
| Manfred Scheucher | 4 | 0 | 0.34 |