8. Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes
Martin Grötschel · Society for Industrial and Applied Mathematics eBooks · 2004
A subset C of the power set of a finite set E is called cardinality homogeneous if, whenever C contains some set F, C contains all subsets of E of cardinality |F|. Examples of such set systems C are the sets of all even or of all odd cardinality subsets of E, or, for each uniform matroid, its set of circuits and its set of cycles. With each cardinality homogeneous set system C, we associate the polytope P(C), the convex hull of the incidence vectors of all sets in C. We provide a complete and nonredundant linear description of P(C). We show that a greedy algorithm optimizes any linear function over P(C); we construct, by a dual greedy procedure, an explicit optimum solution of the dual linear program; and we describe a polynomial time separation algorithm for the class of polytopes of type P(C).