Independence system

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

1. The empty set is independent, i.e., $\mathrm{\varnothing }\in ℐ$. (Alternatively, at least one subset of Template:Tmath is independent, i.e., $ℐ\ne \mathrm{\varnothing }$.)
2. 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 Template:Tmath is a finite set and Template:Tmath is a collection of subsets of Template:Nobr is also called a hypergraph. When using this terminology, the elements in the set Template:Tmath are called vertices and elements in the family Template:Tmath 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 Template:Math INDEPENDENCE-SYSTEMS Template:Math ABSTRACT-SIMPLICIAL-COMPLEXES Template:Math MATROIDS.

References

• Template:Citation.

Template:Combin-stub