Independence system

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

The empty set is independent, i.e., $∅︀ \in ℐ$ . (Alternatively, at least one subset of ⁠ $V$ ⁠ is independent, i.e., $ℐ \neq ∅︀$ .)
Every subset of an independent set is independent, i.e., for each $Y \subseteq X$ , we have $X \in ℐ \Rightarrow Y \in ℐ$ . 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, ℐ)$ , where ⁠ $V$ ⁠ is a finite set and ⁠ $ℐ$ ⁠ is a collection of subsets of ⁠ $V$ ⁠, is also called a hypergraph. When using this terminology, the elements in the set ⁠ $V$ ⁠ are called vertices and elements in the family ⁠ $ℐ$ ⁠ 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 $\supset$ INDEPENDENCE-SYSTEMS $=$ ABSTRACT-SIMPLICIAL-COMPLEXES $\supset$ MATROIDS.

References

Bondy, Adrian; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699.

This combinatorics-related article is a stub. You can help Wikipedia by adding missing information.