Independence system

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

1. The empty set is independent, i.e., [math]\displaystyle{ \emptyset\in\mathcal{I} }[/math]. (Alternatively, at least one subset of [math]\displaystyle{ V }[/math] is independent, i.e., [math]\displaystyle{ \mathcal{I}\neq\emptyset }[/math].)
2. Every subset of an independent set is independent, i.e., for each [math]\displaystyle{ Y\subseteq X }[/math], we have [math]\displaystyle{ X\in\mathcal{I}\Rightarrow Y\in\mathcal{I} }[/math]. 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 [math]\displaystyle{ (V, \mathcal{I}) }[/math], where [math]\displaystyle{ V }[/math] is a finite set and [math]\displaystyle{ \mathcal{I} }[/math] is a collection of subsets of [math]\displaystyle{ V }[/math], is also called a hypergraph. When using this terminology, the elements in the set [math]\displaystyle{ V }[/math] are called vertices and elements in the family [math]\displaystyle{ \mathcal{I} }[/math] 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, 244, Springer, p. 195, ISBN 9781846289699, https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA195 .