Ideal 0, 1 matrices
type: Item
instance of: scholarly article
title: Ideal 0, 1 matrices
zbMATH Open document ID: 0794.05077
author: Beth Novick
author: Gérard Cornuéjols
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-06-06T00:00:00Z
review text: We define a \(0, 1\) matrix \(M\) to be ideal if all vertices of the polyhedron \(\{x: Mx\geq 1,\;x\geq 0\}\) have only \(0, 1\) components. We expand the list of known minor minimal nonideal matrices by several hundred. Many of these examples are obtained polyhedrally, by constructing new minimally nonideal matrices from old ones. We present a conjecture that might be viewed as the counterpart for ideal matrices of Berge's Strong Perfect Graph Conjecture. We provide evidence for the conjecture by completely characterizing all minimally nonideal circulants.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 562399
zbMATH Keywords: clutter
zbMATH Keywords: max flow min cut property
zbMATH Keywords: width-length inequality
zbMATH Keywords: ideal matrix
zbMATH Keywords: Berge's strong perfect graph conjecture
zbMATH Keywords: \(0, 1\) matrix
zbMATH Keywords: ideal
zbMATH Keywords: polyhedron
zbMATH Keywords: minor minimal nonideal matrices
zbMATH Keywords: minimally nonideal circulants
MaRDI profile type: Publication
full work available at URL: jctb.1994.1009
OpenAlex ID: W2045938882
DOI: 10.1006/JCTB.1994.1009
description: scientific article; zbMATH DE number 562399