Namespaces
Variants
Actions

Difference between revisions of "Matroid"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: isbn link)
 
(18 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A combinatorial abstraction of a linear algebra. A matroid is specified by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628701.png" /> of elements and a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628702.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628703.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628704.png" />, all the independent subsets of the matroid which are contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628705.png" /> and are maximal with respect to inclusion relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628706.png" /> have the same number of elements.
+
{{TEX|done}}
  
Examples. 1) The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628707.png" /> of rows of an arbitrary rectangular matrix and the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628708.png" /> of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m0628709.png" /> consisting of linearly independent rows form a matroid. 2) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287010.png" /> be the set of all skeleton forests (see [[Tree|Tree]]) of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287011.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287012.png" /> be the set of edges of the forest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287014.png" />. Then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287015.png" /> of edges of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287016.png" /> and the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287017.png" /> form a matroid. 3) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287018.png" /> be a bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]) with parts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287019.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287020.png" /> of vertices for which there is a matching <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287021.png" /> of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287022.png" /> such that every vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287023.png" /> is incident to some edge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287024.png" /> is called a partial transversal. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287025.png" /> and the set of all transversals of the graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287026.png" /> form a so-called transversal matroid.
+
{{MSC|05B}}
  
A matroid can be also specified by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287027.png" /> of elements and a family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287028.png" /> of non-empty subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287029.png" />, called circuits, which satisfy the following axioms: no proper subset of a circuit is a circuit; and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287030.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287031.png" /> contains a circuit. The independent subsets of this matroid are the subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287032.png" /> that do not contain circuits.
+
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.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287033.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287034.png" />, 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.
+
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.
  
====References====
+
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.
<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</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</TD></TR></table>
 
  
 +
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====
 
====Comments====
 
The example of the matroid consisting of the rows of a (rectangular) matrix gave rise to the name.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287035.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287036.png" /> the third independence axiom (given the other 2) is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287037.png" />) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287039.png" />, then there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287040.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287041.png" />.
+
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287042.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287043.png" /> is called the rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287044.png" />. Given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287045.png" />, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287046.png" /> is called the closure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287047.png" />; one calls <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287048.png" /> closed if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287049.png" />. A maximal (proper) closed subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287050.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287051.png" /> is called a hyperplane.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287052.png" /> the  "basis axiomatization"  is as follows. A non-empty collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287053.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287054.png" /> is the set of bases of a matroid if and only if for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287056.png" /> there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287057.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287058.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287059.png" /> is a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287060.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287061.png" /> to subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287062.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287064.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287065.png" />. Such a closure operation defines a matroid if for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287068.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287069.png" /> (the exchange axiom). The corresponding independent subsets are defined by: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287070.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287071.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287072.png" />, there is a dual matroid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287073.png" />, which is most simply defined in terms of bases as follows: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287074.png" /> is the set of all bases of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287075.png" />, then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287076.png" /> is the set of bases of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287077.png" />. The duality theory has important applications; as a striking example, one could mention the following result of H. Whitney: A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287078.png" /> with associated graphic matroid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287079.png" /> (determined by the circuits, respectively forests, of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287080.png" /> as above) is planar if and only if the dual matroid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287081.png" /> is also graphic.
+
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|Combinatorial geometry]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287082.png" /> be a set system satisfying conditions 1) and 2) above and consider a weighting on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287083.png" />, i.e. a mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287084.png" /> into the real numbers satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287085.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287086.png" />. One extends <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287087.png" /> to the power set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287088.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287089.png" /> for each subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287090.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287091.png" />. It is required to find a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287092.png" /> of maximal weight (among all subsets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287093.png" />). Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287094.png" /> is a matroid if and only if the greedy algorithm solves this problem for every weighting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287095.png" />: One orders the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287096.png" /> according to weight, say <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287097.png" /> and determines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287098.png" /> (starting from the empty set) recursively as follows: In step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m06287099.png" />, the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m062870100.png" /> is added to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m062870101.png" /> unless this results in a set no longer contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m062870102.png" />. Due to this algorithmic property, matroids are an extremely important tool in combinatorial optimization.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m062/m062870/m062870103.png" />-adic curves, and in many other areas.
+
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.
 
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.
Line 38: Line 43:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.J.A. Welsh,  "Matroid theory" , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.L. Lawler,  "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston  (1976)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C.H. Papadimitriou,  K. Steiglitz,  "Combinatorial optimization. Algorithms and complexity" , Prentice-Hall  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  N. White (ed.) , ''Theory of matroids'' , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  N. White (ed.) , ''Combinatorial geometries'' , Cambridge Univ. Press  (1987)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  N. 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)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.P.S. Kung,  "A source book in matroid theory" , Birkhäuser  (1986)</TD></TR></table>
+
<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}}

Latest revision as of 20:24, 20 November 2023


2020 Mathematics Subject Classification: Primary: 05B [MSN][ZBL]

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) 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 of matchings.

References

[1] H. Whitney, "On the abstract properties of linear dependence" Amer. J. Math. , 57 (1935) pp. 509–533 DOI 10.2307/2371182 Zbl 0012.00404
[2] W.T. Tutte, "Lectures on matroids" J. Res. Nat. Bur. Standards Sec. B , 69 : 1–2 (1965) pp. 1–47 Zbl 0151.33801

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. [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 [1] (also included in [a8]).

References

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

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
How to Cite This Entry:
Matroid. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matroid&oldid=14420
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article