Department of
Applied
Mathematics

On symmetric chains and Hamilton cycles

Torsten Mütze

TU Berlin

Abstract

The n-cube is the poset obtained by ordering all subsets of {1,2,...,n} by inclusion. A symmetric chain is a sequence of subsets A_k\subseteq A_{k+1}\subseteq ... \subseteq A_{n-k} with |A_i|=i for all i=k,...,n-k, and a symmetric chain decomposition, or SCD for short, of the n-cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the n-cube for any n>=1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD. In this talk I will present several new constructions of SCDs in the n-cube. Specifically, we construct five pairwise edge-disjoint SCDs in the n-cube for all n>=90, and four pairwise orthogonal SCDs for all n>=60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set). This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the n-cube has \lfloor n/2\rfloor+1 pairwise orthogonal SCDs. We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2n+1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2n+1)-cube, and a cycle factor through any even number of levels around the middle of the (2n+1)-cube.

This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.