[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 21st 2019

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on January 21st at 14:15 h & 16:00 h at TU Berlin.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin 

Time: Monday, January 21st - 14:15 h

Lecture: Maria Bras Amorós (Universitat Rovira i Virgili Tarragona)

Title: On numerical semigroups

Abstract:

A numerical semigroup is a subset of the positive integers (N) together with 0, closed under addition, and with a finite complement in N∪{0}.

The number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus g, denoted (n_g)_g≥0, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each g, n_g+2 ≥ n_g+1 + n_g or, even more simple, n_g+1 ≥ n_g.

We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]

Time: Monday, January 21st - 16:00 h s.t.

Colloquium: Torsten Mütze (Technische Universität Berlin)

Title: On symmetric chains and Hamilton cycles

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⊆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 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.