Springe direkt zu Inhalt

Colloquium by Torsten Mütze (Technische Universität Berlin): On symmetric chains and Hamilton cycles

Jan 21, 2019 | 04:00 PM s.t.

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 AkAk+1⊆…⊆An-k with |Ai|=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 ⌊n/2⌋+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.

Time & Location

Jan 21, 2019 | 04:00 PM s.t.

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room MA 041 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)