Editing Matroid (section)

== Examples ==

=== Free matroid ===
Let <math>E</math> be a finite set. The set of all subsets of <math>E</math> defines the independent sets of a matroid. It is called the [[free matroid]] over <math>E</math>.

===Uniform matroids===
Let <math>E</math> be a finite set and <math>k</math> a [[natural number]]. One may define a matroid on <math>E</math> by taking every {{nobr|<math>k</math> element}} subset of <math>E</math> to be a basis. This is known as the ''[[uniform matroid]]'' of rank <math> k</math>. A uniform matroid with rank <math>k</math> and with <math>n</math> elements is denoted <math> U_{k,n}</math>. All uniform matroids of rank at least 2 are simple (see {{section link||Additional terms}}). The uniform matroid of rank&nbsp;2 on <math>n</math> points is called the <math>n</math>&nbsp;''point line''. A matroid is uniform if and only if it has no circuits of size less than one plus the rank of the matroid. The direct sums of uniform matroids are called [[partition matroid]]s.

In the uniform matroid <math> U_{0,n}</math>, every element is a loop (an element that does not belong to any independent set), and in the uniform matroid <math> U_{n,n}</math>, every element is a coloop (an element that belongs to all bases). The direct sum of matroids of these two types is a partition matroid in which every element is a loop or a coloop; it is called a ''discrete matroid''. An equivalent definition of a discrete matroid is a matroid in which every proper, non-empty subset of the ground set <math>E</math> is a separator.

===Matroids from linear algebra===
[[File:fano plane.svg|thumb|The Fano matroid, derived from the [[Fano plane]]. It is [[GF(2)]]-linear but not real-linear.]]
[[File:Vamos matroid.svg|thumb|The [[Vámos matroid]], not linear over any field]]
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. There are two ways to present the matroids defined in this way:
: If <math>E</math> is any finite subset of a [[vector space]] <math>V</math>, then we can define a matroid <math>M</math> on <math>E</math> by taking the independent sets of <math>M</math> to be the [[linear independence|linearly independent]] subsets of <math>E</math>.
The validity of the independent set axioms for this matroid follows from the [[Steinitz exchange lemma]].

: If <math>M</math> is a matroid that can be defined in this way, we say the set <math>E</math> ''[[matroid representation|represents]]'' <math>M</math>.

: Matroids of this kind are called ''vector matroids''.

An important example of a matroid defined in this way is the Fano matroid, a rank&nbsp;three matroid derived from the [[Fano plane]], a [[finite geometry]] with seven points (the seven elements of the matroid) and seven lines (the proper nontrivial flats of the matroid). It is a linear matroid whose elements may be described as the seven nonzero points in a three&nbsp;dimensional vector space over the [[finite field]] [[GF(2)]]. However, it is not possible to provide a similar representation for the Fano matroid using the [[real number]]s in place of GF(2).

A [[matrix (mathematics)|matrix]] <math>A</math> with entries in a [[field (mathematics)|field]] gives rise to a matroid <math>M</math> 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 <math>A</math>, and <math>A</math> is said to ''represent'' <math>M</math>.

For instance, the Fano matroid can be represented in this way as a 3&nbsp;&times;&nbsp;7 [[Logical matrix|(0,1)&nbsp;matrix]]. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation.{{efn|
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 <math>E</math> 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'' or ''linear''. If <math>M</math> is equivalent to a vector matroid over a [[field (mathematics)|field]] <math>F</math>, then we say <math>M</math> is ''representable over'' {{nobreak|<math>F</math>;}} in particular, <math>M</math> 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 characterize the matroids that may be represented over a given field <math>F</math>; [[Rota's conjecture]] describes a possible characterization for every [[finite field]].  The main results so far are characterizations of [[binary matroid]]s (those representable over GF(2)) due to [[W. T. Tutte|Tutte]] (1950s), of ternary matroids (representable over the 3&nbsp;element field) due to Reid and Bixby, and separately to [[Paul Seymour (mathematician)|Seymour]] (1970s), and of quaternary matroids (representable over the 4&nbsp;element field) due to {{harvp|Geelen|Gerards|Kapoor|2000}}. A proof of Rota's conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.<ref>{{cite journal|title=Solving Rota's conjecture|journal=Notices of the American Mathematical Society|url=http://www.ams.org/notices/201407/rnoti-p736.pdf|date=Aug 17, 2014|pages=736–743}}</ref>

A [[regular matroid]] is a matroid that is representable over all possible fields. The [[Vámos matroid]] is the simplest example of a matroid that is not representable over any field.

===Matroids from graph theory===
A second original source for the theory of matroids is [[graph theory]].

Every finite graph (or [[multigraph]]) <math>G</math> gives rise to a matroid <math>M(G)</math> as follows: take as <math>E</math> the set of all edges in <math>G</math> 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]]. Then <math>M(G)</math> is called a ''cycle matroid''. Matroids derived in this way are ''[[graphic matroid]]s''. Not every matroid is graphic, but all matroids on three elements are graphic.<ref name=Ox13/> 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 <math>G</math> let <math>E</math> and <math>F</math> be two distinguished sets of vertices.  In the set <math>E</math>, define a subset <math>U</math> to be independent if there are <math>|U|</math> vertex-disjoint paths from <math>F</math> onto <math>U</math>.  This defines a matroid on <math>E</math> called a ''[[gammoid]]'':<ref name=Ox115/> a ''strict gammoid'' is one for which the set <math>E</math> is the whole vertex set of <math>G</math>.<ref name=Ox100>{{harvp|Oxley|1992|p=100}}</ref>

*In a [[bipartite graph]] <math>G = (U,V,E)</math>, one may form a matroid in which the elements are vertices on one side <math>U</math> of the bipartition, and the independent subsets are sets of endpoints of [[Matching (graph theory)|matchings]] of the graph. This is called a ''transversal matroid'',<ref name=Ox4648>{{harvp|Oxley|1992|pp=46–48}}</ref><ref name=Wh877297>{{harvp|White|1987|pp=72–97}}</ref> and it is a special case of a gammoid.<ref name=Ox115>{{harvp|Oxley|1992|pp=115}}</ref>  The transversal matroids are the [[dual matroid]]s to the strict gammoids.<ref name=Ox100/>

*Graphic matroids have been generalized to matroids from [[signed graph]]s, [[gain graph]]s, and [[biased graph]]s.  A graph <math>G</math> with a distinguished linear class <math>B</math> of cycles, known as a "biased graph" <math>(G, B)</math>, 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 <math>G</math>. If no cycle is distinguished, the frame matroid is the bicircular matroid of <math>G</math>. 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&nbsp;dimensional [[rigidity matroid]], a matroid defined in the theory of [[structural rigidity]].

*Let <math>G</math> be a connected graph and <math>E</math> be its edge set. Let <math>I</math> be the collection of subsets <math>F</math> of <math>E</math> such that <math> G - F </math> is still connected. Then <math> M^*(G)</math>, whose element set is <math>E</math> and with <math>I</math> as its class of independent sets, is a matroid called the ''bond matroid'' of <math>G</math>.

: The rank function <math>r(F)</math> is the [[cyclomatic number]] of the subgraph induced on the edge subset <math>F</math>, which equals the number of edges outside a maximal forest of that subgraph, and also the number of independent cycles in it.

===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 <math>F</math> and <math>K</math> are fields with <math>K</math> containing <math>F</math>.  Let <math>E</math> be any finite subset of <math>K</math>.
: Define a subset <math>S</math> of <math>E</math> to be [[algebraic independence|algebraically independent]] if the extension field <math>F(S)</math> has [[transcendence degree]] equal to <math>|S|</math>.<ref name=Ox215>{{harvp|Oxley|1992|p=215}}</ref>

A matroid that is equivalent to a matroid of this kind is called an [[algebraic matroid]].<ref name=Ox216>{{harvp|Oxley|1992|p=216}}</ref>  The problem of characterizing algebraic matroids is extremely difficult; little is known about it. The [[Vámos matroid]] provides an example of a matroid that is not algebraic.