Matroid

A matroid ( n. ) Is a mathematical structure that is used to generalize the notion of independence from linear algebra . It represents a special case of the more general independence systems . Matroids have applications in many areas of combinatorics , in particular combinatorial optimization , as well as graph theory .

terminology

Hassler Whitney used the term matroid in his seminal article in 1935. As the word suggests, he conceived a matroid as an abstract generalization of a matrix , with the Greek suffix -oid completing the term. Much of the language of this theory is based on linear algebra. However, Whitney's approach is also based on his work in graph theory, which means that Matroid terminology is also shaped by graph theory. However, the terminology varies from author to author. Even the term matroid is rejected by some. Leonid Mirsky and Hazel Perfect use the expression “independence space”, Henry H. Crapo and Gian-Carlo Rota in their monograph on combinatorial geometry “pregeometry”, Richard Rado “independence functions “(Eng. Ie independence functions) and Paul Cohn “ transitive dependence relation ”(Eng. I. E. Transitive dependency relation). According to Martin Aigner , the term matroid emphasizes the set- theoretical point of view more strongly, while embossing geometry is mainly used by those authors who put the geometric aspect in the foreground.

Historical view

The mathematician Hassler Whitney , who introduced the term matroid

The mathematical structure of a matroid was introduced and further developed by several authors in the 1930s. The aim was to axiomatize well-known terms from linear algebra such as linear dependency , basis and product and to transfer them to more general structural classes. This enables a more precise concept formation in different areas of combinatorics and makes purely combinatorial questions accessible to algebraic ideas and methods. For example, graph theory can be included in the theory of matroids.

As a rule, the beginning of the matroid theory is attributed to the American mathematician Hassler Whitney. In 1935 he investigated matrix matroids in which the elements of are the rows of a given matrix, and a set of rows is independent if the rows are linearly independent in the usual sense. A little later, Bartel Leendert van der Waerden also used the concept of abstract dependency in his book "Modern Algebra". Separately , the Japanese mathematician Takeo Nakasawa wrote four articles between 1935 and 1938 that made him a co-founder of the matroid theory, even if these were long forgotten. ${\displaystyle M=(S,I)}$ ${\displaystyle S}$

In addition, there were isolated articles by Garrett Birkhoff (1935), Saunders Mac Lane (1936) and Robert P. Dilworth (1941–1944) on association -theoretical and geometric aspects of matroid theory. Richard Rado dealt with combinatorial applications of matroids (1942) and infinite matroids (1949). An important impetus for the further development of the theory of matroids was the alternating adoption of ideas from different areas and their effects in others, such as the parallelism between the properties of the dimension in vector spaces and the rank in graphs . In 1958 and 1959, William Thomas Tutte published basic articles on matroids and graphs. Since then, interest in matroids and their applications in combinatorics has increased steadily, not least in the area of combinatorial optimization . Jack Edmonds and Delbert Ray Fulkerson (1965) as well as Leonid Mirsky and Hazel Perfect (1967) independently discovered a new class of matroids, so-called transversal matroids. According to Welsh, matroids have so far achieved the greatest effect in transversal theory (measured in terms of new results that have been achieved and simpler proofs that have been found for already known results).

Introductory examples

Example of a vector matroid

The basic set E is given with the vectors a, b, c, d, e, f. The sets with the zero vector f and the sets that contain the vectors d and e together are linearly dependent.

Let be a field , a - vector space and a finite subset . Let be defined as the set of subsets of which are linearly independent over . Then the pair is a matroid called a vector matroid. ${\displaystyle L}$ ${\displaystyle V}$ ${\displaystyle L}$ ${\displaystyle E\subseteq V}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle L}$ ${\displaystyle M=(E,{\mathcal {I}})}$

For example, let the vector space and the columns of the following matrix be given as the basic set : ${\displaystyle \mathbb {R} }$ ${\displaystyle V=\mathbb {R} ^{3}}$ ${\displaystyle E}$

${\displaystyle A:={\begin{pmatrix}1&0&0&0&0&0\\0&1&0&{\frac {1}{2}}&1&0\\0&0&1&{\frac {1}{2}}&1&0\end{pmatrix}}}$

The corresponding column vectors are denoted as follows:

