Lattice matrices, intersection of ring families and dicuts
type: Item
instance of: scholarly article
title: Lattice matrices, intersection of ring families and dicuts
zbMATH Open document ID: 0773.05028
DOI: 10.1016/0012-365X(92)90700-P
author: Heinz Groeflin
author: Maurice Cochand
author: Arlette Gaillard
published in: Discrete Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 166353
zbMATH Keywords: lattice polyhedra
zbMATH Keywords: dicuts
zbMATH Keywords: incidence matrix
zbMATH Keywords: convex hull
reviewed by: Ratnakaram Nava Mohan
MaRDI profile type: Publication
cites work: Minimum cuts, modular functions, and matroid polyhedra
cites work: Q4149476
cites work: Path-closed sets
cites work: On switching paths polyhedra
cites work: Lattice Polyhedra II: Generalization, Constructions and Examples
cites work: Q4194968
cites work: Q3885764
cites work: Maximal Closure of a Graph and Applications to Combinatorial Problems
cites work: Q3818127
cites work: Q3330974
description: scientific article; zbMATH DE number 166353