Independence system


In combinatorial mathematics, an independence system S is a pair, where V is a finite set and I is a collection of subsets of V with the following properties:
  1. The empty set is independent, i.e., ∅ ∈ I.
  2. Every subset of an independent set is independent, i.e., for each Y ⊆ X, we have X ∈ I → Y ∈ I. 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

1. A pair, where V is a finite set and I is a collection of subsets of V, is also called a hypergraph. When using this terminology, the elements in the set V are called vertices and elements in the family I are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph.
2. An independence system with an additional property called the augmentation property or the exchange property yields a matroid. The following expression summarizes the relations between the terms:
HYPERGRAPHS ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.