${\displaystyle a:={\begin{pmatrix}1\\0\\0\end{pmatrix}},b:={\begin{pmatrix}0\\1\\0\end{pmatrix}},c:={\begin{pmatrix}0\\0\\1\end{pmatrix}},d:={\begin{pmatrix}0\\{\frac {1}{2}}\\{\frac {1}{2}}\end{pmatrix}},e:={\begin{pmatrix}0\\1\\1\end{pmatrix}},f:={\begin{pmatrix}0\\0\\0\end{pmatrix}}}$

This results in the basic amount and the amount ${\displaystyle E=\{a,b,c,d,e,f\}}$

${\displaystyle {\mathcal {I}}=\{\emptyset ,\{a\},\{b\},\{c\},\{d\},\{e\},\{a,b\},\{a,c\},\{a,d\},\{a,e\},\{b,c\},\{b,d\},\{b,e\},\{c,d\},\{c,e\},\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\}\}\subseteq {\mathcal {P}}(E)}$

of the vector sets with linearly independent vectors.

In contrast, the vectors in vector space are linearly dependent if one of the following conditions is met: ${\displaystyle V}$

• It is a one-element set that contains exactly the zero vector. In the example above, this would be the vector . ${\displaystyle f}$
• Two or more vectors are scalar multiples of each other. In the example these are sets with the vectors and and all sets that contain the vector . ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle f}$

Correspondingly, a zero column and scalar multiples or their indices are dependent in a matroid.

For a matroid the bases are defined as the elements of maximal inclusion of . For a vector matroid these are exactly the bases of the vector space . In this example, the following applies: ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle M=(E,{\mathcal {I}})}$

${\displaystyle {\mathcal {B}}=\{\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\}\}}$.

Example of a graphical matroid

Let be an undirected multigraph (i.e. multiple edges and loops are possible) with node set and edge set . The graphical matroid contains as independent sets the circle-free subgraphs of . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle M=(E,{\mathcal {I}})}$ ${\displaystyle G}$

As an example, the graph is the vertex set and the edge set , keeping the edges by the following multi-sets are defined . ${\displaystyle G=(V,E)}$ ${\displaystyle V=\{1,2,3,4\}}$ ${\displaystyle E=\{a,b,c,d,e,f\}}$ ${\displaystyle a=\{1,2\},b=\{2,3\},c=\{2,4\},d=\{3,4\},e=\{3,4\},f=\{1,1\}}$

In this example, the circular subgraphs correspond to independent sets . ${\displaystyle {\mathcal {I}}=\{\emptyset ,\{a\},\{b\},\{c\},\{d\},\{e\},\{a,b\},\{a,c\},\{a,d\},\{a,e\},\{b,c\},\{b,d\},\{b,e\},\{c,d\},\{c,e\},\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\}\}\subseteq {\mathcal {P}}(E)}$

The bases of a graphical matrix correspond to the spanning forests of the graph (or the spanning trees in the case of connected graphs). The following applies to the example: ${\displaystyle {\mathcal {B}}}$

${\displaystyle {\mathcal {B}}=\{\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\}\}}$.

Axiomatization

There is no standard axiom system in matroid theory . Whitney already noted in the basic article that different structures in the matroids offer themselves for axiomatization . Since one structure implies the other, a matroid can be defined in many different equivalent ways. The axioms of independence are more motivated by linear algebra, while the axioms of circles are more based on a graph-theoretical approach. Birkhoff introduced the term cryptomorphism for such an equivalence of different axiomatizations . This is to say that two axiomatizations are "isomorphic" in a non-obvious or even cryptic way.

Axioms of independence

A matroid is an ordered pair consisting of a finite set , called a basic set, and a set of subsets ( set system ), called independent sets, which satisfies the following axioms: ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {I}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}\subseteq {\mathcal {P}}(E)}$

(I1) . ${\displaystyle \emptyset \in {\mathcal {I}}}$

(I2) If and , then is . ${\displaystyle I\in {\mathcal {I}}}$ ${\displaystyle I'\subseteq I}$ ${\displaystyle I'\in {\mathcal {I}}}$

