The concept of matroid, due to Hassler Whitney, is fundamental to combinatorics, giving several different ways of encoding/defining and presenting a general notion of “independence”, e.g., linear independence in a vector space, algebraic independence in a field extension, etc.
There is also a similar concept of an oriented matroid; every oriented matroid has an underlying matroid.
A matroid on a set $X$ is a closure operator $cl: P(X) \to P(X)$ satisfying the exchange axiom: if $a \in cl(S \cup\{b\}) \cap \neg cl(S)$, then $b \in cl(S \cup\{a\}) \cap \neg cl(S)$.
Usually when combinatorialists speak of matroids as such, $X$ is taken to be a finite set. A typical example is $X$ some finite subset of a vector space $V$, taking $cl(S) \coloneqq X \cap Span(S)$ for any $S \subseteq X$.
Under this definition, a subset $S \subseteq X$ is independent if there is a strict inclusion $cl(T) \subset cl(S)$ for every strict inclusion $T \subset S$ (this is the same as requiring $x \notin cl(S\setminus \{x\})$ for every $x \in S$). Again under this definition, $S$ is a basis if $cl(S) = X$ and $S$ is independent. A hyperplane is a closed subset $S$ (meaning $cl(S) = S$) that is maximal among proper closed subsets of $X$. It is possible to axiomatize the notion of matroid by taking bases as the primitive notion, or independent sets as the primitive notion, or hyperplanes as the primitive notion, etc. – Rota (after Birkhoff) speaks of cryptomorphism between these differing definitions. Much of the power and utility of matroid theory comes from this multiplicity of definitions and the possibility of moving seamlessly between them; for example, a matroid structure might be easy to detect from the viewpoint of one definition, but not from another.
Any two bases of a matroid $X$ have the same cardinality, provided that one of them is finite.
The cardinality of such a basis is called of course the dimension of the matroid. Clearly then a finite matroid has a well-defined dimension.
First, suppose $A$ is an independent set and $B$ is a finite basis, and suppose there are subsets $A_0 \subseteq A, B_0 \subseteq B$ such that $A_0 \cup B_0$ is a basis. We claim that for each $a \in A \setminus A_0$, there exists $b \in B_0$ such that $A_0 \cup \{a\} \cup (B_0 \setminus \{b\})$ is a basis. For, let $C \subseteq B_0$ be of minimum cardinality such that $a \in cl(A_0 \cup C)$; we know $C$ must be inhabited since $a \notin cl(A \setminus \{a\}) \supseteq cl(A_0)$; clearly $C \cap A_0 = \emptyset$. So let $b$ be an element of $C$. Since by minimality of $C$ we have
it follows from the exchange axiom that $b \in cl(A_0 \cup (C \setminus \{b\}) \cup \{a\})$. Thus $b \in cl(A_0 \cup (B_0 \setminus \{b\}) \cup \{a\})$, whence
so that $D \coloneqq A_0 \cup (B_0 \setminus \{b\}) \cup \{a\}$ “spans” $X$. Also $D$ is independent: if $x \in D$ and $x \neq a$, then
with neither side containing $x$ since $A_0 \cup B_0$ is independent; whereas if $x = a$ and supposing to the contrary that $a \in cl(D \setminus \{a\}) = cl((A_0 \cup (B_0 \setminus \{b\}))$, we conclude $A_0 \cup (B \setminus \{b\})$ has the same span as $D$. Since $D$ already spans, $b \in cl(A_0 \cup (B_0 \setminus \{b\}))$, again impossible since $A_0 \cup B_0$ is independent. This proves the claim.
Again assuming $A$ independent and $B$ is a finite basis, now we show that $card(A) \leq card(B)$, which will finish the proof. Let $n = card(B)$, and suppose on the contrary that there are distinct elements $a_1, \ldots, a_{n+1} \in A$. Set $A_0 = \emptyset$ and $B_0 = B$. Applying the claim above inductively, we have that $\{a_1, \ldots, a_i\} \cup (B \setminus \{b_1, \ldots, b_i\})$ is a basis for $1 \leq i \leq n$, so in particular $\{a_1, \ldots, a_n\}$ spans $X$. Hence $a_{n+1} \in cl(\{a_1, \ldots, a_{n}\})$, contradicting the independence of $A$.
Vector spaces, algebraic closures, graphs, restrictions, localizations, …
A graphic matroid is a matroid $M$ derived from a simple graph by taking the underlying set of $M$ to be the set of edges $E$, and taking as independent sets of $M$ those $S \subseteq E$ such that the edges of $S$ (and their incident vertices) form a forest?, i.e., a graph without cycles.
If $M$ is a (finite) matroid, then the matroid dual $M^\ast$ of $M$ has the same underlying set as $M$, and where a basis in $M^\ast$ is precisely the complement of a basis of $M$. It follows that $M^{\ast\ast} \cong M$ (this is even an equality according to the definition).
Essentially the very same notion arises in model theory, except instead of being called a matroid it is called a “pregeometry” or “geometry”, and in contrast to combinatorialists, model theorists usually mean infinite matroids. The notion arises in the study of geometry of strongly minimal sets, with applications to stability theory (part of Shelah’s classification theory).
A pregeometry is a (possibly infinite) matroid (given by a set $X$ equipped with a closure operator $cl$) that is finitary: for all $S \subseteq X$, if $x \in cl(S)$ then $x \in cl(S_0)$ for some finite subset $S_0 \subseteq S$. A geometry is a pregeometry such that $cl(\emptyset) = \emptyset$ and $cl(\{x\}) = \{x\}$ for every $x \in X$.
(See also geometric stability theory.)
The language of independence, spanning, and basis carry over as before. A maximal independent set spans (i.e., is a basis), and maximal independent sets exist according to Zorn's lemma. Again we have a notion of dimension by the following proposition.
In a pregeometry $(X, cl)$, any two bases have the same cardinality.
We already proved this in the case where the pregeometry has a finite basis. Otherwise, if $A$ is independent and $B$ is an infinite basis, then
where the second equality follows from the finitary condition. Since each summand $A \cap cl(B_0)$ has cardinality less than that of $B_0$ by independence of $A$ (noting that $B_0$ is a basis of $cl(B_0)$), the union on the right has cardinality bounded above by $card(B)$. From $card(A) \leq card(B)$ it follows that any two bases have the same cardinality.
Mnëv’s universality theorem says that any semialgebraic set in $\mathbb{R}^n$ defined over integers is stably equivalent to the realization space of some oriented matroid.
To be written, possibly with some original research.
Last revised on August 2, 2017 at 08:16:21. See the history of this page for a list of all contributions to it.