In
combinatorialmathematics, an independence system is a pair , where is a finite
set and is a collection of
subsets of (called the independent sets or feasible sets) with the following properties:
The
empty set is independent, i.e., . (Alternatively, at least one subset of 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.
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: