View source for Matroid

{{TEX|done}}

{{MSC|05B}}

A combinatorial abstraction of a linear algebra. A matroid is specified by a set $V$ of elements and a family $\mathcal{E} = \{E_1,E_2,\ldots \}$ of subsets of $V$, called independent subsets, which satisfy the following axioms: 1) the empty set is independent; 2) any subset of an independent set is independent; 3) for every subset $A \subseteq V$, all the independent subsets of the matroid which are contained in $A$ and are maximal with respect to inclusion relative to $A$ have the same number of elements.

Examples. 1) The set $V$ of rows of an arbitrary rectangular matrix and the family $\mathcal{E}$ of all subsets of $V$ consisting of linearly independent rows form a matroid. 2) Let $\mathcal{L} = \{L_1,L_2,\ldots\}$ be the set of all skeleton forests (see [[Tree]]) of a graph $G$, and let $R(L_i)$ be the set of edges of the forest $L_i$, $i=1,2,\ldots$. Then the set $V$ of edges of the graph $G$ and the family $\mathcal{E} = \{R(L_i) : i=1,2,\ldots\}$ form a matroid. 3) Let $G$ be a bipartite graph (cf. [[Graph, bipartite]]) with parts $W', W''$. A subset $V \subseteq W'$ of vertices for which there is a matching $P$ of the graph $G$ such that every vertex $v \in V$ is incident to some edge of $P$ is called a partial transversal. The set $W'$ and the set of all transversals of the graph $G$ form a so-called transversal matroid.

A matroid can be also specified by a set $V$ of elements and a family $\mathcal{C} = \{C_1,C_2,\ldots\}$ of non-empty subsets $C_i \subseteq V$, called circuits, which satisfy the following axioms: no proper subset of a circuit is a circuit; and if $v \in C_i \cap C_j$, then $C_i \cup C_j \setminus \{ v \}$ contains a circuit. The independent subsets of this matroid are the subsets $E \subseteq V$ that do not contain circuits.

If $G$ is a graph, then the set of its edges and the family of its simple circuits form what is called a graphic matroid. If for the circuits of a matroid one takes the cocycles (cuts, cf. [[Graph, connectivity of a|Graph, connectivity of a]]) of the graph $G$, the resulting matroid is called a cographic matroid. The matroids of the last two types are also termed cyclic and cocyclic. The notion of a  "matroid"  is used in graph theory and combinatorics in the proof of some assertions on [[Covering and packing|covering and packing]] of matchings.

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  H. Whitney,   "On the abstract properties of linear dependence"  ''Amer. J. Math.'' , '''57'''  (1935)  pp. 509–533 {{DOI|10.2307/2371182}} {{ZBL|0012.00404}}</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  W.T. Tutte,   "Lectures on matroids"  ''J. Res. Nat. Bur. Standards Sec. B'' , '''69''' :  1–2  (1965)  pp. 1–47 {{ZBL|0151.33801}}</TD></TR>
</table>

====Comments====
The example of the matroid consisting of the rows of a (rectangular) matrix gave rise to the name.