(I3) If and in are and , then there is an element of , so that ${\displaystyle I_{1}}$ ${\displaystyle I_{2}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \left|I_{1}\right|<\left|I_{2}\right|}$ ${\displaystyle e}$ ${\displaystyle I_{2}-I_{1}}$ ${\displaystyle I_{1}\cup \{e\}\in {\mathcal {I}}.}$

It is the cardinality of the set and means the difference of the sets and . Often one also writes for and for , especially when several matroids are taken into account. The amounts from are called dependent. ${\displaystyle \left|I_{1}\right|}$ ${\displaystyle I_{1}}$ ${\displaystyle I_{2}-I_{1}}$ ${\displaystyle I_{2}}$ ${\displaystyle I_{1}}$ ${\displaystyle {\mathcal {I}}(M)}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle E(M)}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {P}}(E)-{\mathcal {I}}}$

The first axiom says that the empty set is independent. According to the second axiom, every subset of an independent set is also independent. It is also said in this regard that the set system is hereditary or hereditary. The unique selling point of a matroid compared to a normal independence system is the exchange property, i.e. the third condition. While the first two axioms can easily be understood as demands the existence of at least one independent set and the closure of the system with regard to inclusion , the motivation for the exchange property is less obvious. ${\displaystyle {\mathcal {I}}}$

This can be illustrated as follows: By applying the exchange property, points of an independent set can be added to a (smaller) independent set . Therefore it is also called the magnification feature (of English. Augmentation property ). We know from the quantity generated in this way that it is also independent again. It now contains elements of the set , but compared to this, the remaining points contained have been replaced by elements from . This in turn justifies the name exchange property . ${\displaystyle I_{2}}$ ${\displaystyle I_{1}}$ ${\displaystyle I_{1}}$ ${\displaystyle I_{2}-I_{1}}$

Basic axioms

A basis is a maximum element of the system of amounts with regard to the amount inclusion . A matroid can be specified more efficiently by a set of all maximally independent sets than by listing all independent sets. ${\displaystyle \subseteq }$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle M}$

For a basic set and a set of bases, the ordered pair is a matroid if the following axioms are satisfied: ${\displaystyle E}$ ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {P}}(E)}$ ${\displaystyle (E,{\mathcal {B}})}$

(B1) ${\displaystyle {\mathcal {B}}\neq \emptyset }$

(B2) For bases and from and each there is a such that . ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle x\in B_{1}-B_{2}}$ ${\displaystyle y\in B_{2}-B_{1}}$ ${\displaystyle (B_{1}-\{x\})\cup \{y\}\in {\mathcal {B}}}$

Condition (B2) is also called Steinitz's generalized exchange theorem. Given the bases of a matroid, the independent sets can be derived as the set of all subsets of bases . ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {B}}}$

Two bases of a matroid always have the same cardinality: If and are bases of a matroid , then applies . ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle M}$ ${\displaystyle |B_{1}|=|B_{2}|}$

Proof: Suppose that . Since and are both independent in , (I3) implies that there is an element out such that . This contradicts the maximality of , so . In the same way it can be shown and it follows ${\displaystyle |B_{1}|<|B_{2}|}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle M}$ ${\displaystyle e}$ ${\displaystyle B_{2}-B_{1}}$ ${\displaystyle B_{1}\cup \{e\}\in {\mathcal {I}}}$ ${\displaystyle B_{1}}$ ${\displaystyle |B_{1}|\geq |B_{2}|}$ ${\displaystyle |B_{2}|\geq |B_{1}|}$ ${\displaystyle |B_{1}|=|B_{2}|}$

Circle axioms

Axiom C3: The union of (red) and (green) contains a circle that does not contain a common edge (red-green dashed). ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{3}}$ ${\displaystyle e}$

A minimum dependent subset of any matroid is called a circle. The set of circles is denoted by or . So a circle is not independent, but every proper subset of is independent. A circle with n elements is also called an n-circle. Obviously, from be determined and vice versa from . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}(M)}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {I}}(M)}$ ${\displaystyle {\mathcal {C}}(M)}$ ${\displaystyle {\mathcal {C}}(M)}$ ${\displaystyle {\mathcal {I}}(M)}$

For a basic set and a set of circles, the ordered pair is a matroid if the following axioms are satisfied: ${\displaystyle E}$ ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {P}}(E)}$ ${\displaystyle (E,{\mathcal {C}})}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {C}}}$

