|
|
| (569 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| In [[combinatorics]], a branch of [[mathematics]], a '''matroid''' ({{IPAc-en|icon|ˈ|m|eɪ|t|r|ɔɪ|d}}) or '''independence structure''' is a structure that captures and generalizes the notion of [[linear independence]] in [[vector space]]s.
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| There are many equivalent ways to define a matroid, 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.
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| 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.
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| ==Definition==<!-- [[Hereditary property (matroid)]] redirects to this section title--> | | '''MathML''' |
| There are many equivalent ([[Cryptomorphism|cryptomorphic]]) ways to define a (finite) matroid.
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| ===Independent sets===
| | <!--'''PNG''' (currently default in production) |
| In terms of independence, a finite matroid <math>M</math> is a pair <math>(E,\mathcal{I})</math>, where <math>E</math> is a [[finite set]] (called the '''ground set''') and <math>\mathcal{I}</math> is a [[family of sets|family]] of [[subset]]s of <math>E</math> (called the '''independent sets''') with the following properties:
| | :<math forcemathmode="png">E=mc^2</math> |
| # The [[empty set]] is independent, i.e., <math>\emptyset\in\mathcal{I}</math>. Alternatively, at least one subset of <math>E</math> is independent, i.e., <math>\mathcal{I}\neq\emptyset</math>.
| |
| # Every subset of an independent set is independent, i.e., for each <math>A'\subset A\subset E</math>, if <math>A\in\mathcal{I}</math> then <math>A'\in\mathcal{I}</math>. This is sometimes called the '''hereditary property'''.
| |
| # If <math>A</math> and <math>B</math> are two independent sets of <math>\mathcal{I}</math> and <math>A</math> has more elements than<math>B</math>, then there exists an element in <math>A</math> that when added to <math>B</math> gives a larger independent set. This is sometimes called the '''augmentation property''' or the '''independent set exchange property'''.
| |
|
| |
|
| The first two properties define a combinatorial structure known as an [[independence system]].
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| ===Bases and circuits=== | | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
| A subset of the ground set <math>E</math> that is not independent is called '''dependent'''. A maximal independent set—that is, an independent set which becomes dependent on adding any element of <math>E</math>—is called a '''basis''' for the matroid. A '''circuit''' in a matroid <math>M</math> is a minimal dependent subset of <math>E</math>—that is, a dependent set whose proper subsets are all independent. The terminology arises because the circuits of [[graphic matroid]]s 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 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 <math>M</math> to be a pair <math>(E,\mathcal{B})</math>, where <math>E</math> is a finite set as before and <math>\mathcal{B}</math> is a collection of subsets of <math>E</math>, called "bases", with the following properties:
| | ==Demos== |
| # <math>\mathcal{B}</math> is nonempty.
| |
| # If <math>A</math> and <math>B</math> are distinct members of <math>\mathcal{B}</math> and <math>a\in A\setminus B</math>, then there exists an element <math>b\in B\setminus A</math> such that <math>A\setminus\{a\}\cup\{b\}\in\mathcal{B}</math>. (Here the backslash symbol stands for the [[Complement (set theory)|difference of sets]]. This property is called the '''basis exchange property'''.)
| |
| It follows from the basis exchange property that no member of <math>\mathcal{B}</math> can be a proper subset of another.
| |
|
| |
|
| ===Rank functions===
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
| It is a basic result of matroid theory, directly analogous to a similar [[basis (linear algebra)|theorem of linear algebra]], that any two bases of a matroid <math>M</math> have the same number of elements. This number is called the '''rank''' of <math>M</math>. If <math>M</math> is a matroid on <math>E</math>, and <math>A</math> is a subset of <math>E</math>, then a matroid on <math>A</math> can be defined by considering a subset of <math>A</math> to be independent if and only if it is independent in <math>M</math>. This allows us to talk about '''submatroids''' and about the rank of any subset of <math>E</math>.
| |
|
| |
|
| The '''rank function''' <math>r</math> assigns a non-negative integer to every subset of <math>E</math> and has the following properties:
| |
| # If <math>A\subset B\subset E</math>, then <math>r(A)\leq r(B)\leq r(E)</math>. That is, the rank is a [[monotonic function]].
| |
| # For any two subsets <math>A</math> and <math>B</math> of <math>E</math>, <math>r(A\cup B)+r(A\cap B)\le r(A)+r(B)</math>. That is, the rank is a [[submodular function]].
| |
|
| |
|
| These properties can be used as one of the alternative definitions of a finite matroid: if <math>(E,r)</math> satisfies these properties, then the independent sets of a matroid over <math>E</math> can be defined as those subsets <math>A</math> of <math>E</math> with <math>r(A)=|A|</math>.
| | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| The difference <math>|A|-r(A)</math> is called the '''nullity''' or '''corank''' of the subset <math>A</math>. It is the minimum number of elements that must be removed from <math>A</math> to obtain an independent set. The nullity of <math>E</math> in <math>M</math> is called the nullity or corank of <math>M</math>.
| | ==Test pages == |
|
| |
|
| ===Closure operators===
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| Let <math>M</math> be a matroid on a finite set <math>E</math>, with rank function <math>r</math> as above. The '''closure''' <math>\operatorname{cl}(A)</math> of a subset <math>A</math> of <math>E</math> is the set
| | *[[Displaystyle]] |
| :<math>\operatorname{cl}(A) = \Bigl\{x\in E\mid r(A)=r\bigl(A\cup\{x\}\bigr)\Bigr\}</math>.
| | *[[MathAxisAlignment]] |
| This defines a [[closure operator]] <math>\operatorname{cl}: \mathcal{P}(E)\mapsto \mathcal{P}(E)</math> where <math>\mathcal{P}</math> denotes the [[power set]], with the following property:
| | *[[Styling]] |
| * For all elements <math>a</math>, and <math>b</math> of <math>E</math> and all subsets <math>Y</math> of <math>E</math>, if <math>a\in\operatorname{cl}(Y\cup b) \setminus Y</math> then <math>b\in\operatorname{cl}(Y\cup a) \setminus Y</math>. | | *[[Linebreaking]] |
| This is sometimes called the '''Mac Lane–Steinitz exchange property''' and may be taken as another definition of matroid: any closure operator on <math>E</math> with this property determines a matroid.
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| ===Flats===
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| A set whose closure equals itself is said to be '''closed''', or a '''flat''' or '''subspace''' of the matroid. A set is closed if it is [[maximal element|maximal]] for its rank, meaning that the addition of any other element to the set would increase the rank. The closed sets of a matroid are characterized by a covering partition property:
| | *[[Url2Image|Url2Image (private Wikis only)]] |
| * The whole point set <math>E</math> is closed. | | ==Bug reporting== |
| * If <math>S</math> and <math>T</math> are flats, then <math>S\cap T</math> is a flat.
| | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| * If <math>S</math> is a flat, then the flats <math>T</math> that [[Covering relation|cover]] <math>S</math> (meaning that <math>T</math> properly contains <math>S</math> but there is no flat <math>U</math> between <math>S</math> and <math>T</math>), partition the elements of <math>E\setminus S</math>.
| |
| | |
| The class <math>\mathcal{L}(M)</math> of all flats, [[partially ordered set|partially ordered]] by set inclusion, forms a [[matroid lattice]].
| |
| Conversely, every matroid lattice <math>L</math> forms a matroid over its set <math>E</math> of [[Atom_(order_theory)|atoms]] under the following closure operator: for a set <math>S</math> of atoms with join <math>\vee S</math>,
| |
| :<math>\operatorname{cl}(S) = \{ x\in E\mid x\le\vee S \}</math>.
| |
| The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element <math>y</math> is the set
| |
| :<math>\{ x\in E\mid x\le y\}</math>.
| |
| Thus, the lattice of flats of this matroid is naturally isomorphic to <math>L</math>.
| |
| | |
| == Examples ==
| |
| ===Uniform matroids===
| |
| | |
| 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''. All uniform matroids of rank at least 2 are simple. The uniform matroid of rank 2 on ''n'' points is called the ''n''-'''point line'''. A matroid is uniform if and only if it has no circuits of size less than the one plus the rank of the matroid. The direct sums of uniform matroids are called [[partition matroid]]s.
| |
| | |
| ===Discrete matroids===
| |
| | |
| A matroid is called '''discrete''' if every element is a loop or a coloop. Equivalently, every proper, non-empty subset of the ground set ''E'' is a separator (loop, coloop, and separator are defined in Additional Terminology below).
| |
| | |
| ===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 [[linear independence|linearly independent]] subsets of ''E''. We say the set ''E'' '''represents''' ''M''. Matroids of this kind are called '''vector matroids'''.
| |
| * A [[matrix (mathematics)|matrix]] ''A'' with entries in a [[field (mathematics)|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 (mathematics)|field]] ''F'', then we say ''M'' is '''representable over''' ''F'' ; in particular, ''M'' is '''real-representable''' if it is representable over the real numbers. 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''. The main results so far are characterizations of binary matroids due to Tutte (1950s), of ternary matroids (representable over the 3-element field) due to Reid and Bixby, and separately to Seymour (1970s), and of quaternary matroids (representable over the 4-element field) due to Geelen, Gerards, and Kapoor (2000). This is very much an open area.
| |
| | |
| A [[regular matroid]] is a matroid that is representable over all possible fields. [[Rota's conjecture]] states that, for every [[finite field]] ''F'', the ''F''-representable matroids have a finite set of [[matroid minor|forbidden minors]].
| |
| | |
| ===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 is a [[tree (graph theory)|forest]]; that is, if it does not contain a [[simple cycle]]. This is called the [[graphic matroid]] of ''G'' and is usually written ''M''(''G''). Every graphic matroid is regular.
| |
| | |
| Other matroids on graphs were discovered subsequently:
| |
| *The [[bicircular matroid]] of a graph is defined by calling a set of edges independent if every connected subset contains at most one cycle.
| |
| *In any directed or undirected graph ''G'' let ''E'' and ''F'' be two distinguished sets of vertices. In the set ''E'', define a subset ''U'' to be independent if there are |''U''| vertex-disjoint paths from ''F'' onto ''U''. This defines a matroid on ''E'' called a [[gammoid]].
| |
| *Graphic matroids have been generalized to matroids from [[signed graph]]s, [[gain graph]]s, and [[biased graph]]s. A graph ''G'' with a distinguished linear class '''''B''''' of cycles, known as a "biased graph" (''G'','''''B'''''), has two matroids, known as the '''frame matroid''' and the '''lift matroid''' of the biased graph. If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of ''G''. If no cycle is distinguished, the frame matroid is the bicircular matroid of ''G''. A signed graph, whose edges are labeled by signs, and a gain graph, which is a graph whose edges are labeled orientably from a group, each give rise to a biased graph and therefore have frame and lift matroids.
| |
| *The [[Laman graph]]s form the bases of the two-dimensional [[rigidity matroid]], a matroid defined in the theory of [[structural rigidity]].
| |
| | |
| ===Transversal matroids===
| |
| Given a set of "points", ''E'', and a class ''A'' of subsets of ''E'', a '''[[Transversal (combinatorics)|transversal]]''' of ''A'' is a subset ''S'' of ''E'' such that there is a [[one-to-one function]] ''f'' from ''S'' to ''A'' by which ''x'' belongs to ''f'' (''x'') for each ''x'' in ''S''. The set of transversals forms the class of independent sets of a matroid, called the '''transversal matroid''' of (''E'', ''A''). Transversal matroids are a special case of gammoids, and are dual to strict gammoids (gammoids in which the set of elements consists of all vertices in the defining graph).
| |
| | |
| ===Matroids from field extensions===
| |
| A third original source of matroid theory is [[field theory (mathematics)|field theory]].
| |
| | |
| An [[extension field|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===
| |
| [[Image:fano plane.svg|thumb|right|Fano matroid]]
| |
| | |
| Matroids with a small number of elements are often portrayed with a diagram. The dots are the elements of the underlying set, and a curve has been drawn through every rank-2 flat. The diagram shows a rank 3 matroid called the '''Fano matroid''', an example that appeared in the original 1935 paper of [[Hassler Whitney|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 [[finite field|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 (algebra)|characteristic]] differs from 2).
| |
| | |
| A less famous example is the '''anti-Fano matroid''', defined in the same way as the Fano matroid with the exception that the circle in the above diagram is missing. The anti-Fano matroid is representable over a field if and only if its characteristic differs from 2.
| |
| | |
| The direct sum of a Fano matroid and an anti-Fano matroid is the simplest example for a matroid which is not representable over any field.
| |
| | |
| ===Non-examples===
| |
| | |
| [[Image:Maximal three-colorable.png|right|frame|Two maximal three-colorings of different sizes. The one on the left cannot be enlarged because the only remaining vertex is already adjacent to all three colors.]]
| |
| 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 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 coloring]]s. 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 ==
| |
| There are some standard ways to make new matroids out of old ones.
| |
| | |
| ===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) = |S|- r(E) + r(E\S).
| |
| | |
| According to a 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]]. In this case, the dual of ''M'' is the matroid of the [[dual graph]] of ''G''. A the dual of a vector matroid representable over a particular field ''F'' is also representable over ''F''. The dual of a transversal matroid is a strict gammoid and vice versa.
| |
| | |
| ===Minors===
| |
| If ''M'' is a matroid with element set ''E'', and ''S'' is a subset of ''E'', the '''restriction''' of ''M'' to ''S'', written ''M'' |''S'', is the matroid on the 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''. In linear algebra, this corresponds to restricting to the subspace generated by the vectors in ''S''.
| |
| The dual operation of restriction is 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 <math>r'(A) = r(A \cup T) - r(T).</math> In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in ''T'', together with the images of the vectors in ''E - T''.
| |
| | |
| A matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations is called a [[matroid minor|minor]] of ''M''. We say ''M'' '''contains''' ''N'' '''as a minor'''. Many important families of matroids may be characterized by the [[minimal element|minor-minimal]] matroids that do not belong to the family; these are called '''forbidden minors'''.
| |
| | |
| ===Sums and unions===
| |
| Let ''M'' be a matroid with an underlying set of elements ''E'', and let ''N'' be another matroid on an underlying set ''F''.
| |
| The '''direct sum''' of matroids ''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''.
| |
| | |
| 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 which are the union of an independent set in ''M'' and one in ''N''. 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''.
| |
| * ''E'' may be called the '''ground set''' of ''M''. Its elements may be called the '''points''' of ''M''.
| |
| * 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'''. Equivalently, an element is a loop if it belongs to no basis.
| |
| * An element that belongs to no circuit is called a '''coloop'''. Equivalently, an element is a coloop if it belongs to every basis.
| |
| * If a two-element set {''f, g''} is a circuit of ''M'', then ''f'' and ''g'' are '''parallel''' in ''M''.
| |
| * A matroid is called '''simple''' if it has no circuits consisting of 1 or 2 elements. That is, it has no loops and no parallel elements. A simple matroid obtained from another matroid ''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 union of circuits is sometimes called a '''cycle''' of ''M''. A cycle is therefore the complement of a flat of the dual matroid. (This usage conflicts with the common meaning of "cycle" in graph theory.)
| |
| * A '''separator''' of ''M'' is a subset ''S'' of ''E'' such that <math>r(S) + r(E-S) = r(M).</math> A '''proper separator''' is a separator that is neither ''E'' nor the empty set. An '''irreducible separator''' is a separator that contains no other non-empty separator. The irreducible separators partition the ground set ''E''.
| |
| * A matroid which cannot be written as the direct sum of two nonempty matroids, or equivalently which has no proper separators, is called '''connected''' or '''irreducible'''.
| |
| * A maximal irreducible submatroid of ''M'' is called a '''component''' of ''M''. A component is the restriction of ''M'' to an irreducible separator, and contrariwise, the restriction of ''M'' to an irreducible separator is a component.
| |
| * A matroid ''M'' is called a '''frame matroid''' if it, or a matroid that contains it, has a basis such that all the points of ''M'' are contained in the lines that join pairs of basis elements.
| |
| | |
| == Further topics ==
| |
| | |
| ===Greedy algorithms===
| |
| A [[weighted matroid]] is a matroid together with a function from its elements to the nonnegative [[real number]]s. The weight of a subset of elements is defined to be the sum of the weights of the elements in the subset. A [[greedy algorithm]] can be used to find the maximum weight independent set of the matroid, by starting from the empty set and repeatedly adding one element at a time, at each step choosing the maximum weight element among the elements whose addition would preserve the independence of the augmented set.
| |
| | |
| This optimization algorithm may be used to characterize matroids: if a family ''F'' of sets has the property that, no matter how the sets are weighted, the greedy algorithm finds the maximum-weight set in the family, then ''F'' must be the family of independent sets of a matroid.
| |
| | |
| 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.
| |
| | |
| ===Matroid intersection===
| |
| The [[matroid intersection|intersection]] of two or more matroids is the family of sets that are simultaneously independent in each of the matroids. The problem of finding the largest set, or the maximum weighted set, in the intersection of two matroids can be found in [[polynomial time]], and provides a solution to many other important combinatorial optimization problems. For instance, [[maximum matching]] in [[bipartite graph]]s can be expressed as a problem of intersecting two [[partition matroid]]s. However, finding the largest set in an intersection of three or more matroids is [[NP-complete]].
| |
| | |
| === Infinite matroids ===
| |
| <!-- [[Infinite matroid]] redirects here. -->
| |
| The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. For a long time, one of the difficulties has been that there were many reasonable and useful definitions, none of which appeared to capture all the important aspects of finite matroid theory. For instance, it seemed to be hard to have bases, circuits, and duality together in one notion of infinite matroids.
| |
| | |
| The simplest definition of an infinite matroid is to require ''finite rank''; that is, the rank of ''E'' is finite. This theory is similar to that of finite matroids except for the failure of duality due to the fact that the dual of an infinite matroid of finite rank does not have finite rank. Finite-rank matroids include any subsets of finite-dimensional vector spaces and of [[Field (mathematics)|field extensions]] of finite [[transcendence degree]].
| |
| | |
| The next simplest infinite generalization is finitary matroids. A matroid is '''finitary''' if it has the property that
| |
| :<math>x \in cl(Y) \Leftrightarrow (\exists Y' \subseteq Y) Y' \text{ is finite and } x \in cl(Y').</math>
| |
| Equivalently, every dependent set contains a finite dependent set.
| |
| Examples are linear dependence of arbitrary subsets of infinite-dimensional [[vector spaces]] (but not infinite dependencies as in [[Hilbert space|Hilbert]] and [[Banach space]]s), and algebraic dependence in arbitrary subsets of field extensions of possibly infinite transcendence degree. Again, the class of finitary matroid is not self-dual, because the dual of a finitary matroid is not finitary.
| |
| Finitary infinite matroids are studied in [[model theory]], a branch of [[mathematical logic]] with strong ties to [[algebra]].
| |
| | |
| In the late 1960s matroid theorists asked for a more general notion that shares the different aspects of finite matroids and generalizes their duality. Many notions of infinite matroids were defined in response to this challenge, but the question remained open. One of the approaches examined by D.A. Higgs became known as ''B-matroids'' and was studied by Higgs, Oxley and others in the 1960s and 1970s. According to a recent result by Bruhn, Diestel, Kriesell, Pendavingh and Wollan ([[#CITEREFBruhnDiestelKriesellWollan2010|2010]]), it solves the problem: Arriving at the same notion independently, they provided four different systems of axioms – in terms of independence, bases, circuits, closure and rank. The duality of B-matroids generalizes dualities that can be observed in infinite graphs.
| |
| | |
| ==Polynomial invariants==
| |
| | |
| There are two especially significant polynomials associated to a finite matroid ''M'' on the ground set ''E''. Each is a '''matroid invariant''', which means that isomorphic matroids have the same polynomial.
| |
| | |
| ===Characteristic polynomial===
| |
| | |
| The '''characteristic polynomial''' of ''M'' (which is sometimes called the '''chromatic polynomial''', although it does not count colorings), is defined to be
| |
| :<math>p_M(\lambda) := \sum_{S \subseteq E} (-1)^{|S|}\lambda^{r(M)-r(S)},</math>
| |
| or equivalently (as long as the empty set is closed in ''M'') as
| |
| :<math>p_M(\lambda) := \sum_A \mu(\emptyset,A) \lambda^{r(M)-r(S)}.</math>
| |
| | |
| When ''M'' is the cycle matroid ''M''(''G'') of a graph ''G'', the characteristic polynomial is a slight transformation of the [[chromatic polynomial]], which is given by χ<sub>''G''</sub> (λ) = λ<sup>c</sup>''p''<sub>''M''(''G'')</sub> (λ), where ''c'' is the number of connected components of ''G''.
| |
| | |
| When ''M'' is the bond matroid ''M''*(''G'') of a graph ''G'', the characteristic polynomial equals the [[Tutte polynomial#Flow polynomial|flow polynomial]] of ''G''.
| |
| | |
| When ''M'' is the matroid of an [[Arrangement of hyperplanes|arrangement]] ''A'' of linear hyperplanes in '''R'''<sup>''n''</sup>, the characteristic polynomial of the arrangement is given by ''p''<sub>''A''</sub> (λ) = λ<sup>n−r(M)</sup>''p''<sub>''M''(''A'')</sub> (λ).
| |
| | |
| ===Tutte polynomial=== | |
| | |
| The '''[[Tutte polynomial]]''' of a matroid, ''T''<sub>''M''</sub> (''x'',''y''), generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property
| |
| :<math>T_{M^*}(x,y) = T_M(y,x),</math>
| |
| which implies a number of dualities between properties of ''M'' and properties of ''M'' *. One definition of the Tutte polynomial is
| |
| :<math>T_M(x,y) = \sum_{S\subseteq E} (x-1)^{r(M)-r(S)}(y-1)^{|S|-r(S)}.</math>
| |
| This expresses the Tutte polynomial as an evaluation of the '''corank-nullity''' or '''rank generating polynomial''',
| |
| :<math>R_M(x,y) = \sum_{S\subseteq E} v^{r(M)-r(S)}u^{|S|-r(S)}.</math>
| |
| | |
| Another definition is in terms of internal and external activities and a sum over bases. This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.
| |
| | |
| The [[Tutte polynomial]] ''T''<sub>''G''</sub> of a graph is the Tutte polynomial ''T''<sub>''M''(''G'')</sub> of its cycle matroid.
| |
| | |
| ==Matroid software==
| |
| | |
| Two systems for calculations with matroids are Kingan's [http://userhome.brooklyn.cuny.edu/skingan/software.html Oid] and Hlineny's [http://www.fi.muni.cz/~hlineny/MACEK/ Macek].
| |
| | |
| "Oid" is an open source, interactive, extensible software system for experimenting with matroids.
| |
| | |
| "Macek" is a specialized software system with tools and routines for reasonably efficient combinatorial computations with representable matroids.
| |
| | |
| ==History==
| |
| | |
| Matroid theory was introduced by {{harvs|last=Whitney|first=Hassler|authorlink=Hassler Whitney|year=1935|txt}}. It was also independently discovered by [[Takeo Nakasawa]], whose work was forgotten for many years {{harv|Nishimura|Kuroda|2009}}.
| |
| | |
| In his seminal paper, Whitney provided two axioms for independence, and defined any structure adhering to these axioms to be "matroids".
| |
| (Although it was perhaps implied, he did not include an axiom requiring at least one subset to be independent.)
| |
| His key observation was that these axioms provide an abstraction of "independence" that is common to both graphs and matrices.
| |
| Because of this, many of the terms used in matroid theory resemble the terms for their analogous concepts in [[linear algebra]] or [[graph theory]].
| |
| | |
| Almost immediately after Whitney first wrote about matroids, an important article was written by {{harvs|last=Mac Lane|first=Saunders|authorlink=Saunders Mac Lane|year=1936|txt}} on the relation of matroids to projective geometry. A year later, {{harvs|last=van der Waerden|first=Bartel|authorlink=Bartel Leendert van der Waerden|year=1937|txt}} noted similarities between algebraic and linear dependence in his classic textbook on Modern Algebra.
| |
| | |
| In the 1940s [[Richard Rado]] developed further theory under the name "independence systems" with an eye towards [[transversal theory]], where his name for the subject is still sometimes used.
| |
| | |
| In the 1950s [[W. T. Tutte]] became the foremost figure in matroid theory, a position he retained for many years. His contributions were plentiful, including the characterization of [[binary matroid|binary]], [[regular matroid|regular]], and [[graphic matroid|graphic]] matroids by [[Matroid minor|excluded minors]]; the regular-matroid representability theorem; the theory of chain groups and their matroids; and the tools he used to prove many of his results, the "Path Theorem" and "Homotopy Theorem" (see, e.g., {{harvnb|Tutte|1965}}), which are so complex that later theorists have gone to great trouble to eliminate the necessity of using them in proofs. (A fine example is [[A. M. H. Gerards]]' short proof ([[#CITEREFGerard1989|1989]]) of Tutte's characterization of regular matroids.)
| |
| | |
| {{harvtxt|Crapo|1969}} and {{harvtxt|Brylawski|1972}} generalized to matroids Tutte's "dichromate", a graphic polynomial now known as the [[Tutte polynomial]] (named by Crapo). Their work has recently been followed by a flood of papers—though not as many as on the Tutte polynomial of a graph.
| |
| | |
| In 1976 Dominic Welsh published the first comprehensive book on matroid theory.
| |
| | |
| [[Paul Seymour (mathematician)|Paul Seymour]]'s decomposition theorem for regular matroids ([[#CITEREFSeymour1980|1980]]) was the most significant and influential work of the late 1970s and the 1980s.
| |
| Another fundamental contribution, by {{harvtxt|Kahn|Kung|1982}}, showed why projective geometries and Dowling geometries play such an important role in matroid theory.
| |
| | |
| By this time there were many other important contributors, but one should not omit to mention Geoff Whittle's extension to ternary matroids of Tutte's characterization of binary matroids that are representable over the rationals {{harv|Whittle|1995}}, perhaps the biggest single contribution of the 1990s. In the current decade{{When|date=August 2011}} the Matroid Minors Project of [[Jim Geelen|Geelen]], Gerards, Whittle, and others, which attempts to duplicate for matroids that are representable over a finite field the success of the Robertson–Seymour Graph Minors Project (see [[Robertson–Seymour theorem]]), has produced substantial advances in the structure theory of matroids. Many others have also contributed to that part of matroid theory, which is presently{{When|date=August 2011}} flourishing.
| |
| | |
| ==See also==
| |
| * [[Algebraic independence]]
| |
| * [[Antimatroid]]
| |
| * [[Oriented matroid]]
| |
| * [[Pregeometry (model theory)]]
| |
| | |
| ==Researchers==
| |
| | |
| Mathematicians who pioneered the study of matroids include the following:
| |
| * [[Saunders Mac Lane]]
| |
| * [[Richard Rado]]
| |
| * [[W. T. Tutte]]
| |
| * [[Bartel Leendert van der Waerden|B. L. van der Waerden]]
| |
| * [[Hassler Whitney]]
| |
| | |
| Other major contributors include:
| |
| * [[Henry Crapo (mathematician)|Henry Crapo]]
| |
| * [[Jack Edmonds]]
| |
| * [[Jim Geelen]]
| |
| * [[Gian-Carlo Rota]]
| |
| * [[Paul Seymour (mathematician)|P. D. Seymour]]
| |
| * [[Geoff Whittle]]
| |
| | |
| There is an on-line list of [http://userhome.brooklyn.cuny.edu/skingan/matroids/people.html current researchers].
| |
| | |
| ==Notes==
| |
| {{reflist}}
| |
| | |
| == References ==
| |
| *{{citation |last1=Bruhn |first1=Henning |last2=Diestel |first2=Reinhard |last3=Kriesell |first3=Matthias |last4=Pendavingh |first4=Rudi |last5=Wollan |first5=Paul |title=Axioms for infinite matroids |year=2010 |arxiv=1003.3919 }}.
| |
| *{{citation|last1=Bryant|first1=Victor|last2=Perfect|first2=Hazel|year=1980|title=Independence Theory in Combinatorics|publisher=Chapman and Hall|location=London and New York|isbn=0-412-22430-5}}.
| |
| *{{citation|last=Brylawski|first=Thomas H.|year=1972|title=A decomposition for combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=171|pages=235–282|doi=10.2307/1996381|publisher=American Mathematical Society|jstor=1996381}}.
| |
| *{{citation|last=Crapo|first=Henry H.|authorlink=Henry H. Crapo|year=1969|title=The Tutte polynomial|journal=Aequationes Mathematicae|volume=3|issue=3|pages=211–229|doi=10.1007/BF01817442}}.
| |
| *{{citation|last1=Crapo|first=Henry H.|authorlink=Henry H. Crapo|last2=Rota|first2=Gian-Carlo|author2-link=Gian-Carlo Rota|year=1970|title=On the Foundations of Combinatorial Theory: Combinatorial Geometries|publisher=M.I.T. Press|location=Cambridge, Mass.|isbn=978-0-262-53016-3|mr=0290980}}.
| |
| *{{citation|last1=Geelen|first1=Jim|last2=Gerards|first2=A. M. H.|last3=Whittle|first3=Geoff|year=2007|contribution=Towards a matroid-minor structure theory|editor=Grimmett, Geoffrey (ed.) et al|title=Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh|series=Oxford Lecture Series in Mathematics and its Applications|volume=34|pages=72–82|publisher=Oxford University Press|publication-place=Oxford}}.
| |
| *{{citation|last=Gerards|first=A. M. H.|year=1989|title=A short proof of Tutte's characterization of totally unimodular matrices|journal=[[Linear Algebra and its Applications]]|volume=114/115|pages=207–212|doi=10.1016/0024-3795(89)90461-8}}.
| |
| *{{citation|last1=Kahn|first1=Jeff|last2=Kung|first2=Joseph P. S.|year=1982|title=Varieties of combinatorial geometries|journal=Transactions of the American Mathematical Society|volume=271|pages=485–499|doi=10.2307/1998894|issue=2|publisher=American Mathematical Society|jstor=1998894}}.
| |
| *{{citation|last1=Kingan|first1=Robert|last2=Kingan|first2=Sandra | year=2005|contribution=A software system for matroids|title=Graphs and Discovery|series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science|pages=287–296}}.
| |
| *{{citation|editor-last=Kung|editor-first=Joseph P. S.|title=A Source Book in Matroid Theory|publisher=Birkhäuser|isbn=0-8176-3173-9|location=Boston|year=1986|mr=0890330}}.
| |
| *{{citation|last=Mac Lane|first=Saunders|authorlink=Saunders Mac Lane|year=1936|title=Some interpretations of abstract linear dependence in terms of projective geometry|journal=American Journal of Mathematics|volume=58|pages=236–240|doi=10.2307/2371070|issue=1|publisher=The Johns Hopkins University Press|jstor=2371070}}.
| |
| *{{citation|mr=2516551
| |
| |title=A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
| |
| |editor-first=Hirokazu |editor-last=Nishimura |editor2-first=Susumu |editor2-last=Kuroda|publisher= Birkhäuser Verlag|place= Basel|year= 2009|isbn= 978-3-7643-8572-9|url=http://www.springerlink.com/content/978-3-7643-8572-9}}.
| |
| *{{citation|last=Oxley|first=James|year=1992|title=Matroid Theory|publisher=Oxford University Press|location=New York|isbn=0-19-853563-5|mr=1207587}}.
| |
| *{{citation|last=Recski|first=András|year=1989|title=Matroid Theory and its Applications in Electric Network Theory and in Statics|publisher=Springer-Verlag and Akademiai Kiado|location=Berlin and Budapest|isbn=3-540-15285-7|mr=1027839}}.
| |
| *{{eom|id=M/m062870|first=A.A.|last= Sapozhenko}}
| |
| *{{citation|last=Seymour|first=Paul D.|authorlink=Paul Seymour (mathematician)|year=1980|title=Decomposition of regular matroids|journal=Journal of Combinatorial Theory, Series B|volume=28|issue=3|pages=305–359|doi=10.1016/0095-8956(80)90075-1}}.
| |
| *{{citation|last=Truemper|first=Klaus|title=Matroid Decomposition|publisher=Academic Press|location=Boston|year=1992|isbn=0-12-701225-7|url=http://www.emis.de/monographs/md/index.html|mr=1170126}}.
| |
| *{{citation|last=Tutte|first=W. T.|authorlink=W. T. Tutte|year=1959|title=Matroids and graphs|journal=Transactions of the American Mathematical Society|volume=90|pages=527–552|doi=10.2307/1993185|issue=3|publisher=American Mathematical Society|mr=0101527|jstor=1993185}}.
| |
| *{{citation|last=Tutte|first=W. T.|authorlink=W. T. Tutte|year=1965|title=Lectures on matroids|journal=Journal of Research of the National Bureau of Standards (U.S.A.), Sect. B|volume=69|pages=1–47}}.
| |
| *{{citation|last=Tutte|first=W. T.|authorlink=W. T. Tutte|year=1971|title=Introduction to the Theory of Matroids|location=New York|publisher=American Elsevier}}.
| |
| *{{citation|last=Vámos|first=Peter|year=1978|title=The missing axiom of matroid theory is lost forever|journal=Journal of the London Mathematical Society, II. Ser.|volume=18|pages=403–408|doi=10.1112/jlms/s2-18.3.403|issue=3}}.
| |
| *{{citation|last=van der Waerden|first=B. L.|authorlink=Bartel Leendert van der Waerden|year=1937|title=Moderne Algebra}}.
| |
| *{{citation|last=Welsh|first=D. J. A.|year=1976|title=Matroid Theory|publisher=Academic Press|isbn=0-12-744050-X}}.
| |
| *{{citation|editor-last=White|editor-first=Neil|year=1986|title=Theory of Matroids|series=Encyclopedia of Mathematics and its Applications|volume=26|publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-30937-0}}.
| |
| *{{citation|editor-last=White|editor-first=Neil|year=1992|title=Matroid Applications|series=Encyclopedia of Mathematics and its Applications|volume=40|publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-38165-9}}.
| |
| *{{citation|last=Whitney|first=Hassler|authorlink=Hassler Whitney|year=1935|title=On the abstract properties of linear dependence|journal=American Journal of Mathematics|volume=57|pages=509–533|doi=10.2307/2371182|issue=3|publisher=The Johns Hopkins University Press|mr=1507091|jstor=2371182}}. Reprinted in {{harvtxt|Kung|1986}}, pp. 55–79.
| |
| *{{citation|last=Whittle|first=Geoff|year=1995|title=A characterization of the matroids representable over ''GF''(3) and the rationals|journal=Journal of Combinatorial Theory Series B|volume=65|issue=2|pages=222–261|url=http://eprints.kfupm.edu.sa/39296/1/39296.pdf|doi=10.1006/jctb.1995.1052}}.
| |
| | |
| == External links ==
| |
| | |
| * Kingan, Sandra : [http://userhome.brooklyn.cuny.edu/skingan/matroids/ Matroid theory]. A large bibliography of matroid papers, matroid software, and links.
| |
| * Locke, S. C. : [http://www.math.fau.edu/locke/Greedy.htm Greedy Algorithms].
| |
| * Pagano, Steven R. : [http://www.math.binghamton.edu/zaslav/Pagano/Matridx.htm Matroids and Signed Graphs].
| |
| * Mark Hubenthal: [http://www.math.washington.edu/~hubenjm/matroid2.pdf A Brief Look At Matroids] ([[pdf]]) (contain proofs for staments of this article)
| |
| * James Oxley : [http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/oxley-matroids.pdf What is a matroid?]
| |
| | |
| [[Category:Matroid theory]]
| |
| [[Category:Dimension]]
| |
| [[Category:Closure operators]]
| |
| [[Category:Set families]]
| |
| | |
| [[ca:Matroide]]
| |
| [[cs:Matroid]]
| |
| [[de:Matroid]]
| |
| [[es:Matroide]]
| |
| [[fr:Matroïde]]
| |
| [[it:Matroide]]
| |
| [[he:מטרואיד]]
| |
| [[hu:Matroid]]
| |
| [[nl:Matroïde]]
| |
| [[ja:マトロイド]]
| |
| [[pl:Matroid]]
| |
| [[ru:Матроид]]
| |
| [[sk:Matroid]]
| |
| [[sr:Matroid]]
| |
| [[zh:拟阵]]
| |
