Counting 2-level polytopes

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.