NDLI: On 2-Level Polytopes Arising in Combinatorial Settings

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Aprile, Manuel Faenza, Yuri Cevallos, Alfonso
Copyright Year	2018
Abstract	$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)\leq d2^{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\leq 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.
Sponsorship	Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
Starting Page	1857
Ending Page	1886
Page Count	30
File Format	PDF
ISSN	08954801
DOI	10.1137/17M1116684
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2018-08-01
Access Restriction	Subscribed
Subject Keyword	matroids Special polytopes Matroids 2-level polytopes polyhedral combinatorics Polyhedral combinatorics, branch-and-bound, branch-and-cut
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The facets of the spanning trees polytope

On cardinality constrained cycle and path polytopes

Extended Formulations in Combinatorial Optimization

Implementation of a Unimodularity Test

Bounds on the number of 2-level polytopes, cones and configurations

On the graph-density of random 0/1-polytopes

Low-dimensional faces of random 0/1-polytopes

Basic Polyhedral Theory

On the 3-Terminal Cut Polyhedron

On 2-Level Polytopes Arising in Combinatorial Settings

Similar Documents

The facets of the spanning trees polytope

On cardinality constrained cycle and path polytopes

Extended Formulations in Combinatorial Optimization

Implementation of a Unimodularity Test

Bounds on the number of 2-level polytopes, cones and configurations

On the graph-density of random 0/1-polytopes

Low-dimensional faces of random 0/1-polytopes

Basic Polyhedral Theory

On the 3-Terminal Cut Polyhedron

On 2-Level Polytopes Arising in Combinatorial Settings