A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system ℐ, there exist several bouquets of matroids having the same family ℐ of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when ℐ is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of ℐ into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice. © 1989 North-Holland.
On the geometric structure of independence systems
CONFORTI, MICHELANGELO;
1989
Abstract
A bouquet of matroids is a combinatorial structure that generalizes the properties of matroids. Given an independence system ℐ, there exist several bouquets of matroids having the same family ℐ of independent sets. We show that the collection of these geometries forms in general a meet semi-lattice and, in some cases, a lattice (for instance, when ℐ is the family of the stable sets in a graph). Moreover, one of the bouquets that correspond to the highest elements in the meet semi-lattice provides the smallest decomposition of ℐ into matroidal families, such that the rank functions of the different matroids have the same values for common sets. In the last section, we give sharp bounds on the performance of the greedy algorithm, using parameters of some special bouquets in the semi-lattice. © 1989 North-Holland.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
