Difference between revisions of "Matroid"
(Importing text file) |
m (→References: isbn link) |
||
(18 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | + | {{TEX|done}} | |
− | + | {{MSC|05B}} | |
− | A matroid | + | 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==== | ====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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 [[ | + | 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 | + | 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 | + | 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 & 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"> | + | <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 & 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
Matroid. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matroid&oldid=14420