On matrices with 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.