Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, December 20, 2018, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Torsten Mütze (TU Berlin)

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login