Independence system
Encyclopedia
In combinatorial
mathematics, an independence system S is a pair (E, I), where E is a finite set and I is a collection of subset
s of E (called the independent sets) with the following properties:
Adding the augmentation property or the independent set exchange property yields a matroid
.
For a more general description, see abstract simplicial complex
.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics, an independence system S is a pair (E, I), where E is a finite set and I is a collection of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of E (called the independent sets) with the following properties:
- The empty setEmpty setIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
is independent, i.e., ∅ ∈ I. (Alternatively, at least one subset of E is independent, i.e., I ≠ ∅.) - Every subset of an independent set is independent, i.e., for each E' ⊆ E, E ∈ I → E' ∈ I. This is sometimes called the hereditary property.
Adding the augmentation property or the independent set exchange property yields a matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
.
For a more general description, see abstract simplicial complex
Abstract simplicial complex
In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets...
.