Matroid

In combinatorics, a branch of mathematics, a matroid /ˈmeɪtrɔɪd/ is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid, the most significant being in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions. In combinatorics, a branch of mathematics, a matroid /ˈmeɪtrɔɪd/ is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid, the most significant being in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions. Matroid theory borrows extensively from the terminology of 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. There are many equivalent (cryptomorphic) ways to define a (finite) matroid. 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: The first two properties define a combinatorial structure known as an independence system (or abstract simplicial complex). 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 which becomes dependent on 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 terminology 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: It follows from the basis exchange property that no member of B {displaystyle {mathcal {B}}} can be a proper subset of another. It is a basic result of matroid theory, directly analogous to a similar theorem of bases in linear algebra, that any two bases of a matroid M {displaystyle M} have the same number of elements. This number is called the rank of  M {displaystyle M} . If M {displaystyle M} is a matroid on E {displaystyle E} , and A {displaystyle A} is a subset of E {displaystyle E} , then a matroid on A {displaystyle A} can be defined by considering a subset of A {displaystyle A} to be independent if and only if it is independent in M {displaystyle M} . This allows us to talk about submatroids and about the rank of any subset of E {displaystyle E} . The rank of a subset A {displaystyle A} is given by the rank function r ( A ) {displaystyle r(A)} of the matroid, which has the following properties: