Independence system

In combinatorial mathematics, an independence system S is a pair , where V is a finite set and \mathcal{I} is a collection of subsets of V (called the independent sets or feasible sets) with the following properties: The empty set is independent, i.e., . (Alternatively, at least one subset of V is independent, i.e., .) Every subset of an independent set is independent, i.e., for each , we have . This is sometimes called the hereditary property, or downward-closedness. Another term for an independence system is an abstract simplicial complex. A pair , where V is a finite set and \mathcal{I} is a collection of subsets of is also called a hypergraph. When using this terminology, the elements in the set V are called vertices and elements in the family \mathcal{I} are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph. An independence system with an additional property called the augmentation property or the independent set exchange property yields a matroid. The following expression summarizes the relations between the terms:HYPERGRAPHS ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.