Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Torsten Mütze (TU Berlin)

On symmetric chains and Hamilton cycles

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:   2024  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