Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. On 2-Level Polytopes Arising In Combinatorial Settings
 
research article

On 2-Level Polytopes Arising In Combinatorial Settings

Aprile, Manuel  
•
Cevallos, Alfonso  
•
Faenza, Yuri  
January 1, 2018
Siam Journal On Discrete Mathematics

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.

  • Details
  • Metrics
Type
research article
DOI
10.1137/17M1116684
Web of Science ID

WOS:000450810500015

Author(s)
Aprile, Manuel  
Cevallos, Alfonso  
Faenza, Yuri  
Date Issued

2018-01-01

Publisher

SIAM PUBLICATIONS

Published in
Siam Journal On Discrete Mathematics
Volume

32

Issue

3

Start page

1857

End page

1886

Subjects

Mathematics, Applied

•

Mathematics

•

2-level polytopes

•

matroids

•

polyhedral combinatorics

•

positive semidefinite rank

•

independence polytopes

•

regular matroids

•

poset polytopes

•

graphs

•

algorithms

•

complexity

•

marriage

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
MATHAA  
Available on Infoscience
December 13, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/151997
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés