On the cycle polytope of a binary matroid
Linear optimization problems defined over the polytope \(P(M,b)=conv\{x\in \{0,1\}^ n:\) Mx\(\equiv b\) (mod 2)\(\}\) are often used in modelling real world problems. The following results regarding P(M,b) are shown: (1) In order to characterize the facet defining inequalities of P(M,b) it is enough to characterize the facets that contain a given vertex. As a corollary it can be shown that P(M,b) is defined by the so-called cocircuit-inequalities. (2) Adjacency on P(M,b) is characterized. (3) The Hirsch conjecture is proved if the binary matroid associated with M contains on \(F^*_ 7\) minor.
scientific article; zbMATH DE number 3959447