Semigroups – a computational approach. (English) Zbl 1437.11166

Hibi, Takayuki (ed.), The 50th anniversary of Gröbner bases. Proceedings of the 8th Mathematical Society of Japan-Seasonal Institute (MSJ-SI 2015), Osaka, Japan, July 1–10, 2015. Tokyo: Mathematical Society of Japan (MSJ). Adv. Stud. Pure Math. 77, 155-170 (2018).
Summary: The question whether there exists an integral solution to the system of linear equations with non-negative constraints, \(A\mathbf x = \mathbf b, \, \mathbf x \ge 0\), where \(A \in \mathbb Z^{m\times n}\) and \(\mathbf b \in \mathbb Z^m\), finds its applications in many areas, such as operation research, number theory and statistics. In order to solve this problem, we have to understand the semigroup generated by the columns of the matrix A and the structure of the “holes” which are the difference between the semigroup generated by the columns of the matrix A and its saturation. In this paper, we discuss the implementation of an algorithm by Hemmecke, Takemura, and Yoshida that computes the set of holes of a semigroup and we discuss applications to problems in combinatorics. Moreover, we compute the set of holes for the common diagonal effect model, and we show that the \(n\)th linear ordering polytope has the integer-decomposition property for \(n\geq 7\). The software is available at http://ehrhart.math.fu-berlin.de/People/fkohl/HASE/.
For the entire collection see [Zbl 1404.13003].


11Y50 Computer solution of Diophantine equations
11D04 Linear Diophantine equations
11P21 Lattice points in specified regions
52B11 \(n\)-dimensional polytopes
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Full Text: arXiv