2017/06/26 by Spink, Hunter
#06A07 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1706.08545
In 1979, Shearer and Kleitman conjectured that there exist \lfloor n/2 \rfloor+1 orthogonal chain decompositions of the hypercube Qn, 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 Qn for n large enough. To do this, we introduce the notion of "almost orthogonal symmetric chain decompositions". We explicitly describe three such decompositions of Q5 and Q7, 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.