Misplaced Pages

Independence system

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 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.

References


Stub icon

This combinatorics-related article is a stub. You can help Misplaced Pages by expanding it.

Categories:
Independence system Add topic