matroid

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

$a \in cl(A_0 \cup (C \setminus \{b\}) \cup \{b\}) \cap \neg cl(A_0 \cup (C \setminus \{b\})),$

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

$cl(A_0 \cup (B_0 \setminus \{b\}) \cup \{a\}) = cl(A_0 \cup B_0 \cup \{a\}) = X$

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

$cl(D \setminus \{x\}) \subseteq cl((A_0 \cup B_0) \setminus \{x\})$

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

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

$A = A \cap X = A \cap \bigcup_{B_0 \subseteq B\; finite} cl(B_0) = \bigcup_{B_0 \subseteq B\; finite} A \cap cl(B_0)$

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.

- wikipedia matroid, Mnëv’s universality theorem, oriented matroid
- Hassler Whitney,
*On the abstract properties of linear dependence*, American Journal of Mathematics (The Johns Hopkins University Press) 57 (3): 509–533, 1935, jstor, MR1507091 - J. Oxley,
*What is a matroid*, pdf - James G. Oxley,
*Matroid theory*, Oxford Grad. Texts in Math. 1992, 2010 - some papers on Coxeter matroids html
- MathOverflow question Mnëv’s universality corollaries, quantitative versions
- Eric Katz, Sam Payne,
*Realization space for tropical fans*, pdf - Nikolai E. Mnev,
*The universality theorems on the classification problem of configuration varieties and convex polytopes varieties*, pp. 527-543, in “Topology and geometry: Rohlin Seminar.” Edited by O. Ya. Viro. Lecture Notes in Mathematics,**1346**, Springer 1988;*A lecture on universality theorem*(in Russian) pdf - Talal Ali Al-Hawary,
*Free objects in the category of geometries*, pdf - Talal Ali Al-Hawary, D. George McRae,
*Toward an elementary axiomatic theory of the category of LP-matroids*, Applied Categorical Structures**11**: 157–169, 2003, doi - Hirokazu Nishimura, Susumu Kuroda,
*A lost mathematician, Takeo Nakasawa: the forgotten father of matroid theory*1996, 2009 - William H. Cunningham,
*Matching, matroids, and extensions*, Math. Program., Ser. B**91**: 515–542 (2002) doi - L. Lovász,
*Matroid matching and some applications*, J. Combinatorial Theory B**28**, 208–236 (1980) - A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G.M. Ziegler,
*Oriented matroids*, Cambridge Univ. Press 1993, 2000, view at reslib.com - Matthew Baker,
*Matroids over hyperfields*, arxiv/1601.01204 - David Marker,
*Model Theory: An Introduction*, Graduate Texts in Math. 217, Springer-Verlag New York, 2002.

Revised on February 18, 2016 08:00:57
by Todd Trimble
(67.81.95.215)