In combinatorial mathematics, an independence system ${\displaystyle S}$ is a pair ${\displaystyle (V,{\mathcal {I}})}$, where ${\displaystyle V}$ is a finite set and ${\displaystyle {\mathcal {I}}}$ is a collection of subsets of ${\displaystyle V}$ (called the independent sets or feasible sets) with the following properties:

1. The empty set is independent, i.e., ${\displaystyle \emptyset \in {\mathcal {I}}}$. (Alternatively, at least one subset of ${\displaystyle V}$ is independent, i.e., ${\displaystyle {\mathcal {I}}\neq \emptyset }$.)
2. Every subset of an independent set is independent, i.e., for each ${\displaystyle Y\subseteq X}$, we have ${\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 ${\displaystyle (V,{\mathcal {I}})}$, where ${\displaystyle V}$ is a finite set and ${\displaystyle {\mathcal {I}}}$ is a collection of subsets of ${\displaystyle V}$, is also called a hypergraph. When using this terminology, the elements in the set ${\displaystyle V}$ are called vertices and elements in the family ${\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.