Independence system
In combinatorial mathematics, an independence system is a pair, where is a finite set and is a collection of subsets of with the following properties:
- The empty set 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.
Relation to other concepts
- A pair, where is a finite set and is a collection of subsets of is also called a hypergraph. When using this terminology, the elements in the set are called vertices and elements in the family 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.