2022/03/08 by D. V. Gribanov, Gribanov, D. V., D. S. Malyshev +3
Computer Science · Mathematics · Engineering · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2203.03907
Let A ∈ Zm × n, rank(A) = n, b ∈ Zm, and P be an n-dimensional polyhedron, induced by the system A x ≤ b. It is a known fact that if F is a k-face of P, then there exist at least n-k linearly independent inequalities of the system A x ≤ b that become equalities on F. In other words, there exists a set of indices J, such that |J| ≥ n-k, rank(AJ) = n-k, and AJ x - bJ = 0, for any x ∈ F. We show that a similar fact holds for the integer polyhedron PI = conv.hull(P ∩ Zn), if we additionally suppose that P is Δ-modular, for some Δ∈ \1,2,…\. More precisely, if F is a k-face of PI, then there exists a set of indices J, such that |J| ≥ n-k, rank(AJ) = n-k, and AJ x - bJ \oversetΔ= 0, for any x ∈ F ∩ Zn, where x \oversetΔ= y means that ‖x - y‖∞ < Δ. In other words, there exist at least n-k linearly independent inequalities of the system A x ≤ b that almost become equalities on F ∩ Zn. When we say almost, we mean that the slacks are not greater than Δ-1. Using this fact, we prove the inequality |vert(PI)| ≤ 2 ⋅ \binommn ⋅ Δn-1, for the number of vertices of PI, which is better, than the state of the art bound for Δ= O(n2).