On the Facial Structure of Independence System Polyhedra

A polyhedron P whose extreme points are the incidence vectors of the sets of an independence system ℐ is called an independence system polyhedron. In this paper, we consider the problem of describing the facial structure of independence system polyhedra.

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 ℐ 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 ℐ. When the independence system ℐ 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.