Matroid

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 subset 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, 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