Independence system

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

  1. The empty set is independent, i.e., ∅ ∈ I. (Alternatively, at least one subset of V is independent, i.e., I ≠ ∅.)
  2. Every subset of an independent set is independent, i.e., for each Y  ⊆ X, we have X ∈ I → Y  ∈ 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

1. A pair (V, I), where V is a finite set and I 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 I are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph.

2. An independence system with an additional property called the augmentation property or the exchange property yields a matroid. The following expression summarizes the relations between the terms:

HYPERGRAPHS ⊃ INDEPENDENCE-SYSTEMS = ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS.

gollark: Well, it's power-costing energy/power.
gollark: Wait, you're *not* oxidizing your fuel? It's free energy/power.
gollark: This was useful once when a draconic reactor explosion accidentally destroyed the entire spawn area on one server I was on, but the storage stuff had a dedicated spatial IO unit and could be sent to a backup site in the End.
gollark: GTech™ standard policy is to have the main ME controller/storage/crafting CPU stuff in one area and then run a bunch of wires out for machinery.
gollark: You get more side-product outputs for slightly more power/processing time.

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


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.