BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 ⊆ A k +1 ⊆…⊆ 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 know
n 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 construction
s\, however\, yield the very same SCD. In this talk I will present severa
l new constructions of SCDs in the n -cube. Specifically\, we construct fi
ve pairwise edge-disjoint SCDs in the n -cube for all n ≥90\, and four pa
irwise orthogonal SCDs for all n ≥60\, where orthogonality is a slightly s
tronger requirement than edge-disjointness. Specifically\, two SCDs are cal
led orthogonal if any two chains intersect in at most a single element\, ex
cept the two longest chains\, which may only intersect in the unique minima
l and maximal element (the empty set and the full set). This improves the p
revious best lower bound of three orthogonal SCDs due to Spink\, and is ano
ther step towards an old problem of Shearer and Kleitman from the 1970s\, w
ho 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 leve
ls problem\, a far-ranging generalization of the well-known middle two leve
ls conjecture (now theorem)\, on Hamilton cycles in subgraphs of the (2 n +
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 o
f the (2 n +1)-cube\, and a cycle factor through any even number of levels
around the middle of the (2 n +1)-cube. This talk is based on two papers\
, jointly with Sven Jäger\, Petr Gregor\, Joe Sawada\, and Kaja Wille (ICAL
P 2018)\, and with Karl Däubel\, Sven Jäger\, and Manfred Scheucher\, respe
ctively.
DTSTAMP:20190115T033900
DTSTART:20190121T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Torsten Mütze (Technische Universität Berlin): On symmetric chains
and Hamilton cycles
UID:95604715@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190121-C-Muetze.html
END:VEVENT
END:VCALENDAR