Orthogonal Symmetric Chain Decompositions of Hypercubes

Citations Over Time

Abstract

In 1979, Shearer and Kleitman conjectured that there exist $\lfloor n/2 \rfloor+1$ orthogonal chain decompositions of the hypercube $Q_n$, and constructed two orthogonal chain decompositions. In this paper, we make the first non-trivial progress on this conjecture since by constructing three orthogonal chain decompositions of $Q_n$ for $n$ large enough. To do this, we introduce the notion of "almost orthogonal symmetric chain decompositions". We explicitly describe three such decompositions of $Q_5$ and $Q_7$, and describe conditions which allow us to decompose products of hypercubes into $k$ almost orthogonal symmetric chain decompositions given such decompositions of the original hypercubes.

Related Papers

• → The Condition Number of Join Decompositions(2018)48 cited
• → The geometry of rank decompositions of matrix multiplication II: $3\times 3$ matrices(2018)3 cited
• → Decompositions of the free product of graphs(2006)2 cited
• → Linear N-decompositions and tri-diagonal matrices(1977)1 cited
• → Large families of homogeneous polynomials with non-unique additive decompositions(2019)