Counting 2-level polytopes

Decanato - Facoltà di scienze informatiche

Data: 14 Marzo 2018 / 14:00 - 15:00

USI Lugano Campus, room A34, Red building (Via G. Buffi 13)

Speaker:	Samuel Fiorini
	Université libre de Bruxelles, Belgium
Date:	Wednesday, March 14, 2018
Place:	USI Lugano Campus, room A34, Red building (Via G. Buffi 13)
Time:	14:00-15:00

Abstract:

Two-level polytopes are fascinating polytopes that appear in different contexts (Erhart theory, sum-of-squares hierarchies, and more). They generalize, for instance, stable set polytopes of perfect graphs. Although all the evidence we have indicates that they have a very constrained structure, so far there are very few general results about 2-level polytopes.

In this talk I will report on recent results about 2-level polytopes. We can show that there are very few: at most 2^{O(d^2 log(d))}, up to isomorphism. The same bound also applies to 2-level cones.

This result is joint work with Marco Macchia and Kanstantsin Pashkovich.

Biography:

Samuel Fiorini is Associate Professor at the Université libre de Bruxelles, Department of Mathematics. His research interests include polyhedral combinatorics, extended formulations, combinatorial optimization, approximation algorithms, some problems in structural graph theory.

Host:

Prof. Monaldo Mastrolilli