![]() | 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 is a pair , where is a finite set and is a collection of subsets of (called the independent sets or feasible sets) with the following properties:
- The empty set is independent, i.e., . (Alternatively, at least one subset of is independent, i.e., .)
- Every subset of an independent set is independent, i.e., for each , we have . 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 set and is a collection of subsets of , is also called a hypergraph. When using this terminology, the elements in the set are called vertices and elements in the family are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph. , where is a finite
- 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
- 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 Misplaced Pages by expanding it. |