Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903858 | Journal of Combinatorial Theory, Series B | 2018 | 43 Pages |
Abstract
In this paper we study totally half-modular matrices obtained from {0,±1}-matrices with at most two nonzero entries per column by multiplying by 2 some of the columns. We give an excluded-minor characterization of the matrices in this class having strong Chvà tal rank 1. Our result is a special case of a conjecture by Gerards and Schrijver [11]. It also extends a well known theorem of Edmonds and Johnson [10].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Alberto Del Pia, Antoine Musitelli, Giacomo Zambelli,