In combinatorial mathematics, an independence system S {\displaystyle S} is a pair ( V , I ) {\displaystyle (V,{\mathcal {I}})} , where V {\displaystyle V} is a finite set and I {\displaystyle {\mathcal {I}}} is a collection of subsets of V {\displaystyle V} (called the independent sets or feasible sets) with the following properties:
The empty set is independent, i.e., ∅ ∈ I {\displaystyle \emptyset \in {\mathcal {I}}} . (Alternatively, at least one subset of V {\displaystyle V} is independent, i.e., I ≠ ∅ {\displaystyle {\mathcal {I}}\neq \emptyset } .) Every subset of an independent set is independent, i.e., for each Y ⊆ X {\displaystyle Y\subseteq X} , we have X ∈ I ⇒ Y ∈ I {\displaystyle X\in {\mathcal {I}}\Rightarrow Y\in {\mathcal {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 A pair ( V , I ) {\displaystyle (V,{\mathcal {I}})} , where V {\displaystyle V} is a finite set and I {\displaystyle {\mathcal {I}}} is a collection of subsets of V {\displaystyle V} , is also called a hypergraph. When using this terminology, the elements in the set V {\displaystyle V} are called vertices and elements in the family I {\displaystyle {\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.
References Bondy, Adrian; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699.