Events
June
2018
July
2018

Counting 2-level polytopes

Staff - Faculty of Informatics

Date: / -

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