On matrices with the Edmonds-Johnson property

The strong Chvátal rank of a rational matrix A is the smallest number t such that the polyhedron defined by the system b <= A x <= c, l <= x <= u has Chvátal rank at most t for all integral vectors b,c,l,u. Matrices with strong Chvátal rank at most 1 are said to have the Edmonds-Johnson property. There are two main classes of matrices known to have the Edmonds-Johnson property, one was introduced by Edmonds and Johnson, and the other by Gerards and Schrijver. Characterizing integral matrices with the Edmonds-Johnson property seems complicated. However, Gerards and Schrijver noticed that there are some openings if we restrict ourselves to totally half-modular matrices, and they conjectured a characterization of totally half-modular matrices with the Edmonds-Johnson property. In this thesis we introduce two new classes of totally half-modular matrices with the Edmonds-Johnson property, that prove the validity of the conjecture by Gerards and Schrijver in two particular cases. In Chapter 3 we study systems of the from b <= Mx <= d, l <= x <= u, where M is obtained from a totally unimodular matrix with two nonzero elements per row by multiplying by 2 some of its columns, and b,d,l,u are integral vectors. We give an explicit description of a totally dual integral system that describes the integer hull of the polyhedron P defined by the above inequalities. Since the inequalities of such totally dual integral system are Chvátal inequalities for P, our result implies that the matrix M has the Edmonds-Johnson property. In Chapter 4 we consider the class of totally half-modular matrices obtained from matrices 0, ± 1 with at most two nonzero entries per column by multiplying by 2 some of the columns. In this class we characterize, in terms of excluded minors, the matrices that have the Edmonds-Johnson property.

Il rango forte di Chvátal di una matrice razionale A è il più piccolo numero t tale che il poliedro definito dal sistema b <= A x <= c, l <= x <= u ha rango di Chvátal al più t per tutti i vettori interi b,c,l,u. Matrici con rango forte di Chvátal al più 1 si dicono avere la proprietà di Edmonds-Johnson. Ci sono due principali classi note di matrici con la proprietà di Edmonds-Johnson, una fu introdotta da Edmonds e Johnson, e l'altra da Gerards e Schrijver. Caratterizzare le matrici intere con la proprietà di Edmonds-Johnson sembra complicato. Tuttavia, Gerards e Schrijver notarono che ci sono più possibilità se ci restringiamo alle matrici totalmente 1/2-modulari, e congetturarono una caratterizzazione delle matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson. In questa tesi introduciamo due nuovi classi di matrici totalmente 1/2-modulari con la proprietà di Edmonds-Johnson, che provano la validità della congettura di Gerards e Schrijver in due casi particolari. Nel Capitolo 3 studiamo sistemi nella forma b <= Mx <= d, l <= x <= u, dove M è ottenuta da una matrice totalmente unimodulare con due elementi diversi da zero per riga moltiplicando per 2 alcune colonne, e b,d,l,u sono vettori interi. Noi diamo una descrizione esplicita di un sistema totally dual integral che descrive l'inviluppo convesso dei punti interi del poliedro P definito dalle disuguaglianze precedenti. Dato che le disuguaglianze di tale sistema totally dual integral sono disuguaglianze di Chvátal per P, questo implica che la matrice M ha la proprietà di Edmonds-Johnson. Nel Capitolo 4 consideriamo la classe delle matrici totalmente 1/2-modulari ottenute da matrici 0, ± 1 con al più due elementi non zero per colonna moltiplicando per 2 alcune colonne. In questa classe caratterizziamo, in termini di minori esclusi, le matrici che hanno la proprietà di Edmonds-Johnson.