On 2-Level Polytopes Arising In Combinatorial Settings

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arising in combinatorial settings. Our first contribution is proving that f(0)(P)f(d-1) (P)

On vertices and facets of combinatorial 2-level polytopes

Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano, Yuri Faenza

2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number of vertices, where d is the dimension of a 2-level polytope P. This question was first posed in [3], where experimental results showed an upper bound of d2^{d+1} up to d = 6, where d is the dimension of the polytope. We show that this bound holds for all known (to the best of our knowledge) 2-level polytopes coming from combinatorial settings, including stable set polytopes of perfect graphs and all 2-level base polytopes of matroids. For the latter family, we also give a simple description of the facet-defining inequalities. These results are achieved by an investigation of related combinatorial objects, that could be of independent interest.

Springer2016

On some problems related to 2-level polytopes

Manuel Francesco Aprile

In this thesis we investigate a number of problems related to 2-level polytopes, in particular regarding their combinatorial structure and extension complexity. 2-level polytopes have been introduced as a generalization of stable set polytopes of perfect graphs, and despite their apparently simple structure, are at the center of many open problems: these include connection with communication complexity and the separation between linear and semidefinite programming. The extension complexity of a polytope P is a measure of the complexity of representing P: it is the smallest size of an extended formulation of P, which in turn is a linear description of a polyhedron that projects down to P. In the first chapter we introduce themain concepts that will be used through the thesis and we motivate our interest in 2-level polytopes. In the second chapter we examine several classes of 2-level polytopes arising in combinatorial settings and we prove a relation between the number of vertices and facets of such polytopes, which is conjectured to hold for all 2-level polytopes. The proofs are obtained through an improved understanding of the combinatorial structure of such polytopes, which in some cases leads to results of independent interest. In the third chapter we study the extension complexity of a restricted class of 2-level polytopes, the stable set polytopes of bipartite graphs, for which we obtain improved lower and upper bounds. In the fourth chapter we study slack matrices of 2-level polytopes, important combinatorial objects related to extension complexity, defining operations on them and giving algorithms for the following recognition problem: given a matrix, determine whether it is a slack matrix of some special class of 2-level polytopes. In the fifth chapter we address the problem of explicitly obtaining small size extended formulations whose existence is guaranteed by communication protocols. In particular we give an output-efficient algorithmto write down extended formulations for the stable set polytope of perfect graphs, making a well known result by Yannakakis constructive, and we extend this to all deterministic protocols. We then conclude the thesis outlining themain open questions that stem from our work.

EPFL

On some problems related to 2-level polytopes

Manuel Francesco Aprile

EPFL