Independence system

{{one source |date=May 2024}} In combinatorial mathematics, an '''independence system''' {{tmath|S }} is a pair <math>(V, \mathcal{I})</math>, where {{tmath|V }} is a finite set and {{tmath|\mathcal{I} }} is a collection of subsets of {{tmath|V}} (called the '''independent sets''' or '''feasible sets''') with the following properties: # The empty set is independent, i.e., <math>\emptyset\in\mathcal{I}</math>. (Alternatively, at least one subset of {{tmath|V }} is independent, i.e., <math>\mathcal{I}\neq\emptyset</math>.) # Every subset of an independent set is independent, i.e., for each <math>Y\subseteq X</math>, we have <math>X\in\mathcal{I}\Rightarrow Y\in\mathcal{I}</math>. 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 <math>(V, \mathcal{I})</math>, where {{tmath|V }} is a finite set and {{tmath|\mathcal{I} }} is a collection of subsets of {{nobr|{{tmath|V }},}} is also called a '''hypergraph'''. When using this terminology, the elements in the set {{tmath|V }} are called '''vertices''' and elements in the family {{tmath|\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:<p>HYPERGRAPHS {{math|⊃ }} INDEPENDENCE-SYSTEMS {{math|{{=}} }} ABSTRACT-SIMPLICIAL-COMPLEXES {{math|⊃ }} MATROIDS.</p>

==References== *{{citation | last1 = Bondy | first1 = Adrian | last2 = Murty | first2 = U.S.R. |authorlink1 = John Adrian Bondy |authorlink2 = U. S. R. Murty | isbn = 9781846289699 | page = 195 | publisher = Springer | series = Graduate Texts in Mathematics | title = Graph Theory | url = https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA195 | volume = 244 | year = 2008}}.

Category:Combinatorics Category:Hypergraphs

{{combin-stub}}