MSC2010 90C10
On integer points in two polyhedra
S. I. Veselov1
| Annotation | In the article we study the convex hulls of integer points in polyhedra of two types. The first type is convex cone consisting of solutions of homogeneous systems of linear inequalities with unimodular matrices of coefficients. The second type includes polyhedra defined by systems of inequalities with bimodular matrices of coefficients at unknowns. For the polyhedra of the first type it is established that the Hilbert basis consists of the spanning vectors of the cone and has a unimodular triangulation. It is also proved that the integer distance from the convex hull facet of the nonzero integer points of the cone to the cone vertex is 1. This means that for polyhedra obtained from the cone by removing its vertex the Chvatal rank is equal to 1. In the class of polyhedra of the second type such restriction on the coefficient matrix was foundthat its implementation makes Chvatal rank equal to one. |
|---|---|
| Keywords | Hilbert basis, unimodular triangulation, the convex hull of integer points, facets of integer polyhedron, Chvatal rank. |
1Sergey I. Veselov, Associate Professor, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod (23 Gagarina avenue, Nizhny Novgorod, 603950, Russia), ORCID: http://orcid.org/ 0000-0003-2737-5876, sergey.veselov@itmm.unn.ru
Citation: S. I. Veselov, "[On integer points in two polyhedra]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,19:3 (2017) 24–30 (In Russian)
DOI 10.15507/2079-6900.19.201703.24-30
