Independence system

In combinatorial mathematics, an independence system S is a pair (E, I), where E is a finite set and I is a collection of subsets of E (called the independent sets) with the following properties:

  1. The empty set is independent, i.e., ∅  I. (Alternatively, at least one subset of E is independent, i.e., I  ∅.)
  2. Every subset of an independent set is independent, i.e., for each Y   X, X  I  Y   I. This is sometimes called the hereditary property.

Adding the augmentation property or the independent set exchange property yields a matroid.

For a more general description, see abstract simplicial complex.

References


This article is issued from Wikipedia - version of the 10/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.