[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 10th 2020

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

You are cordially invited to our last Monday Lecture & Colloquium for this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin.

Exceptionally, there will be once again a second Colloquium at 17:00.

The Faculty will meet after the second Colloquium.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, February 10th - 14:15 h

Lecture: Lionel Pournin (Université Paris 13)

Title: Recent results on the diameter of lattice polytopes

Abstract:

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.

Coffee & Tea Break:
Room 134

Time: Monday, February 10th - 16:00 h s.t.

Colloquium: José Samper (Max Planck Institute Leipzig)

Title: Dual matroid polytopes and the independence complex of a matroid

Abstract:

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.

Time: Monday, February 10th - 17:00 h s.t.

Colloquium: Zslot Ádám Wagner (ETH Zürich)

Title: Recent developments in the container method

Abstract:

The container algorithm is a recently-developed technique for establishing subtle clustering phenomena of independent sets in graphs and hypergraphs. This method has found numerous applications in extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. In this talk, I will give a brief overview of this method and survey some recent developments.