Principally Box-integer Polyhedra and Equimodular Matrices Article Swipe

MAKE IMPACT

Patrick Chervet , Roland Grappe , Louis‐Hadrien Robert · YOU? · · 2018 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1804.08977

A polyhedron is box-integer if its intersection with any integer box $\{\ell\leq x \leq u\}$ is integer. We define principally box-integer polyhedra to be the polyhedra $P$ such that $kP$ is box-integer whenever $kP$ is integer. We characterize them in several ways, involving equimodular matrices and box-total dual integral (box-TDI) systems. A rational $r\times n$ matrix is equimodular if it has full row rank and its nonzero $r\times r$ determinants all have the same absolute value. A face-defining matrix is a full row rank matrix describing the affine hull of a face of the polyhedron. Box-TDI systems are systems which yield strong min-max relations, and the underlying polyhedron is called a box-TDI polyhedron. Our main result is that the following statements are equivalent. - The polyhedron $P$ is principally box-integer. - The polyhedron $P$ is box-TDI. - Every face-defining matrix of $P$ is equimodular. - Every face of $P$ has an equimodular face-defining matrix. - Every face of $P$ has a totally unimodular face-defining matrix. - For every face $F$ of $P$, lin($F$) has a totally unimodular basis. Along our proof, we show that a cone $\{x:Ax\leq \mathbf{0}\}$ is box-TDI if and only if it is box-integer, and that these properties are passed on to its polar. We illustrate the use of these characterizations by reviewing well known results about box-TDI polyhedra. We also provide several applications. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra having the Integer Carathéodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1804.08977

PDF

https://arxiv.org/pdf/1804.08977

OA Status

green

References

31

Related Works

20

OpenAlex ID

https://openalex.org/W2799246934

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2799246934

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1804.08977

Digital Object Identifier

Title

Principally Box-integer Polyhedra and Equimodular Matrices

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2018

Year of publication

Publication date

2018-04-24

Full publication date if available

Authors

Patrick Chervet, Roland Grappe, Louis‐Hadrien Robert

List of authors in order

Landing page

https://arxiv.org/abs/1804.08977

Publisher landing page

PDF URL

https://arxiv.org/pdf/1804.08977

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1804.08977

Direct OA link when available

Concepts

Polyhedron, Unimodular matrix, Integer (computer science), Combinatorics, Mathematics, Matrix (chemical analysis), Integer points in convex polyhedra, Face (sociological concept), Discrete mathematics, Integer programming, Computer science, Algorithm, Composite material, Materials science, Sociology, Social science, Branch and price, Programming language

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

References (count)

31

Number of works referenced by this work

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload