nLab matroid

Redirected from "matroids".
Contents

Contents

Idea

The concept of matroid (Whitney 1935) 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.

Definitions

Plain definition

Definition

A matroid on a set XX is a closure operator cl:P(X)P(X)cl \colon P(X) \to P(X) satisfying the exchange axiom: for all a,bXa, b \in X and SXS \subseteq X, if acl(S{b})cl(S)a \in cl(S \cup\{b\}) \setminus cl(S), then bcl(S{a})cl(S)b \in cl(S \cup\{a\}) \setminus cl(S).

Remark

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

Remark

When combinatorialists speak of matroids as such, XX is usually taken to be a finite set. A typical example is XX some finite subset of a vector space VV, taking cl(S)XSpan(S)cl(S) \,\coloneqq\, X \cap Span(S) for any SXS \subseteq X.

Further terminology:

Definition

Under Def. :

  1. A subset SXS \subseteq X is called independent if there is a strict inclusion cl(T)cl(S)cl(T) \subset cl(S) for every strict inclusion TST \subset S (this is the same as requiring xcl(S{x})x \notin cl(S\setminus \{x\}) for every xSx \in S).

  2. A subset SXS \subset X is called a basis if cl(S)=Xcl(S) = X and SS is independent.

  3. A hyperplane is a closed subset SS (meaning cl(S)=Scl(S) = S) that is maximal among proper closed subsets of XX.

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

Proposition

Any two bases (Def. ) of a matroid XX 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

First, suppose AA is an independent set and BB is a finite basis, and suppose there are subsets A 0A,B 0BA_0 \subseteq A, B_0 \subseteq B such that A 0B 0A_0 \cup B_0 is a basis. We claim that for each aAA 0a \in A \setminus A_0, there exists bB 0b \in B_0 such that A 0{a}(B 0{b})A_0 \cup \{a\} \cup (B_0 \setminus \{b\}) is a basis. For, let CB 0C \subseteq B_0 be of minimum cardinality such that acl(A 0C)a \in cl(A_0 \cup C); we know CC must be inhabited since acl(A{a})cl(A 0)a \notin cl(A \setminus \{a\}) \supseteq cl(A_0); clearly CA 0=C \cap A_0 = \emptyset. So let bb be an element of CC. Since by minimality of CC we have

acl(A 0(C{b}){b})¬cl(A 0(C{b})),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 bcl(A 0(C{b}){a})b \in cl(A_0 \cup (C \setminus \{b\}) \cup \{a\}). Thus bcl(A 0(B 0{b}){a})b \in cl(A_0 \cup (B_0 \setminus \{b\}) \cup \{a\}), whence

cl(A 0(B 0{b}){a})=cl(A 0B 0{a})=Xcl(A_0 \cup (B_0 \setminus \{b\}) \cup \{a\}) = cl(A_0 \cup B_0 \cup \{a\}) = X

so that DA 0(B 0{b}){a}D \coloneqq A_0 \cup (B_0 \setminus \{b\}) \cup \{a\} “spans” XX. Also DD is independent: if xDx \in D and xax \neq a, then

cl(D{x})cl((A 0B 0){x})cl(D \setminus \{x\}) \subseteq cl((A_0 \cup B_0) \setminus \{x\})

