In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice. Matroid theory borrows extensively from the terms used in both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory, and coding theory.
Definition There are many equivalent ways to define a (finite) matroid.
Independent sets In terms of independence, a finite matroid M {\displaystyle M} is a pair ( E , I ) {\displaystyle (E,{\mathcal {I}})} , where E {\displaystyle E} is a finite set (called the ground set) and I {\displaystyle {\mathcal {I}}} is a family of subsets of E {\displaystyle E} (called the independent sets) with the following properties:
(I1) The empty set is independent, i.e., ∅ ∈ I {\displaystyle \emptyset \in {\mathcal {I}}} . (I2) Every subset of an independent set is independent, i.e., for each A ′ ⊆ A {\displaystyle A'\subseteq A} , if A ∈ I {\displaystyle A\in {\mathcal {I}}} then A ′ ∈ I {\displaystyle A'\in {\mathcal {I}}} . This is sometimes called the hereditary property, or the downward-closed property. (I3) If A {\displaystyle A} and B {\displaystyle B} are two independent sets (i.e., each set is independent) and A {\displaystyle A} has more elements than B {\displaystyle B} , then there exists x ∈ A ∖ B {\displaystyle x\in A\setminus B} such that B ∪ { x } {\displaystyle B\cup \{x\}} is independent. This is sometimes called the augmentation property or the independent set exchange property (cf. Steinitz exchange lemma) The first two properties define a combinatorial structure known as an independence system (or abstract simplicial complex). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of E {\displaystyle E} is independent, i.e., I ≠ ∅ {\displaystyle {\mathcal {I}}\neq \emptyset } .
Bases and circuits
A subset of the ground set E {\displaystyle E} that is not independent is called dependent. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of E {\displaystyle E} – is called a basis for the matroid. A circuit in a matroid M {\displaystyle M} is a minimal dependent subset of E {\displaystyle E} – that is, a dependent set whose proper subsets are all independent. The term arises because the circuits of graphic matroids are cycles in the corresponding graphs. The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely: a set is independent if and only if it is not dependent, if and only if it is a subset of a basis, and if and only if it does not contain a circuit. The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid M {\displaystyle M} to be a pair ( E , B ) {\displaystyle (E,{\mathcal {B}})} , where E {\displaystyle E} is a finite set as before and B {\displaystyle {\mathcal {B}}} is a collection of subsets of E {\displaystyle E} , called bases, with the following properties:
… excerpt ends here. Continue reading the full article.