(C1) . ${\displaystyle \emptyset \notin {\mathcal {C}}}$

(C2) If and , then it follows . ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ ${\displaystyle C_{1}\subseteq C_{2}}$ ${\displaystyle C_{1}=C_{2}}$

(C3) For everyone with and there , so . ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ ${\displaystyle C_{1}\neq C_{2}}$ ${\displaystyle e\in C_{1}\cap C_{2}}$ ${\displaystyle C_{3}\in {\mathcal {C}}}$ ${\displaystyle C_{3}\subseteq (C_{1}\cup C_{2})-\{e\}}$

The minimally dependent subsets of a matroid always form a circle system. This becomes particularly clear in graphical matroids, since there the elements contain the circles of the underlying graph, from which the name comes. The property (C3) is also called the (weak) axiom of circle elimination : For every two different circles and and one element from the intersection of these two circles, there is a third circle , which is contained in the two circles and and the selected element from the intersection avoids. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle e}$ ${\displaystyle C_{3}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle e}$

Axioms of the rank function

Be a matroid and . Now be defined as . The couple are again a matroid. This is called a restriction of on and is marked with or . It is also said that it is deleted. ${\displaystyle M=(E,{\mathcal {I}})}$ ${\displaystyle X\subseteq E}$ ${\displaystyle {\mathcal {I}}|X}$ ${\displaystyle \{I\subseteq X:I\in {\mathcal {I}}\}}$ ${\displaystyle (X,{\mathcal {I}}|X)}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M|X}$ ${\displaystyle M\backslash (E-X)}$ ${\displaystyle E-X}$ ${\displaystyle M}$

For a matroid , its rank function is defined as ${\displaystyle M=(E,{\mathcal {I}})}$ ${\displaystyle r:{\mathcal {P}}(E)\to \mathbb {N} _{0}}$

${\displaystyle X\mapsto r(X):=|B_{X}|}$for a . ${\displaystyle B_{X}\in {\mathcal {B}}({\mathcal {I}}|X)}$

So the rank of a matroid is the cardinality of a (and therefore every) base of . It is supposed to describe a kind of "dimension" of a matroid. The rank of a subset of a matroid corresponds to the cardinality of one (and thus all) maximally independent elements of the restriction of on . Note that a restriction is always created by deleting the subset from the basic set . ${\displaystyle M}$ ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle X\subseteq E}$ ${\displaystyle M=(E,{\mathcal {I}})}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M|X}$ ${\displaystyle T=(E-X)}$ ${\displaystyle E}$

With the help of rank functions, another equivalent axiom system for matroids can now be developed. Let it be a matroid and its rank function, then: ${\displaystyle M=(E,{\mathcal {I}})}$ ${\displaystyle r:{\mathcal {P}}(E)\to \mathbb {N} _{0}}$

(R1) If , then . ${\displaystyle X\subseteq E}$ ${\displaystyle 0\leq r(X)\leq |X|}$

(R2) If , then . ${\displaystyle X\subseteq Y\subseteq E}$ ${\displaystyle r(X)\leq r(Y)}$

(R3) for all valid: . ${\displaystyle X,Y\in E}$ ${\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)}$

The rank function is thus non-negative and subcardinal (R1), monotonic (R2) and submodular (R3). The last property is also reminiscent of the dimensional formula from linear algebra. ${\displaystyle r}$

Independent sets, bases and circles can be characterized relatively easily by the rank function. Be a ranked matroid and be . Then applies ${\displaystyle M}$ ${\displaystyle r}$ ${\displaystyle X\subseteq E(M)}$

• ${\displaystyle X}$is independent if and only if ; ${\displaystyle |X|=r(X)}$
• ${\displaystyle X}$is a basis if and only if ; and ${\displaystyle |X|=r(X)=r(M)}$
• ${\displaystyle X}$is a circle if and only if not empty and for all in true . ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle r(X-x)=|X|-1=r(X)}$

Axioms of the Hull Operator

