In combinatorial mathematics, an independence system , where is a finite set and is a collection of subsets of (called the independent sets or feasible sets) with the following properties:

1. The empty set. (Alternatively, at least one subset of .)

2. . This is sometimes called the hereditary property, or downward-closedness.

Another term for an independence system is an abstract simplicial complex.

Relation to other concepts

• , 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.

References

• .