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 is a mapping of subsets of to subsets of such that , , . Such a closure operation defines a matroid if for all , , one has (the exchange axiom). The corresponding independent subsets are defined by: if and only if .

Given any matroid , there is a dual matroid , which is most simply defined in terms of bases as follows: If is the set of all bases of , then the set is the set of bases of . The duality theory has important applications; as a striking example, one could mention the following result of H. Whitney: A graph with associated graphic matroid (determined by the circuits, respectively forests, of as above) is planar if and only if the dual matroid 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