Geodesic
On integer points in two polyhedra
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 3, pp. 24-30.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SVMO_2017_19_3_a1,
     author = {S. I. Veselov},
     title = {On integer points in two polyhedra},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {24--30},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2017_19_3_a1/}
}
TY  - JOUR
AU  - S. I. Veselov
TI  - On integer points in two polyhedra
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2017
SP  - 24
EP  - 30
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2017_19_3_a1/
LA  - ru
ID  - SVMO_2017_19_3_a1
ER  - 
%0 Journal Article
%A S. I. Veselov
%T On integer points in two polyhedra
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2017
%P 24-30
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2017_19_3_a1/
%G ru
%F SVMO_2017_19_3_a1
S. I. Veselov. On integer points in two polyhedra. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 3, pp. 24-30. http://geodesic.mathdoc.fr/item/SVMO_2017_19_3_a1/

[1] A. Schrijver, Theory of Linear andInteger Programming, v. 2, Mir Publ., Moscow, 1991, 342 pp. (In Russ.) | MR

[2] V.A Emelichev, M.M. Kovalev, M.K. Kravtsov, Polyhedra, Graphs, and Optimization, Nauka Publ., Moscow, 1981, 344 pp. (In Russ.) | MR

[3] J. Moussafir, “Sails and Hilbert Bases”, Funktsional. Anal. i Prilozhen., 34:2 (2000), 43–49 (In Russ.) | DOI | MR

[4] O. N. German, “Sails and Hilbert Bases”, Tr. Mat. Inst. Steklova, 239 (2002), 98–105 (In Russ.) | Zbl

[5] C. Bouvier and G. Gonzalez-Sprinberg, “Systeme generateurs minimal, diviseurs essentiels et G-desingularizations de varietes toriques”, Tohoku Math. J., 47:1 (1995), 125–149 | DOI | MR | Zbl

[6] J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices”, J. Res. Nat. Bur. Standards Sect., 69:1 (1965), 125–130 | DOI | MR | Zbl

[7] V. Chvatal, “Edmonds polytopes and a hierarchy of combinatorial problems”, Discrete Mathematics, 4:4 (1973), 305–337 | DOI | MR | Zbl

[8] W. Cook W., C.R. Coullard, G. Turan, “On the complexity of cutting-plane proofs”, Discrete Applied Mathematics, 18:1 (1987), 25–38 | DOI | MR | Zbl

[9] M. Rhodes, “On the Chvatal rank of the Pigeonhole Principle”, Theoretical Computer Science, 410:27-29 (2009), 2774–2778 | DOI | MR | Zbl

[10] F. Eisenbrand, A.S. Schulz, “Bounds on the chvatal rank of polytopes in the 0/1-cube”, Combinatorica, 23:2 (2003), 245–261 | DOI | MR | Zbl

[11] S. I. Veselov, A, J. Chirkov, “Integer program with bimodular matrix”, Discrete Optimization, 6:2 (2009), 220–222 | DOI | MR | Zbl