2023/03/02 by D. Gribanov, Gribanov, D. · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2303.01224
openalex publication_date 2023/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a class of simplices defined by systems A x ≤ b of linear inequalities with Δ-modular matrices. A matrix is called Δ-modular, if all its rank-order sub-determinants are bounded by Δ in an absolute value. In our work we call a simplex Δ-modular, if it can be defined by a system A x ≤ b with a Δ-modular matrix A. And we call a simplex empty, if it contains no points with integer coordinates. In literature, a simplex is called lattice-simplex, if all its vertices have integer coordinates. And a lattice-simplex called empty, if it contains no points with integer coordinates excluding its vertices. Recently, assuming that Δ is fixed, it was shown that the number of Δ-modular empty simplices modulo the unimodular equivalence relation is bounded by a polynomial on dimension. We show that the analogous fact holds for the class of Δ-modular empty lattice-simplices. As the main result, assuming again that the value of the parameter Δ is fixed, we show that all unimodular equivalence classes of simplices of the both types can be enumerated by a polynomial-time algorithm. As the secondary result, we show the existence of a polynomial-time algorithm for the problem to check the unimodular equivalence relation for a given pair of Δ-modular, not necessarily empty, simplices.