matroid in nLab

+-- {: .rightHandSide}
+-- {: .toc .clickDown tabindex="0"}
### Context
#### Combinatorics
+-- {: .hide}
[[!include combinatorics - contents]]
=--
#### Modalities, Closure and Reflection
+-- {: .hide}
[[!include modalities - contents]]
=--
=--
=--


# Contents #
* table of contents 
{: toc}

## Idea 

The concept of *matroid* ([Whitney 1935](#Whitney35)) is fundamental to [[combinatorics]], giving several different ways of encoding/defining and presenting a general notion of "independence", e.g., [[linearly independent subset|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. 

## Definitions 

### Plain definition

\begin{definition}\label{Matroid}
A **matroid** on a [[set]] $X$ is a [[Moore closure|closure operator]] $cl \colon P(X) \to P(X)$ satisfying the _exchange axiom_: for all $a, b \in X$ and $S \subseteq X$, if $a \in cl(S \cup\{b\}) \setminus cl(S)$, then $b \in cl(S \cup\{a\}) \setminus cl(S)$. 
\end{definition}

\begin{remark}
Without loss of generality, the exchange axiom can be stated as: if $a \in cl(S + \{b\}) \setminus cl(S)$, then $b \in cl(S + \{a\}) \setminus cl(S)$, since the implication is vacuous when $b \in S$.
\end{remark}

\begin{remark}
When [[combinatorics|combinatorialists]] speak of matroids as such, $X$ is usually 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$. 
\end{remark}

Further terminology:

\begin{definition}\label{Bases}
Under Def. \ref{Matroid}: 

1. A [[subset]] $S \subseteq X$ is called *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$). 

1. A [[subset]] $S \subset X$ is called a _basis_ if $cl(S) = X$ and $S$ is independent. 

1. A _hyperplane_ is a closed subset $S$ (meaning $cl(S) = S$) that is maximal among proper closed subsets of $X$. 

\end{definition}

It is possible to axiomatize the notion of matroid by taking bases (Def. \ref{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. 

+-- {: .num_prop #dim1} 
###### Proposition 

Any two bases (Def. \ref{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. 

+-- {: .proof} 
###### Proof 
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$. 

=-- 



### Model-theoretic geometry 
 {#ModelTheoreticGeometry}

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). 

\begin{definition}

A _pregeometry_ (in [[model theory]]) is a (possibly infinite) matroid (Def. \ref{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 set|finite]] [[subset]] $S_0 \subseteq S$. 

A *geometry* is a pregeometry such that, in addition:

1. $cl(\varnothing) = \varnothing$ (the [[empty set|empty subset]] is closed),

1. $cl(\{x\}) = \{x\}$ for every $x \in X$ (all [[singleton]] subsets are closed).

\end{definition}

(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 [[axiom of choice|Zorn's lemma]]. Again we have a notion of dimension by the following proposition. 

+-- {: .num_prop #welldefined} 
###### Proposition 
In a pregeometry $(X, cl)$, any two bases have the same cardinality. 
=-- 

+-- {: .proof} 
###### Proof 
We already [proved this](#dim1) 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. 
=-- 



## Examples 
 {#Examples}

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.  

* A *vector matroid* is a matroid $M$ derived from a a collection of vectors $E$ in a vector space. Independent sets of $M$ are those $S \subseteq E$ such that $S$ is linearly independent. Providing an equivalence to such a vector matroid is the problem of representability over a specified field.

* An *algebraic matroid* for a field extension $K/F$ is derived from a collection of elements $E \subset K$ and independent sets of $M$ are those such that $F(S)$ has transcendence degree equal to $\mid S \mid$ so all of $S$ are algebraically independent.

* 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). 

* For a topological space $X$ the exchange condition is equivalent to
$$ \forall x,y \in X: x\in cl({y}) \Leftrightarrow y\in cl({x}) $$
In particular, every $T1$-space is a matroid.


## Properties

### Mnev's theorem 

Mn&#235;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. 


### Combinatorial optimization 

(...)


## Related concepts

* [[oriented matroid]]

## References 

The original article:

* {#Whitney35} [[Hassler Whitney]], _On the abstract properties of linear dependence_, American Journal of Mathematics (The Johns Hopkins University Press) **57** 3  (1935) 509-533 &lbrack;[jstor:2371182](http://jstor.org/stable/2371182), [MR1507091](http://www.ams.org/mathscinet-getitem?mr=1507091)&rbrack;

* H. H. Crapo, [[Gian Carlo Rota]], _On the foundations of combinatorial theory: combinatorial geometries_, MIT Press, Cambridge 1970

On the [[category]] of matroids with *strong maps* between them:

* [[Chris Heunen]], [[Vaia Patta]], *The category of matroids*, Applied Categorical Structures **26** (2018) 205–237 &lbrack;[arXiv:1512.01390](https://arxiv.org/abs/1512.01390), [doi:10.1007/s10485-017-9490-2](https://doi.org/10.1007/s10485-017-9490-2)&rbrack;

On [[Hodge theory]] and [[intersection cohomology]] of matroids:

* Tom Braden, [[June Huh]], Jacob P. Matherne, [[Nicholas Proudfoot]], Botong Wang, *Singular Hodge theory for combinatorial geometries* &lbrack;[arXiv:2010.06088](https://arxiv.org/abs/2010.06088)&rbrack;


* {#Huh22} [[June Huh]], _Combinatorics and Hodge theory_, Proc. Int. Cong. Math. **1** (2022)
 &lbrack;[doi:10.4171/ICM2022/205](), [pdf](https://www.mathunion.org/fileadmin/IMU/Prizes/Fields/2022/jh.pdf), [[Huh-CombinatoricsAndHodgeTheory.pdf:file]]&rbrack;

On the axiomatization of [[infinite set|infinite]] matroids:

* [[Henning Bruhn]], [[Reinhard Diestel]], [[Matthias Kriesell]], [[Rudi Pendavingh]], [[Paul Wollan]], *Axioms for infinite matroids*, Advances in Mathematics, **239** (2013) 18–46 &lbrack;[arXiv:1003.3919](https://arxiv.org/abs/1003.3919), [doi:10.1016/j.aim.2013.01.011](https://doi.org/10.1016/j.aim.2013.01.011)&rbrack;

Further references:

* Wikipedia [matroid](http://en.wikipedia.org/wiki/Matroid), [Mn&#235;v's universality theorem](http://en.wikipedia.org/wiki/Mnev%27s_universality_theorem), [oriented matroid](http://en.wikipedia.org/wiki/Oriented_matroid), [matroid minor](https://en.wikipedia.org/wiki/Matroid_minor)


* J. Oxley, _What is a matroid_, [pdf](http://www.math.lsu.edu/~oxley/survey4.pdf)
* James G. Oxley, _Matroid theory_, Oxford Grad. Texts in Math. 1992, 2010
* some papers on Coxeter matroids [html](http://www.math.ufl.edu/~white/cox.html)

* MathOverflow question [Mn&#235;v's universality corollaries, quantitative versions](http://mathoverflow.net/questions/72154/mnevs-universality-corollaries-quantitative-versions) 
* Eric Katz, Sam Payne, _Realization space for [[tropical geometry|tropical]] fans_, [pdf](http://users.math.yale.edu/~sp547/pdf/Realization-spaces.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](http://club.pdmi.ras.ru/~panina/9.pdf)
* Talal Ali Al-Hawary, _Free objects in the category of geometries_, [pdf](http://www.emis.de/journals/HOA/IJMMS/Volume26_12/770.pdf)
* Talal Ali Al-Hawary, D. George McRae, _Toward an elementary axiomatic theory of the category of LP-matroids_, Applied Categorical Structures __11__: 157&#8211;169, 2003, [doi](https://doi.org/10.1023/A:1023557229668)
* 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&#8211;542 (2002) [doi](https://doi.org/10.1007/s101070100256)
* L. Lov&#225;sz, _Matroid matching and some applications_, J. Combinatorial Theory B __28__, 208--236 (1980)
* A. Bj&#246;rner, M. Las Vergnas, B. Sturmfels, N. White, G.M. Ziegler,  _Oriented matroids_, Cambridge Univ. Press 1993, 2000, [view at reslib.com](http://reslib.com/book/Oriented_Matroids)
* Matthew Baker, _Matroids over hyperfields_, [arxiv/1601.01204](https://arxiv.org/abs/1601.01204)
* David Marker, _Model theory: an introduction_, Graduate Texts in Math. __217__, Springer-Verlag New York, 2002. 
* Tom Braden, Carl Mautner, _Matroidal Schur algebras_, [arxiv/1609.04507](https://arxiv.org/abs/1609.04507)
* P. S. Kung, _A source book in matroid theory_, Birkh&#228;user, Boston, 1986.
* Jim Geelen, Bert Gerards, Geoff Whittle, _Towards a structure theory for matrices and matroids_ , ICM 2006 Proceedings 827--842 [pdf](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/towards_a_structure_theory_for_matrices_and_matroids.pdf)
* [[I. M. Gelfand]], R. M. Goresky, R. D. MacPherson, _Combinatorial geometries, convex polyhedra, and Schubert cells_, Adv. Math. __63 (1987) 301--316 
* [[Federico Ardila]], _The geometry of geometries: matroid theory, old and new_, [arXiv:2111.08726](https://arxiv.org/abs/2111.08726)


category: combinatorics, model theory

[[!redirects matroids]] 
[[!redirects pregeometry]]
[[!redirects pregeometries]]