Counting 2-level polytopes

Staff - Faculty of Informatics

Date: 14 March 2018 / 14:00 - 15:00

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


Samuel Fiorini


Université libre de Bruxelles, Belgium


Wednesday, March 14, 2018


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






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.




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.




Prof. Monaldo Mastrolilli