The linear envelope of a subset of a vector space over a body is the set of all linear combinations with vectors out with scalars out . The linear envelope forms a sub-vector space , which is also the smallest sub-vector space that it contains. Is z. B. given the set of vectors of the vector space , then all vectors of the sub-vector space have an invariant effect with respect to the dimension . The dimension is therefore not increased by these vectors. ${\displaystyle \langle A\rangle }$ ${\displaystyle A}$ ${\displaystyle V}$ ${\displaystyle K}$ ${\displaystyle A}$ ${\displaystyle K}$ ${\displaystyle A}$ ${\displaystyle \{a_{1},\dots ,a_{k}\}}$ ${\displaystyle V}$ ${\displaystyle \langle a_{1},\dots ,a_{k}\rangle }$ ${\displaystyle \operatorname {dim} (A)}$

The envelope operator (also known as the closing operator) is used to mark those elements of a matroid that do not change the rank compared to a subset after adding one of the elements: ${\displaystyle cl:{\mathcal {P}}(E)\to {\mathcal {P}}(E)}$ ${\displaystyle x\in E}$ ${\displaystyle M}$ ${\displaystyle X\subseteq E}$

${\displaystyle cl(X)=\{x\in E:r(X\cup x)=r(X)\}}$

The envelope operator of a matroid on a base set now has the following properties: ${\displaystyle M}$ ${\displaystyle E}$

(CL1) If , then . ${\displaystyle X\subseteq E}$ ${\displaystyle X\subseteq cl(X)}$

(CL2) If , then . ${\displaystyle X\subseteq Y\subseteq E}$ ${\displaystyle cl(X)\subseteq cl(Y)}$

(CL3) If , then . ${\displaystyle X\subseteq E}$ ${\displaystyle cl(cl(X))=cl(X)}$

(CL4) If , and , then . ${\displaystyle X\subseteq E}$ ${\displaystyle x\in E}$ ${\displaystyle y\in cl(X\cup x)-cl(X)}$ ${\displaystyle x\in cl(X\cup y)}$

Greedy algorithms

A weighted matroid is a matroid with a weight function . Greedy algorithms always calculate bases with minimum or maximum weight for these matroids . One example is Kruskal's algorithm for calculating a minimal forest spanning an edge-weighted graph . ${\displaystyle w\colon E\to \mathbb {R} ^{+}}$

Conversely, an independence system is a matroid if and only if a greedy algorithm can always calculate bases with minimum / maximum weight for every weight function.

Matroids and Hyperplanes

An important connection between matroid theory and geometry and above all between matroids and finite geometric structures can be found in the concept of the hyperplane . Here, within a matroid above the basic set as a hyperplane, a real subset of closed under the associated envelope operator is designated , which is maximal with regard to this property . ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle s}$ ${\displaystyle E}$

A hyperplane of is characterized by two properties: ${\displaystyle H}$ ${\displaystyle M}$

1. ${\displaystyle s(H)=H\subsetneqq E}$
2. ${\displaystyle \forall x\in {E\setminus H}\colon s(H\cup \{x\})=E}$

In the case of matroids of finite rank , whose base sets all have the same finite cardinality , there is also a further description of the hyperplanes , which makes the connection with the hyperplane concept of geometry obvious. According to this, a hyperplane of a matroid can be characterized as a maximum subset of the rank . Because of this connection, the term copoint is also used in addition to hyperplane . ${\displaystyle B\in {\mathcal {B}}}$ ${\displaystyle \rho }$ ${\displaystyle H}$ ${\displaystyle M}$ ${\displaystyle H\subsetneqq E}$ ${\displaystyle r(H)=\rho -1}$

The hyper-levels of a matroid clearly define its structure, since they are linked to the circles of the dual matroid in a reversible manner by forming a complement . In this way one finds that matroid structures can also be determined by hyperplane systems , i.e. by systems of subsets that satisfy the following hyperplane axioms. ${\displaystyle M^{*}}$

Hyperplane axioms

A subset system forms the system of hyperplanes of a matroid over the basic set if and only if it satisfies the following conditions: ${\displaystyle {\mathcal {H}}\subset {\mathcal {P}}(E)}$ ${\displaystyle E}$

(H1) ${\displaystyle E\notin {\mathcal {H}}}$

(H2) ${\displaystyle \forall H_{1};H_{2}\in {\mathcal {H}}\colon (H_{1}\neq H_{2})\Rightarrow (H_{1}\nsubseteq H_{2})}$

