Lattice matrices, intersection of ring families and dicuts
Lattice matrices are 0/1-matrices used in the description of certain lattice polyhedra and related to dicuts in a graph. The incidence matrix \(A^ T\) of a so-called intersection of two ring families and the incidence matrix \(A^ D\) of all dicuts of a graph are examples of such matrices. In this paper after showing that any lattice matrix \(A\) can be obtained from some matrix \(A^ I\) by deletion or some \(A^ D\) by contraction, they first describe the convex hull of the rows of \(A^ I\), \(\text{CONV}(A^ I)\), as the solution set of a system \(x\geq 0\), \(B_ x\leq 1\), \(R_ x\leq 0\), which is tdi. Then they derive the main result, the description of \(\text{CONV}(A)\) by another tdi system. As applications, the polyhedral description of all dicuts in a graph, \(\text{CONV}(A^ D)\), and that of all convex sets of bounded length in a poset are established.
scientific article; zbMATH DE number 166353