Lehman's forbidden minor characterization of ideal 0-1 matrices
type: Item
instance of: scholarly article
title: Lehman's forbidden minor characterization of ideal 0-1 matrices
zbMATH Open document ID: 0798.05010
DOI: 10.1016/0012-365X(93)90178-V
published in: Discrete Mathematics
publication date: 1993-12-20T00:00:00Z
review text: An \(m\times n\) (0,1)-matrix is called ideal if the polyhedron \(P(A):= \{x\in \mathbb{R}^ n: Ax\geq e,\;x\geq 0\) (componentwise)\} is nonempty and all of its extreme points are integer-valued, where \(e= (1,\dots,1)^ T\). In 1979 A. Lehman gave characterizations of minimally nonideal (0,1)- matrices which remained unpublished. In the paper under review, the author presents both a documentation of Lehman's investigations and a different proof of the complete characterization of all minimally (almost) nonideal matrices.
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15B33
zbMATH DE Number: 428336
zbMATH Keywords: zero-one matrices
zbMATH Keywords: ideal matrices
author: Manfred Padberg
MaRDI profile type: Publication
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: On the width—length inequality
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q4093221
cites work: Perfect zero–one matrices
cites work: Q4077730
cites work: Almost integral polyhedra related to certain combinatorial optimization problems
cites work: An extension of a theorem of the Bruijn and Erdős on combinatorial designs
cites work: Q4190651
description: scientific article; zbMATH DE number 428336