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:

  1. 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 }.)
  2. 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.