العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolMATROID
In combinatorics, a branch of mathematics, a 'matroid' is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces. (The pronunciation of the first syllable is as in ''mate'', ''may'', or ''matrix''.)
There are many equivalent ways to define a matroid, and many concepts within matroid theory have a variety of equivalent formulations. Depending on the sophistication of the concept, it may be nontrivial to show that the different formulations are equivalent, a phenomenon sometimes called cryptomorphism. Significant definitions of matroid include those 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.
There are dozens of equivalent ways to define a (finite) matroid. Here are some of the most important. There is no one preferred or customary definition; in that respect, matroids differ from many other mathematical structures, such as groups and topologies.
One of the most valuable definitions is that in terms of independence. In this definition a finite matroid ''M'' is a pair (''E'', 'I'), where ''E'' is a finite set and 'I' is a collection of subsets of ''E'' (called the 'independent sets') with the following properties:
# The empty set is independent. (Alternatively, at least one subset of ''E'' is independent.)
# Every subset of an independent set is independent. This is sometimes called the 'hereditary property'.
# If ''A'' and ''B'' are two independent sets and ''A'' has more elements than ''B'', then there exists an element in ''A'' which is not in ''B'' and when added to ''B'' still gives an independent set. This is sometimes called the 'augmentation property' or the 'independent set exchange property'.
The first two properties are simple, and define a combinatorial structure known as an independence system, but the motivation behind the third property is not obvious. The examples in the example section below will make its motivation clearer.
A subset of ''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''—is called a 'basis' for the matroid. It is a basic result of matroid theory, directly analogous to a similar theorem of linear algebra, that any two bases of a matroid ''M'' have the same number of elements. This number is called the 'rank' of ''M''.
A 'circuit' in a matroid ''M'' is a minimal dependent subset of ''E''—that is, a dependent set whose proper subsets are all independent. In spite of the similarity to the definition of ''basis'' this notion has no analogue in classical linear algebra. The terminology comes from graph theory; see below.
The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely. Furthermore, the collection of dependent sets, or of bases, or of circuits each has simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid ''M'' to be a pair (''E'', 'B'), where ''E'' is a finite set as before and 'B' is a collection of subsets of ''E'', called bases, with the following property:
★ If ''A'' and ''B'' are distinct bases of ''M'' and ''a'' is an element of ''A'' not belonging to ''B'', then there exists an element ''b'' belonging to ''B'' such that ''B'' - ''b'' + ''a'' is a basis. This property is sometimes called the 'basis exchange property'.
If ''M'' is a matroid on ''E'', and ''A'' is a subset of ''E'', then a matroid on ''A'' can be defined by considering a subset of ''A'' independent if and only if it is independent in ''M''. This allows us to talk about 'submatroids' and about the rank of any subset of ''E''.
The 'rank function' ''r'' assigns a natural number to every subset of ''E'' and has the following properties:
# ''r''(''A'') ≤ |''A''| for all subsets ''A'' of ''E''.
# If ''A'' and ''B'' are subsets of ''E'' with ''A'' ⊆ ''B'', then ''r''(''A'') ≤ ''r''(''B'').
# For any two subsets ''A'' and ''B'' of ''E'', we have ''r''(''A'' ∪ ''B'') + ''r''(''A'' ∩ ''B'') ≤ ''r''(''A'') + ''r''(''B'').
These three properties can be used as one of the alternative definitions of a finite matroid: the independent sets are then defined as those subsets ''A'' of ''E'' with ''r''(''A'') = |''A''|.
Let ''M'' be a matroid on a finite set ''E'', defined as above. The 'closure' cl(''A'') of a subset ''A'' of ''E'' is the subset of ''E'' containing ''A'' and every element ''x'' in ''EA'', such that there is a circuit ''C'' containing ''x'' and contained in the union of ''A'' and {''x''}. This defines the closure operator, from 'P'(''E'') to 'P'(''E''), where 'P' denotes the power set.
The closure operator cl from 'P'(''E'') to 'P'(''E'') has the following property:
★ For all elements ''a'', ''b'' of ''E'' and all subsets ''Y'', ''Z'' of ''E'', if ''a'' is in cl(''Y'' ∪ ''b'') cl(''Y''), then ''b'' is in cl(''Y'' ∪ ''a''). This is sometimes called the 'MacLane–Steinitz exchange property'.
In fact this may be taken as another definition of matroid – any closure operator on ''E'' with this property determines a matroid on ''E''.
Let ''E'' be a finite set and ''k'' a natural number. One may define a matroid on ''E'' by taking every ''k''-element subset of ''E'' to be a basis. This is known as the 'uniform matroid of rank' ''k''.
The uniform matroid of rank 2 on ''n'' points is called the ''n''-'point line'.
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. Matroids from vector spaces are still the main examples. There are two ways to present them.
★ If ''E'' is any finite subset of a vector space ''V'', then we can define a matroid ''M'' on ''E'' by taking the independent sets of ''M'' to be the linearly independent elements in ''E''. We say the set ''E'' 'represents' ''M''. Matroids of this kind are called 'vector matroids'.
★ A matrix ''A'' with entries in a field gives rise to a matroid ''M'' on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors. This matroid is called the 'column matroid' of ''A'', and ''A'' is said to 'represent' ''M''. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation. (There is one technical difference: a column matroid can have distinct elements that are the same vector, but a vector matroid as defined above cannot. Usually this difference is insignificant and can be ignored, but by letting ''E'' be a multiset of vectors one brings the two definitions into complete agreement.)
A matroid that is equivalent to a vector matroid, although it may be presented differently, is called 'representable'. If ''M'' is equivalent to a vector matroid over a field ''F'', then we say ''M'' is 'representable over' ''F''. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field. A basic problem in matroid theory is to determine whether a given matroid ''M'' is representable over a given field ''F''. Whitney found one solution to this problem when ''F'' is a field with two elements (see "Binary matroids", below), but the general situation is famously complicated.
A second original source for the theory of matroids is graph theory.
Every finite graph (or multigraph) ''G'' gives rise to a matroid as follows: take as ''E'' the set of all edges in ''G'' and consider a set of edges independent if and only if it does not contain a simple cycle. Such an edge set is called a 'forest' in graph theory. This is called the 'cycle matroid' or 'graphic matroid' of ''G''; it is usually written ''M''(''G'').
Any matroid that is equivalent to the cycle matroid of a (multi)graph, even if it is not presented in terms of graphs, is called a 'graphic matroid'. The matroids that are graphic have been characterized by Tutte.
Graphic matroids have been generalized to matroids from signed graphs and biased graphs.
A third original source of matroid theory is field theory.
An extension of a field gives rise to a matroid. Suppose ''F'' and ''K'' are fields with ''K'' containing ''F''. Let ''E'' be any finite subset of ''K''. Define a subset ''S'' of ''E'' to be independent if the extension field ''F''[''S''] has transcendence degree equal to |''S''|.
A matroid that is equivalent to a matroid of this kind is called an 'algebraic matroid'. The problem of characterizing algebraic matroids is extremely difficult; little is known about it.
Matroids with a small number of elements are often pictured as in the diagram. The dots are the elements of the underlying set, and a curve has been drawn through every circuit. The diagram shows a rank 3 matroid called the 'Fano matroid', an example that appeared in the original 1935 paper of Whitney.
The name arises from the fact that the Fano matroid is the projective plane of order 2, known as the Fano plane, whose coordinate field is the 2-element field. This means the Fano matroid is the vector matroid associated to the seven nonzero vectors in a three-dimensional vector space over a field with two elements.
It is known from projective geometry that the Fano matroid is not representable by any set of vectors in a real or complex vector space (or in any vector space over a field whose characteristic differs from 2).
On the other hand, consider this 'non-example': let ''E'' be a set of pairs (''v'',''c'') where ''v'' ranges over the vertices of a graph and ''c'' ranges over the the set {red, blue, yellow}. Let the independent sets be the sets of pairs that associate only one color with each vertex and do not associate the same color with two adjacent vertices; that is, they represent valid graph colorings. The empty set is a valid three-coloring, and any subset of a valid three-coloring is a valid three-coloring, but the exchange property does not hold, because it's possible to have two maximal three-colored subgraphs of different sizes, as shown to the right. It's no surprise that this is not a matroid, since if it were, it would give us a greedy algorithm for the NP-complete 3-coloring problem, showing P = NP.
Let ''M'' be a matroid with an underlying set of elements ''E'', and let ''N'' be another matroid on underlying set ''F''.
There are some standard ways to make new matroids out of old ones.
★ 'Restriction'. If ''S'' is a subset of ''E'', the 'restriction' of ''M'' to ''S'', written ''M''|''S'', is the matroid on underlying set ''S'' whose independent sets are the independent sets of ''M'' that are contained in ''S''. Its circuits are the circuits of ''M'' that are contained in ''S'' and its rank function is that of ''M'' restricted to subsets of ''S''.
★ 'Contraction'. If ''T'' is a subset of ''E'', the 'contraction' of ''M'' by ''T'', written ''M''/''T'', is the matroid on the underlying set ''E − T'' whose rank function is
★ 'Minors'. A matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations is called a 'minor' of ''M''. We say ''M'' 'contains' ''N'' 'as a minor'.
★ 'Direct sum'. The 'direct sum' of ''M'' and ''N'' is the matroid whose underlying set is the disjoint union of ''E'' and ''F'', and whose independent sets are the disjoint unions of an independent set of ''M'' with an independent set of ''N''.
★ 'Matroid union'. The 'union' of ''M'' and ''N'' is the matroid whose underlying set is the union (not the disjoint union) of ''E'' and ''F'', and whose independent sets are those subsets whose intersections with both ''E'' and ''F'' are independent. Usually the term "union" is applied when ''E'' = ''F'', but that assumption is not essential. If ''E'' and ''F'' are disjoint, the union is the direct sum.
Let ''M'' be a matroid with an underlying set of elements ''E''.
★ A subset of ''E'' 'spans' ''M'' if its closure is ''E''. A set is said to 'span' a closed set ''K'' if its closure is ''K''.
★ A maximal closed proper subset of ''E'' is called a 'coatom' or 'copoint' or 'hyperplane' of ''M''. An equivalent definition: A coatom is a subset of ''E'' that does not span ''M'', but such that adding any other element to it does make a spanning set.
★ An element that forms a single-element circuit of ''M'' is called a 'loop'.
★ An element that belongs to no circuit is called a ''coloop''.
★ If a two-element set {''f, g''} is a circuit of ''M'', then ''f'' and ''g'' are 'parallel' in ''M''.
★ ''M'' is called 'simple' if no 1- or 2-element subset of ''E'' is a circuit.
★ A simple matroid obtained from ''M'' by deleting all loops and deleting one element from each 2-element circuit until no 2-element circuits remain is called a 'simplification' of ''M''.
★ A matroid which cannot be written as the direct sum of two nonempty matroids is called 'connected' or 'irreducible'.
★ A maximal irreducible submatroid of ''M'' is called a 'component' of ''M''.
A matroid is 'regular' if it can be represented by a totally unimodular matrix (a matrix whose square submatrices all have determinants equal to 0, 1, or −1). Tutte proved that the following three properties of a matroid are logically equivalent:
# ''M'' is regular.
# ''M'' is representable over every field.
# ''M'' has no minor that is a four-point line or a Fano plane or its dual.
For this he used his difficult homotopy theorem. Simpler proofs have since been found.
The most amazing result about regular matroids is Seymour's decomposition theorem, that all regular matroids can be built up in a simple way from graphic matroids and their duals and one special matroid. This theorem has major consequences for linear programming involving totally unimodular matrices.
A matroid that is representable over the two-element field is called a 'binary matroid'. Binary matroids include graphic and regular matroids. They have many of the nice properties of those types of matroid. Whitney and Tutte found famous characterizations. Addition of sets is symmetric difference. The following properties of a matroid ''M'' are equivalent:
# ''M'' is binary.
# In ''M'', every sum of circuits is a union of disjoint circuits (Whitney).
# ''M'' has no minor that is a four-point line (Tutte).
Suppose 'L' is a list of matroids. The class Ex('L') of all matroids that do not contain as a minor any member of the list is said to be 'characterized by forbidden minors' (or 'excluded minors'). Some of the great theorems of matroid theory characterize natural classes of matroids by forbidden minors. Three examples due to Tutte:
★ Binary matroids (see above).
★ Regular matroids (see above).
★ Graphic matroids are the matroids that have no minor that is the four-point line (which is self-dual), the Fano plane or its dual, the dual of the cycle matroid ''M''(''K''5), or the dual of the cycle matroid ''M''(''K''3,3).
It is easy to show that the matroids representable over a fixed field can be characterized by a list of forbidden minors. A famous outstanding problem ('Rota's conjecture') is to prove that this list is finite for finite fields. This has been solved only for the fields of up to four elements (and the exact lists are known for those fields, but one cannot expect exact lists for larger fields). The problem is significant because there are matroid properties that can be characterized by forbidden minors but not by a finite list of them—for example, the property of being representable over the real numbers.
The Robertson-Seymour Theorem, whose full proof runs to more than 500 pages, states that every matroid property of ''graphic'' matroids characterized by a list of forbidden minors can be characterized by a finite list—in other words, if an infinite list 'L' includes the forbidden minors for graphic matroids, then Ex('L') = Ex('L’') for some finite list 'L’'.
If ''M'' is a finite matroid, we can define the 'dual matroid' ''M''
★ by taking the same underlying set and calling a set a ''basis'' in ''M''
★ if and only if its complement is a basis in ''M''. It is not difficult to verify that ''M''
★ is a matroid and that the dual of ''M''
★ is ''M''.
The dual can be described equally well in terms of other ways to define a matroid. For instance:
★ A set is independent in ''M''
★ if and only if its complement spans ''M''.
★ A set is a circuit of ''M''
★ if and only if its complement is a coatom in ''M''.
★ The rank function of the dual is r
★ (S) = |E|- r(M) - |S| + r(S).
A main result is the matroid version of Kuratowski's theorem: The dual of a graphic matroid ''M'' is a graphic matroid if and only if ''M'' is the matroid of a planar graph.
A simpler result is that the dual of a vector matroid representable over a particular field ''F'' is also representable over ''F''.
A 'weight function' on a finite set ''E'' is a function ''w'': ''E'' → 'R'+ from ''E'' to the nonnegative real numbers. Abusing notation, such a weight function ''w'' can be extended to subsets ''S'' ⊆ ''E'' by defining
:''w''(''S'') = ∑''s'' ∈ ''S''''w''(''s'').
Suppose ''E'' is a finite set, ''F'' a nonempty family of subsets of ''E'' such that any subset of any element of ''F'' also belongs to ''F'', and ''w'': ''F'' → 'R'+ a weight function on ''F''. A greedy algorithm for (''E'', ''F'', ''w'') is any algorithm that attempts to construct a maximum weight element of ''F'' as follows:
:1. Let ''F''0 = ∅.
:2. For ''i'' ≥ 0:
:: 3. Let ''Z''''i'' = { ''z''''i'' ∈ ''E''-''F''''i'' | ''F''''i'' ∪ {''z''''i''} ∈ ''F'' }.
::4. If ''Z''''i'' = ∅, terminate and return ''F''''i''.
::5. Otherwise, choose an element ''y'' ∈ ''Z''''i'' such that ''w''(''y'') = max{''w''(''z''''i''), ''z''''i'' ∈ ''Z''''i''}, let ''F''''i''+1 = ''F''''i'' ∪ {''y''} and continue.
The following two theorems establish a correspondence between matroids and sets (''E'', ''F'') as defined above for which greedy algorithms do give maximum weight solutions.
:'Theorem 1': If ''E'' in (''E'', ''F'', ''w'') is the underlying set of a matroid ''M'' and ''F'' is the set of independent sets in ''M'', then any greedy algorithm for (''E'', ''F'', ''w'') constructs a maximum weight element of ''F''.
:'Theorem 2': If every greedy algorithm for the pair (''E'', ''F'') constructs a maximum weight element of ''F'' for every choice of weight function ''w'': ''F'' → 'R'+ then ''F'' is the set of independent sets of a matroid ''M'' with underlying set ''E''.
The notion of matroid has been generalized to allow for other types of sets on which greedy algorithms give optimal solutions; see greedoid for more information.
The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. One of the difficulties is that there are many reasonable and useful definitions, none of which captures all the important aspects of finite matroid theory. For instance, it seems to be hard to have bases, circuits, and duality together in one notion of infinite matroids.
★ Infinite matroid
★ Oriented matroid
★ Tutte polynomial
★ Weighted matroid
★ Gian-Carlo Rota
★ P.D. Seymour
★ W. T. Tutte
★ Hassler Whitney
★ Crapo, H., and Rota, G-C. (1970), ''On the Foundations of Combinatorial Theory: Combinatorial Geometries.'' M.I.T. Press, Cambridge, Mass.
★ Oxley, J. (1992), ''Matroid Theory''. Oxford University Press, New York. ISBN 0-19-853563-5.
★ White, N., ed. (1986), ''Theory of Matroids''. Encyclopedia of Mathematics and its Applications, Vol. 26. Cambridge University Press, Cambridge.
★ Whitney, H. (1935), "On the abstract properties of linear dependence". ''American Journal of Mathematics'', vol. 57, pp. 509-533.
★
★ Contains several other equivalent definitions of matroids.
★
★ S. C. Locke: Greedy Algorithms.
★ Steven R. Pagano: Matroids and Signed Graphs.
★ Sandra Kingan: Matroid theory. Lots of links.
★ Klaus Truemper Matroid decomposition.
There are many equivalent ways to define a matroid, and many concepts within matroid theory have a variety of equivalent formulations. Depending on the sophistication of the concept, it may be nontrivial to show that the different formulations are equivalent, a phenomenon sometimes called cryptomorphism. Significant definitions of matroid include those 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.
Formal definitions of finite matroids
There are dozens of equivalent ways to define a (finite) matroid. Here are some of the most important. There is no one preferred or customary definition; in that respect, matroids differ from many other mathematical structures, such as groups and topologies.
Independent sets, bases, and circuits
One of the most valuable definitions is that in terms of independence. In this definition a finite matroid ''M'' is a pair (''E'', 'I'), where ''E'' is a finite set and 'I' is a collection of subsets of ''E'' (called the 'independent sets') with the following properties:
# The empty set is independent. (Alternatively, at least one subset of ''E'' is independent.)
# Every subset of an independent set is independent. This is sometimes called the 'hereditary property'.
# If ''A'' and ''B'' are two independent sets and ''A'' has more elements than ''B'', then there exists an element in ''A'' which is not in ''B'' and when added to ''B'' still gives an independent set. This is sometimes called the 'augmentation property' or the 'independent set exchange property'.
The first two properties are simple, and define a combinatorial structure known as an independence system, but the motivation behind the third property is not obvious. The examples in the example section below will make its motivation clearer.
A subset of ''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''—is called a 'basis' for the matroid. It is a basic result of matroid theory, directly analogous to a similar theorem of linear algebra, that any two bases of a matroid ''M'' have the same number of elements. This number is called the 'rank' of ''M''.
A 'circuit' in a matroid ''M'' is a minimal dependent subset of ''E''—that is, a dependent set whose proper subsets are all independent. In spite of the similarity to the definition of ''basis'' this notion has no analogue in classical linear algebra. The terminology comes from graph theory; see below.
The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely. Furthermore, the collection of dependent sets, or of bases, or of circuits each has simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid ''M'' to be a pair (''E'', 'B'), where ''E'' is a finite set as before and 'B' is a collection of subsets of ''E'', called bases, with the following property:
★ If ''A'' and ''B'' are distinct bases of ''M'' and ''a'' is an element of ''A'' not belonging to ''B'', then there exists an element ''b'' belonging to ''B'' such that ''B'' - ''b'' + ''a'' is a basis. This property is sometimes called the 'basis exchange property'.
Rank functions
If ''M'' is a matroid on ''E'', and ''A'' is a subset of ''E'', then a matroid on ''A'' can be defined by considering a subset of ''A'' independent if and only if it is independent in ''M''. This allows us to talk about 'submatroids' and about the rank of any subset of ''E''.
The 'rank function' ''r'' assigns a natural number to every subset of ''E'' and has the following properties:
# ''r''(''A'') ≤ |''A''| for all subsets ''A'' of ''E''.
# If ''A'' and ''B'' are subsets of ''E'' with ''A'' ⊆ ''B'', then ''r''(''A'') ≤ ''r''(''B'').
# For any two subsets ''A'' and ''B'' of ''E'', we have ''r''(''A'' ∪ ''B'') + ''r''(''A'' ∩ ''B'') ≤ ''r''(''A'') + ''r''(''B'').
These three properties can be used as one of the alternative definitions of a finite matroid: the independent sets are then defined as those subsets ''A'' of ''E'' with ''r''(''A'') = |''A''|.
Closure operators
Let ''M'' be a matroid on a finite set ''E'', defined as above. The 'closure' cl(''A'') of a subset ''A'' of ''E'' is the subset of ''E'' containing ''A'' and every element ''x'' in ''EA'', such that there is a circuit ''C'' containing ''x'' and contained in the union of ''A'' and {''x''}. This defines the closure operator, from 'P'(''E'') to 'P'(''E''), where 'P' denotes the power set.
The closure operator cl from 'P'(''E'') to 'P'(''E'') has the following property:
★ For all elements ''a'', ''b'' of ''E'' and all subsets ''Y'', ''Z'' of ''E'', if ''a'' is in cl(''Y'' ∪ ''b'') cl(''Y''), then ''b'' is in cl(''Y'' ∪ ''a''). This is sometimes called the 'MacLane–Steinitz exchange property'.
In fact this may be taken as another definition of matroid – any closure operator on ''E'' with this property determines a matroid on ''E''.
Examples
The uniform matroid
Let ''E'' be a finite set and ''k'' a natural number. One may define a matroid on ''E'' by taking every ''k''-element subset of ''E'' to be a basis. This is known as the 'uniform matroid of rank' ''k''.
The uniform matroid of rank 2 on ''n'' points is called the ''n''-'point line'.
Matroids from linear algebra
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. Matroids from vector spaces are still the main examples. There are two ways to present them.
★ If ''E'' is any finite subset of a vector space ''V'', then we can define a matroid ''M'' on ''E'' by taking the independent sets of ''M'' to be the linearly independent elements in ''E''. We say the set ''E'' 'represents' ''M''. Matroids of this kind are called 'vector matroids'.
★ A matrix ''A'' with entries in a field gives rise to a matroid ''M'' on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors. This matroid is called the 'column matroid' of ''A'', and ''A'' is said to 'represent' ''M''. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation. (There is one technical difference: a column matroid can have distinct elements that are the same vector, but a vector matroid as defined above cannot. Usually this difference is insignificant and can be ignored, but by letting ''E'' be a multiset of vectors one brings the two definitions into complete agreement.)
A matroid that is equivalent to a vector matroid, although it may be presented differently, is called 'representable'. If ''M'' is equivalent to a vector matroid over a field ''F'', then we say ''M'' is 'representable over' ''F''. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field. A basic problem in matroid theory is to determine whether a given matroid ''M'' is representable over a given field ''F''. Whitney found one solution to this problem when ''F'' is a field with two elements (see "Binary matroids", below), but the general situation is famously complicated.
Matroids from graph theory
A second original source for the theory of matroids is graph theory.
Every finite graph (or multigraph) ''G'' gives rise to a matroid as follows: take as ''E'' the set of all edges in ''G'' and consider a set of edges independent if and only if it does not contain a simple cycle. Such an edge set is called a 'forest' in graph theory. This is called the 'cycle matroid' or 'graphic matroid' of ''G''; it is usually written ''M''(''G'').
Any matroid that is equivalent to the cycle matroid of a (multi)graph, even if it is not presented in terms of graphs, is called a 'graphic matroid'. The matroids that are graphic have been characterized by Tutte.
Graphic matroids have been generalized to matroids from signed graphs and biased graphs.
Matroids from field extensions
A third original source of matroid theory is field theory.
An extension of a field gives rise to a matroid. Suppose ''F'' and ''K'' are fields with ''K'' containing ''F''. Let ''E'' be any finite subset of ''K''. Define a subset ''S'' of ''E'' to be independent if the extension field ''F''[''S''] has transcendence degree equal to |''S''|.
A matroid that is equivalent to a matroid of this kind is called an 'algebraic matroid'. The problem of characterizing algebraic matroids is extremely difficult; little is known about it.
The Fano matroid
Matroids with a small number of elements are often pictured as in the diagram. The dots are the elements of the underlying set, and a curve has been drawn through every circuit. The diagram shows a rank 3 matroid called the 'Fano matroid', an example that appeared in the original 1935 paper of Whitney.
The name arises from the fact that the Fano matroid is the projective plane of order 2, known as the Fano plane, whose coordinate field is the 2-element field. This means the Fano matroid is the vector matroid associated to the seven nonzero vectors in a three-dimensional vector space over a field with two elements.
It is known from projective geometry that the Fano matroid is not representable by any set of vectors in a real or complex vector space (or in any vector space over a field whose characteristic differs from 2).
Non-examples
On the other hand, consider this 'non-example': let ''E'' be a set of pairs (''v'',''c'') where ''v'' ranges over the vertices of a graph and ''c'' ranges over the the set {red, blue, yellow}. Let the independent sets be the sets of pairs that associate only one color with each vertex and do not associate the same color with two adjacent vertices; that is, they represent valid graph colorings. The empty set is a valid three-coloring, and any subset of a valid three-coloring is a valid three-coloring, but the exchange property does not hold, because it's possible to have two maximal three-colored subgraphs of different sizes, as shown to the right. It's no surprise that this is not a matroid, since if it were, it would give us a greedy algorithm for the NP-complete 3-coloring problem, showing P = NP.
Basic constructions
Let ''M'' be a matroid with an underlying set of elements ''E'', and let ''N'' be another matroid on underlying set ''F''.
There are some standard ways to make new matroids out of old ones.
★ 'Restriction'. If ''S'' is a subset of ''E'', the 'restriction' of ''M'' to ''S'', written ''M''|''S'', is the matroid on underlying set ''S'' whose independent sets are the independent sets of ''M'' that are contained in ''S''. Its circuits are the circuits of ''M'' that are contained in ''S'' and its rank function is that of ''M'' restricted to subsets of ''S''.
★ 'Contraction'. If ''T'' is a subset of ''E'', the 'contraction' of ''M'' by ''T'', written ''M''/''T'', is the matroid on the underlying set ''E − T'' whose rank function is
★ 'Minors'. A matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations is called a 'minor' of ''M''. We say ''M'' 'contains' ''N'' 'as a minor'.
★ 'Direct sum'. The 'direct sum' of ''M'' and ''N'' is the matroid whose underlying set is the disjoint union of ''E'' and ''F'', and whose independent sets are the disjoint unions of an independent set of ''M'' with an independent set of ''N''.
★ 'Matroid union'. The 'union' of ''M'' and ''N'' is the matroid whose underlying set is the union (not the disjoint union) of ''E'' and ''F'', and whose independent sets are those subsets whose intersections with both ''E'' and ''F'' are independent. Usually the term "union" is applied when ''E'' = ''F'', but that assumption is not essential. If ''E'' and ''F'' are disjoint, the union is the direct sum.
Additional terminology
Let ''M'' be a matroid with an underlying set of elements ''E''.
★ A subset of ''E'' 'spans' ''M'' if its closure is ''E''. A set is said to 'span' a closed set ''K'' if its closure is ''K''.
★ A maximal closed proper subset of ''E'' is called a 'coatom' or 'copoint' or 'hyperplane' of ''M''. An equivalent definition: A coatom is a subset of ''E'' that does not span ''M'', but such that adding any other element to it does make a spanning set.
★ An element that forms a single-element circuit of ''M'' is called a 'loop'.
★ An element that belongs to no circuit is called a ''coloop''.
★ If a two-element set {''f, g''} is a circuit of ''M'', then ''f'' and ''g'' are 'parallel' in ''M''.
★ ''M'' is called 'simple' if no 1- or 2-element subset of ''E'' is a circuit.
★ A simple matroid obtained from ''M'' by deleting all loops and deleting one element from each 2-element circuit until no 2-element circuits remain is called a 'simplification' of ''M''.
★ A matroid which cannot be written as the direct sum of two nonempty matroids is called 'connected' or 'irreducible'.
★ A maximal irreducible submatroid of ''M'' is called a 'component' of ''M''.
Further topics
Regular matroids
A matroid is 'regular' if it can be represented by a totally unimodular matrix (a matrix whose square submatrices all have determinants equal to 0, 1, or −1). Tutte proved that the following three properties of a matroid are logically equivalent:
# ''M'' is regular.
# ''M'' is representable over every field.
# ''M'' has no minor that is a four-point line or a Fano plane or its dual.
For this he used his difficult homotopy theorem. Simpler proofs have since been found.
The most amazing result about regular matroids is Seymour's decomposition theorem, that all regular matroids can be built up in a simple way from graphic matroids and their duals and one special matroid. This theorem has major consequences for linear programming involving totally unimodular matrices.
Binary matroids
A matroid that is representable over the two-element field is called a 'binary matroid'. Binary matroids include graphic and regular matroids. They have many of the nice properties of those types of matroid. Whitney and Tutte found famous characterizations. Addition of sets is symmetric difference. The following properties of a matroid ''M'' are equivalent:
# ''M'' is binary.
# In ''M'', every sum of circuits is a union of disjoint circuits (Whitney).
# ''M'' has no minor that is a four-point line (Tutte).
Forbidden minors
Suppose 'L' is a list of matroids. The class Ex('L') of all matroids that do not contain as a minor any member of the list is said to be 'characterized by forbidden minors' (or 'excluded minors'). Some of the great theorems of matroid theory characterize natural classes of matroids by forbidden minors. Three examples due to Tutte:
★ Binary matroids (see above).
★ Regular matroids (see above).
★ Graphic matroids are the matroids that have no minor that is the four-point line (which is self-dual), the Fano plane or its dual, the dual of the cycle matroid ''M''(''K''5), or the dual of the cycle matroid ''M''(''K''3,3).
It is easy to show that the matroids representable over a fixed field can be characterized by a list of forbidden minors. A famous outstanding problem ('Rota's conjecture') is to prove that this list is finite for finite fields. This has been solved only for the fields of up to four elements (and the exact lists are known for those fields, but one cannot expect exact lists for larger fields). The problem is significant because there are matroid properties that can be characterized by forbidden minors but not by a finite list of them—for example, the property of being representable over the real numbers.
The Robertson-Seymour Theorem, whose full proof runs to more than 500 pages, states that every matroid property of ''graphic'' matroids characterized by a list of forbidden minors can be characterized by a finite list—in other words, if an infinite list 'L' includes the forbidden minors for graphic matroids, then Ex('L') = Ex('L’') for some finite list 'L’'.
Matroid duality
If ''M'' is a finite matroid, we can define the 'dual matroid' ''M''
★ by taking the same underlying set and calling a set a ''basis'' in ''M''
★ if and only if its complement is a basis in ''M''. It is not difficult to verify that ''M''
★ is a matroid and that the dual of ''M''
★ is ''M''.
The dual can be described equally well in terms of other ways to define a matroid. For instance:
★ A set is independent in ''M''
★ if and only if its complement spans ''M''.
★ A set is a circuit of ''M''
★ if and only if its complement is a coatom in ''M''.
★ The rank function of the dual is r
★ (S) = |E|- r(M) - |S| + r(S).
A main result is the matroid version of Kuratowski's theorem: The dual of a graphic matroid ''M'' is a graphic matroid if and only if ''M'' is the matroid of a planar graph.
A simpler result is that the dual of a vector matroid representable over a particular field ''F'' is also representable over ''F''.
Greedy algorithms
A 'weight function' on a finite set ''E'' is a function ''w'': ''E'' → 'R'+ from ''E'' to the nonnegative real numbers. Abusing notation, such a weight function ''w'' can be extended to subsets ''S'' ⊆ ''E'' by defining
:''w''(''S'') = ∑''s'' ∈ ''S''''w''(''s'').
Suppose ''E'' is a finite set, ''F'' a nonempty family of subsets of ''E'' such that any subset of any element of ''F'' also belongs to ''F'', and ''w'': ''F'' → 'R'+ a weight function on ''F''. A greedy algorithm for (''E'', ''F'', ''w'') is any algorithm that attempts to construct a maximum weight element of ''F'' as follows:
:1. Let ''F''0 = ∅.
:2. For ''i'' ≥ 0:
:: 3. Let ''Z''''i'' = { ''z''''i'' ∈ ''E''-''F''''i'' | ''F''''i'' ∪ {''z''''i''} ∈ ''F'' }.
::4. If ''Z''''i'' = ∅, terminate and return ''F''''i''.
::5. Otherwise, choose an element ''y'' ∈ ''Z''''i'' such that ''w''(''y'') = max{''w''(''z''''i''), ''z''''i'' ∈ ''Z''''i''}, let ''F''''i''+1 = ''F''''i'' ∪ {''y''} and continue.
The following two theorems establish a correspondence between matroids and sets (''E'', ''F'') as defined above for which greedy algorithms do give maximum weight solutions.
:'Theorem 1': If ''E'' in (''E'', ''F'', ''w'') is the underlying set of a matroid ''M'' and ''F'' is the set of independent sets in ''M'', then any greedy algorithm for (''E'', ''F'', ''w'') constructs a maximum weight element of ''F''.
:'Theorem 2': If every greedy algorithm for the pair (''E'', ''F'') constructs a maximum weight element of ''F'' for every choice of weight function ''w'': ''F'' → 'R'+ then ''F'' is the set of independent sets of a matroid ''M'' with underlying set ''E''.
The notion of matroid has been generalized to allow for other types of sets on which greedy algorithms give optimal solutions; see greedoid for more information.
Infinite matroids
The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. One of the difficulties is that there are many reasonable and useful definitions, none of which captures all the important aspects of finite matroid theory. For instance, it seems to be hard to have bases, circuits, and duality together in one notion of infinite matroids.
See also
★ Infinite matroid
★ Oriented matroid
★ Tutte polynomial
★ Weighted matroid
★ Gian-Carlo Rota
★ P.D. Seymour
★ W. T. Tutte
★ Hassler Whitney
References
★ Crapo, H., and Rota, G-C. (1970), ''On the Foundations of Combinatorial Theory: Combinatorial Geometries.'' M.I.T. Press, Cambridge, Mass.
★ Oxley, J. (1992), ''Matroid Theory''. Oxford University Press, New York. ISBN 0-19-853563-5.
★ White, N., ed. (1986), ''Theory of Matroids''. Encyclopedia of Mathematics and its Applications, Vol. 26. Cambridge University Press, Cambridge.
★ Whitney, H. (1935), "On the abstract properties of linear dependence". ''American Journal of Mathematics'', vol. 57, pp. 509-533.
External links
★
★ Contains several other equivalent definitions of matroids.
★
★ S. C. Locke: Greedy Algorithms.
★ Steven R. Pagano: Matroids and Signed Graphs.
★ Sandra Kingan: Matroid theory. Lots of links.
★ Klaus Truemper Matroid decomposition.
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
