Loading...
Please wait, while we are loading the content...
Similar Documents
On orthogonal symmetric chain decompositions
| Content Provider | arXiv |
|---|---|
| Author | Däubel, Karl Jäger, Sven Mütze, Torsten Scheucher, Manfred |
| Date of Submission | 2019-04-25 |
| Abstract | The $n$-cube is the poset obtained by ordering all subsets of $\{1,\ldots,n\}$ by inclusion, and it can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ 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/2\rfloor+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\geq 24$. In this paper, we construct four pairwise orthogonal chain decompositions of the $n$-cube for $n\geq 60$. We also construct five pairwise edge-disjoint chain decompositions of the $n$-cube for $n\geq 90$, where edge-disjointness is a slightly weaker notion than orthogonality. |
| Related Links | https://arxiv.org/pdf/1810.09847.pdf |
| arXiv | 1810.09847 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Mathematics - Combinatorics Computer Science - Discrete Mathematics Computer Science Mathematics |
| Content Type | Text |
| Resource Type | Article |
| Subject | Mathematics |