In matroid theory, most often the underlying set $V$ is supposed to be finite. And, in fact, it is not particularly clear what the right definitions are in the infinite case (cf. [[#References|[a1]]], Chapt. 20). For a finite $V$ the third independence axiom (given the other 2) is equivalent to $3')$ If $E_1, E_2 \in \mathcal{E}$ and $|E_1| \ge |E_2|+1$, then there is a $v \in E_1 \setminus E_2$ such that $E_2 \cup \{x\}$ \in $\mathcal{E}$.

There are many axiom systems for matroids. In addition to those based on the ideas of independent subsets and circuits there are axiom systems based on the idea of a rank function, the idea of a basis, the idea of a hyperplane, or the idea of a closure operation.

A maximal independent set is called a ''basis'' (and a minimal dependent set is called a ''circuit'' or ''cycle'' of the matroid). The maximal cardinality of an independent set contained in a subset $A$ of $V$ is called the ''rank'' $\rho(A)$. Given $A$, the set $\sigma A = \{ x \in V : \rho(A \cup\{x\}) = \rho(A) \}$ is called the ''closure'' of $A$; one calls $A$ closed if and only if $\sigma A = A$. A maximal (proper) closed subset $A$ of $V$ is called a ''hyperplane''.

For a finite $V$ the  "basis axiomatization"  is as follows. A non-empty collection $\mathcal{B}$ of subsets of $V$ is the set of bases of a matroid if and only if for all $B_1,B_2 \in \mathcal{B}$ and $x \in B_1 \setminus B_2$ there is a $y \in B_2 \setminus B_1$ such that $B_1 \setminus \{x\} \cup \{y\} \in \mathcal{B}$.

A closure operation on a set $V$ is a mapping $A \mapsto \sigma A$ of subsets of $V$ to subsets of $V$ such that $A \subseteq \sigma A$, $\sigma\sigma A = \sigma A$ and $A \subseteq B \Rightarrow \sigma A \subseteq \sigma B$. Such a closure operation defines a matroid if for all $A \subset V$, $p,q \in V$, $p \not\in \sigma A$ one has $p \in \sigma(A \cup \{q\}) \Rightarrow q \in \sigma(A \cup {p})$ (the exchange axiom). The corresponding independent subsets are defined by: $A \in \mathcal{E}$ if and only if $x \in A \Rightarrow x \not\in \sigma(A \setminus \{x\})$.

Given any matroid $M = (V,\mathcal{E})$, there is a dual matroid $M^*$, which is most simply defined in terms of bases as follows: If $\mathcal{B}$ is the set of all bases of $M$, then the set $\{ V \setminus B : B \in \mathcal{B} \}$ is the set of bases of $M^*$. The duality theory has important applications; as a striking example, one could mention the following result of H. Whitney: A graph $G$ with associated graphic matroid $M_G$ (determined by the circuits, respectively forests, of $G$ as above) is planar if and only if the dual matroid $M_G^*$ is also graphic.

Matroids are also studied from a more geometric point of view, under the name  "combinatorial geometries"  (cf. also [[Combinatorial geometry]]).

Finally, it is also possible to define matroids in an algorithmic way. Let $M = (V,\mathcal{E})$ be a set system satisfying conditions 1) and 2) above and consider a weighting on $M$, i.e. a mapping $w:V \rightarrow \mathbb{R}$ into the real numbers satisfying $w(v) > 0$ for all $v \in V$. One extends $w$ to the power set of $V$ by linearity, putting $w(A) = \sum_{v \in A} w(v)$ for each subset $A$ of $V$. It is required to find a subset $E \in \mathcal{E}$ of maximal weight (among all subsets in $\mathcal{E}$). Then $M$ is a matroid if and only if the [[greedy algorithm]] solves this problem for every weighting $w$: One orders the elements of $V$ according to weight, say $w(v_1) \ge w(v_2) \ge \cdots$ and determines $E$ (starting from the empty set) recursively as follows: In step $i$, the element $v_i$ is added to $E$ unless this results in a set no longer contained in $\mathcal{E}$. Due to this algorithmic property, matroids are an extremely important tool in combinatorial optimization.

Matroids are also used in the stratification of Grassmann manifolds, in the analysis of higher-dimensional splines and $p$-adic curves, and in many other areas.

An important related concept is that of an oriented matroid, which is an abstraction of a linear algebra over an ordered field, and is used in the study of convex polytopes.

The seminal paper that started the whole theory of matroids is [[#References|[1]]] (also included in [[#References|[a8]]]).

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  D.J.A. Welsh,   "Matroid theory" , Acad. Press  (1976) {{ISBN|0-12-744050-X}}; reprinted (Courier Dover Publications, 2010) {{ISBN|9780486474397}} {{ZBL|0343.05002}}</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  E.L. Lawler,   "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston  (1976) {{ZBL|0413.90040}}</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  C.H. Papadimitriou,   K. Steiglitz,   "Combinatorial optimization. Algorithms and complexity" , Prentice-Hall  (1982) {{ZBL|0503.90060}}</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  Neil White (ed.) , ''Theory of matroids'' , Encyclopedia of Mathematics and Its Applications '''26'''.  Cambridge Univ. Press  (1986) {{ISBN|9780521309370}} {{ZBL|0579.00001}}</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  Neil White (ed.) , ''Combinatorial geometries'', Encyclopedia of Mathematics and its Applications '''29'''.  Cambridge Univ. Press  (1987) {{ISBN|0-521-33339-3}}, {{ZBL|0626.00007}}</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  Neil White (ed.) , ''Combinatorial geometries: Advanced theory'' , Cambridge Univ. Press  (1986)</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  M. Aigner,   "Kombinatorik II. Matroide und Transversaltheorie" , Springer  (1976) {{ZBL|0373.05002}} </TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  J.P.S. Kung,   "A source book in matroid theory" , Birkhäuser  (1986) {{ISBN|0-8176-3173-9}} {{ZBL|0597.05019}} </TD></TR>
<TR><TD valign="top">[a9]</TD> <TD valign="top">Oxley, James G. ''Matroid theory''. Oxford Science  Publications.  Oxford: Oxford University Press (1992). {{ISBN|0-19-853563-5}}, {{ZBL|0784.05002}}</TD></TR>
</table>

===Greedoid===
A generalisation of the concept of matroid.  A greedoid on a set  $V$ is a set system $\mathcal{F}$ of subsets of $V$, called "feasible" sets, with the properties: 1) the empty set is feasible, $\emptyset \in \mathcal{F}$; 
2) if $F \in \mathcal{F}$ is non-empty, then there is $x \in F$ such that $F \setminus \{x\} \in \mathcal{F}$; 3) if $X, Y \in \mathcal{F}$ with $|X| > |Y|$ then there is $x \in X$ such that $Y \cup \{x\} \in \mathcal{F}$.

Axiom (3), the exchange property, implies that all maximal feasible sets have the same number of elements: this is the ''rank'' of the greedoid.  The ''greedoid language'' attached to $\mathcal{F}$ is the set $\mathcal{L}$ of words (ordered sequences of distinct elements) over $A$, with $(a_1,a_2,\ldots,a_k) \in \mathcal{L}$ iff each of $\{a_1\}, \{a_1,a_2\}, \ldots, \{a_1,\ldots,a_k\} \in \mathcal{F}$.  

The independent sets of a matroid form a greedoid, and the feasible sets of a greedoid form a matroid if they are hereditary, that is, axiom (2) holds in the strong form that for every $x \in F$, $F \setminus \{x\} \in \mathcal{F}$.

An ''antimatroid'' is a greedoid with the property that if $A \subset B$ are feasible, $x \not\in B$, and $A \cup \{x\}$ is feasible, then $B \cup \{x\}$ is feasible.  

====References====
* Björner, Anders; Ziegler, Günter M. "Introduction to greedoids", ''Matroid applications'', ed Neil White, Encycl. Math. Appl. '''40''', Cambridge University Press (1992) 284-357. {{ISBN|0-521-38165-7}} {{ZBL|0772.05026}}