TY - GEN A1 - Grötschel, Martin T1 - Cardinality Homogeneous Set Systems, Cycles in Matroids, and Associated Polytopes N2 - A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$. T3 - ZIB-Report - 02-19 KW - Cycles in Matroids KW - cardinality homogeneous set systems KW - polytopes KW - greedy algorithm KW - polyhedral combinatorics Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6868 ER -