Matroids and graphs

Abstract

This project lies in the area of discrete mathematics and combinatorics, and is associated to a two months long visit to the Department of Computer Science of the Institute of Mathematics and Statistics of the University of São Paulo. We are interested in studying problems relating notions of graphs and matroids. Matroid theory is a subject gathering several areas. It helps to explain and to discover the common properties of such areas. Studying problems in this more general setting often provides new insight to different problems and their connections. The theory of matroid can be approached from many different points of view. A matroid can be defined as a simplicial complex of independent sets, a lattice of flats, a closure relation, and in many other different ways. A relatively new point of view is the study of matroid polytopes, which in some sense, are the natural combinatorial setting of matroids in algebraic geometry and optimisation. A better conceptual and mathematical understanding of matroid polytopes is required since this would have significant algorithmic and theoretical consequences. The goal of this project is to develop the study of matroid polytopes and its interactions with other subjects. The project is divided into two connected parts. Firstly, we shall study combinatorial properties of the base matroid graphs, that is, the graphs associated to the 1-skeleton of matroid polytopes. Secondly, we will investigate the major cut set expansion matroid problem. (AU)