with neither side containing xx since A 0B 0A_0 \cup B_0 is independent; whereas if x=ax = a and supposing to the contrary that acl(D{a})=cl((A 0(B 0{b}))a \in cl(D \setminus \{a\}) = cl((A_0 \cup (B_0 \setminus \{b\})), we conclude A 0(B{b})A_0 \cup (B \setminus \{b\}) has the same span as DD. Since DD already spans, bcl(A 0(B 0{b}))b \in cl(A_0 \cup (B_0 \setminus \{b\})), again impossible since A 0B 0A_0 \cup B_0 is independent. This proves the claim.

Again assuming AA independent and BB is a finite basis, now we show that card(A)card(B)card(A) \leq card(B), which will finish the proof. Let n=card(B)n = card(B), and suppose on the contrary that there are distinct elements a 1,,a n+1Aa_1, \ldots, a_{n+1} \in A. Set A 0=A_0 = \emptyset and B 0=BB_0 = B. Applying the claim above inductively, we have that {a 1,,a i}(B{b 1,,b i})\{a_1, \ldots, a_i\} \cup (B \setminus \{b_1, \ldots, b_i\}) is a basis for 1in1 \leq i \leq n, so in particular {a 1,,a n}\{a_1, \ldots, a_n\} spans XX. Hence a n+1cl({a 1,,a n})a_{n+1} \in cl(\{a_1, \ldots, a_{n}\}), contradicting the independence of AA.

Model-theoretic geometry

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

Definition

A pregeometry (in model theory) is a (possibly infinite) matroid (Def. , given by a set XX equipped with a closure operator clcl) that is finitary:

  • for all SXS \subseteq X, if xcl(S)x \in cl(S) then xcl(S 0)x \in cl(S_0) for some finite subset S 0SS_0 \subseteq S.

A geometry is a pregeometry such that, in addition:

  1. cl()=cl(\varnothing) = \varnothing (the empty subset is closed),

  2. cl({x})={x}cl(\{x\}) = \{x\} for every xXx \in X (all singleton subsets are closed).

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

Proposition

In a pregeometry (X,cl)(X, cl), any two bases have the same cardinality.

Proof

We already proved this in the case where the pregeometry has a finite basis. Otherwise, if AA is independent and BB is an infinite basis, then

A=AX=A B 0Bfinitecl(B 0)= B 0BfiniteAcl(B 0)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 Acl(B 0)A \cap cl(B_0) has cardinality less than that of B 0B_0 by independence of AA (noting that B 0B_0 is a basis of cl(B 0)cl(B_0)), the union on the right has cardinality bounded above by card(B)card(B). From card(A)card(B)card(A) \leq card(B) it follows that any two bases have the same cardinality.

Examples

Vector spaces, algebraic closures, graphs, restrictions, localizations, …

  • A graphic matroid is a matroid MM derived from a simple graph by taking the underlying set of MM to be the set of edges EE, and taking as independent sets of MM those SES \subseteq E such that the edges of SS (and their incident vertices) form a forest, i.e., a graph without cycles.

  • A vector matroid is a matroid MM derived from a a collection of vectors EE in a vector space. Independent sets of MM are those SES \subseteq E such that SS 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/FK/F is derived from a collection of elements EKE \subset K and independent sets of MM are those such that F(S)F(S) has transcendence degree equal to S\mid S \mid so all of SS are algebraically independent.

  • If MM is a (finite) matroid, then the matroid dual M *M^\ast of MM has the same underlying set as MM, and where a basis in M *M^\ast is precisely the complement of a basis of MM. It follows that M **MM^{\ast\ast} \cong M (this is even an equality according to the definition).

  • For a topological space XX the exchange condition is equivalent to

    x,yX:xcl(y)ycl(x) \forall x,y \in X: x\in cl({y}) \Leftrightarrow y\in cl({x})

    In particular, every T1T1-space is a matroid.

Properties

Mnev’s theorem

Mnëv’s universality theorem says that any semialgebraic set in n\mathbb{R}^n defined over integers is stably equivalent to the realization space of some oriented matroid.

Combinatorial optimization

(…)

References

The original article:

  • Hassler Whitney, On the abstract properties of linear dependence, American Journal of Mathematics (The Johns Hopkins University Press) 57 3 (1935) 509-533 [jstor:2371182, MR1507091]

  • 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:

On Hodge theory and intersection cohomology of matroids:

On the axiomatization of infinite matroids:

Further references:

  • Wikipedia matroid, Mnëv’s universality theorem, oriented matroid, matroid minor

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

  • Tom Braden, Carl Mautner, Matroidal Schur algebras, arxiv/1609.04507

  • P. S. Kung, A source book in matroid theory, Birkhäuser, Boston, 1986.

  • Jim Geelen, Bert Gerards, Geoff Whittle, Towards a structure theory for matrices and matroids , ICM 2006 Proceedings 827–842 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

Last revised on September 24, 2024 at 21:06:57. See the history of this page for a list of all contributions to it.