A polyhedron P whose extreme points are the incidence vectors of the sets of an independence system I is called an independence system polyhedron. In this paper, we consider the problem of describing the facial structure of independence system polyhedra.#R##N##R##N#Using the fact that this structure is known when the independence system is a matroid, we study the polyhedron P by decomposing the independence system I as a union of matroidal families. We provide a system of valid inequalities for P that contains all its facets. A consequence of this result is the following: the maximum number of distinct coefficients of a facet is bounded by the minimum number of matroidal families whose union gives I. When the independence system I is the union of two matroids, we give necessary and sufficient conditions for an inequality of the above system to define a facet of P.
['Michele Conforti', 'Monique Laurent']
On the Facial Structure of Independence System Polyhedra