(H3) ${\displaystyle \forall H_{1};H_{2}\in {\mathcal {H}}\,\forall x\in E\setminus (H_{1}\cup H_{2})\colon \exists H_{3}\in {\mathcal {H}}\colon H_{3}\supseteq (H_{1}\cap H_{2})\cup \{x\}}$

The first two conditions state that an anti- chain represents the inclusion relation, which consists of pure subsets of . The third axiom formulated a kind of coverage condition (English covering condition ) ${\displaystyle {\mathcal {H}}}$ ${\displaystyle E}$

literature

• Martin Aigner : Combinatorics II: Matroids and transversal theory (=  university text ). Springer Verlag , Berlin (among others) 1976, ISBN 3-540-07949-1 ( MR0460127 ).
• Martin Aigner : Combinatorial Theory (=  The Basic Teachings of Mathematical Sciences . Volume 234 ). Springer Verlag , Berlin, Heidelberg, New York 1979, ISBN 3-540-90376-3 ( MR0542445 ).
• . Hubertus Th Jongen: optimization B . Script for the lecture. Verlag der Augustinus-Buchhandlung, Aachen 1988, ISBN 3-925038-19-1 .
• Dieter Jungnickel : Transversal Theory (=  mathematics and its applications in physics and technology . Volume 39 ). Academic publishing company Geest & Portig K.-G., Leipzig 1982 ( MR0706076 ).
• Bernhard Korte , László Lovász , Rainer Schrader : Greedoids (=  Algorithms and Combinatorics . Volume 4 ). Springer Verlag , Berlin, Heidelberg 1991, ISBN 3-540-18190-3 ( MR1183735 ).
• Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, Berlin 2007, ISBN 978-3-540-71843-7 .
• Sven Oliver Krumke, Hartmut Noltemeier: Graph theory concepts and algorithms. 2nd Edition. Vieweg-Teubner, Wiesbaden 2009, ISBN 978-3-8348-0629-1 .
• Joseph PS Kung: A Source Book in Matroid Theory. Birkhäuser, Basel 1986, ISBN 3-7643-3173-9 .
• P. Läuchli: Matroide , an introduction for mathematicians and computer scientists. Hochschulverlag vdf, Zurich 1998, ISBN 3-7281-2470-2 .
• Jon Lee: A First Course in Combinatorial Optimization. In: Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge 2004, ISBN 0-521-01012-8 .
• Giorgio Nicoletti, Neil White : Axiom Systems. In: Theory of Matroids. Edited by Neil White, University of Florida (=  Encyclopedia of Mathematics and its Applications . Volume 26 ). Cambridge University Press , Cambridge et al. 1986, ISBN 0-521-30937-9 , pp. 29-44 .
• Hirokazu Nishimura, Susumu Kuroda: A Lost Mathematician, Takeo Nakasawa. The Forgotten Father of Matroid Theory. Birkhäuser, Basel / Boston / Berlin 2009.
• James Oxley : Matroid Theory (=  Oxford Graduate Texts in Mathematics . Volume 21 ). 2nd Edition. Oxford University Press , Oxford 2011, ISBN 978-0-19-960339-8 ( MR2849819 ).
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, Englewood Cliffs (NJ) 1982, ISBN 0-13-152462-3 .
• DJA Welsh : Matroid Theory (=  LMS Monographs . Volume 8 ). Academic Press , London, New York, San Francisco 1976, ISBN 0-12-744050-X ( MR0427112 ).
• DJA Welsh: Matroids: Fundamental Concepts. In: RL Graham, M. Grötschel, L. Lovász (Eds.): Handbook of Combinatorics. Volume 1, MIT Press, Cambridge 1995, pp. 481-527.

Web links

• Mark Hubenthal: A Brief Look At Matroids. ( Memento of March 2, 2012 in the Internet Archive )
• Alexander von Felbert: Introduction to the theory of the matroids. (PDF; 665 kB)

References and footnotes

