Independence system

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Independence system" – news · newspapers · books · scholar · JSTOR (May 2024)

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.