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) <= d(2)(d+1) for a large collection of families of such polytopes P. Here f(0)(P) (resp., f(d-1) (P)) is the number of vertices (resp., facets) of P, and d is its dimension. Whether this holds for all 2-level polytopes was asked in [A. Bohn, Y. Faenza, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich, in Algorithms-ESA 2015, Springer, Berlin, 2015, pp. 191-202], and experimental results from [S. Fiorini, V. Fisikopoulos, and M. Macchia, in Combinatorial Optimization, Springer, Cham, 2016, pp. 285-296] showed it true for d <= 7. The key to most of our proofs is a deeper understanding of the relations among those polytopes and their underlying combinatorial structure. This leads to a number of results that we believe to be of independent interest: a trade-off formula for the number of cliques and stable sets in a graph, a description of stable matching polytopes as affine projections of certain order polytopes, and a linear-size description of the base polytope of matroids that are 2-level in terms of cuts of an associated tree.


Publié dans:
Siam Journal On Discrete Mathematics, 32, 3, 1857-1886
Année
Jan 01 2018
Publisher:
Philadelphia, SIAM PUBLICATIONS
ISSN:
0895-4801
1095-7146
Mots-clefs:
Laboratoires:




 Notice créée le 2018-12-13, modifiée le 2019-06-19


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)