1. ^ ^{A b} Hassler Whitney: On the abstract properties of linear dependence. In: Amer. J. Math. 57, 3, 1935, pp. 509-533.
2. ^ ^{A b} Leonid Mirsky, Hazel Perfect: Applications of the notion of independence to combinatorial analysis. In: J. Combinatorial Theory. 2, 1967, pp. 317-357.
3. ^ Henry H. Crapo, Gian-Carlo Rota: On the Foundations of Combinatorial Theory: Combinatorial Geometries. Cambridge, MIT Press 1970.
4. ^ Paul M. Cohn: Universal Algebra. Harper & Row, 1965.
5. ↑ Martin Aigner: Kombinatorik II. Pp. 15-16.
6. ↑ Bartel Leendert van der Waerden: Modern Algebra. 2nd Edition. Springer, Berlin 1937.
7. ↑ Hirokazu Nishimura, Susumu Kuroda (Ed.): A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory. Birkhäuser, Basel / Boston / Berlin 2009.
8. ^ Garrett Birkhoff: Abstract linear dependence in lattices. In: Amer. J. Math. 57, 1935, pp. 800-801.
9. ↑ Saunders MacLane: Some interpretations of abstract linear dependence in terms of projective geometry. In: Amer. J. Math. 58, 1936, 236-240.
10. ^ Robert P. Dilworth: Ideals in Birkhoff lattices. In: Trans. Amer. Math. Soc. 49, 1941, pp. 325-353; Arithmetic theory of Birkhoff lattices. In: Duke Math. J. 8, 1941, pp. 286-299; Dependence relations in a semimodular lattice. In: Duke Math. J. 11, pp. 575-587.
11. ^ Richard Rado: A theorem on independence relations. In: Quart. J. Math. 13, 1942, pp. 83-89.
12. ^ Richard Rado: Axiomatic treatment of rank in infinite sets. In: Canad. J. Math. 1, 1949, pp. 337-343.
13. ^ William Thomas Tutte: A homotropy theory for matroids, I and II. In: Trans. Amer. Math. Soc. 88, 1958, pp. 144-174; Matroids and graphs. In: Trans. Amer. Math. Soc. 90, 1959, pp. 527-552.
14. ↑ Welsh: Matroids. In: Handbook of Combinatorics. P. 483.
15. ↑ Jack Edmonds, Delbert R. Fulkerson: Transversals and matroid partition. In: J. Res. Nat. Bar. Stand. 69B, 1965, pp. 147-153.
16. ↑ DJA Welsh: Matroid Theory. 1976, p. 6.
17. ↑ ^{a b} The introductory examples are based on examples from an introductory lecture on Matroid that was given by Frederico Ardila in 2007 at San Francisco State University. See this video and these lecture notes .
18. ↑ The notation of the basic definitions is based on Oxley: Matroid Theory. Pp. 7-15.
19. ^ ^{A b} G. Meyer: Lecture: Algorithms and Data Structures 2 ; University of Leipzig; Winter semester 2000; C. Kingsford: CMSC 451: Matroids, When Greed Works (PDF; 93 kB) ; Lecture slides; Department of Computer Science, University of Maryland; 2009; College Park, US MD.
20. ↑ For a proof of the cryptomorphism between independence axioms and base axioms see z. B. Oxley: Matroid Theory. Pp. 16-18.
21. ↑ For a proof of the cryptomorphism between axioms of independence and axioms of circles see z. B. Oxley: Matroid Theory. Pp. 9-11.
22. ↑ For a proof of the cryptomorphism between independence axioms and circle axioms see Oxley: Matroid Theory. Pp. 9-10.
23. ↑ Alexander von Felbert: Introduction to the Theory of Matroids , In: mathematik-netz.de, November 28, 2007, p. 29; Oxley: Matroid Theory. P. 22.
24. ↑ Alexander von Felbert: Introduction to the theory of the matroids. 2007, p. 31.
25. ↑ ^{a b} D. JA Welsh: Matroid Theory . 1976, p. 38 .
26. ↑ is also called the rank of and it is included ; see. M. Aigner: Combinatorics. II . 1976, p. ${\displaystyle \rho }$ ${\displaystyle M}$ ${\displaystyle \rho =r(E)=r(M)}$ 21 .
27. ↑ M. Aigner: combinatorics. II . 1976, p. 21 .
28. ^ Nicoletti-White: Axiom Systems . S. 37 ff .
29. ↑ DJA Welsh: Matroid Theory . 1976, p. 35-39 .
30. ↑ DJA Welsh: Matroid Theory . 1976, p. 37 .