Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
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.
A matroid on a set is a closure operator satisfying the exchange axiom: for all and , if , then .
Without loss of generality, the exchange axiom can be stated as: if , then , since the implication is vacuous when .
When combinatorialists speak of matroids as such, is usually taken to be a finite set. A typical example is some finite subset of a vector space , taking for any .
Further terminology:
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.
Any two bases (Def. ) of a matroid 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 is an independent set and is a finite basis, and suppose there are subsets such that is a basis. We claim that for each , there exists such that is a basis. For, let be of minimum cardinality such that ; we know must be inhabited since ; clearly . So let be an element of . Since by minimality of we have
it follows from the exchange axiom that . Thus , whence
so that “spans” . Also is independent: if and , then
with neither side containing since is independent; whereas if and supposing to the contrary that , we conclude has the same span as . Since already spans, , again impossible since is independent. This proves the claim.
Again assuming independent and is a finite basis, now we show that , which will finish the proof. Let , and suppose on the contrary that there are distinct elements . Set and . Applying the claim above inductively, we have that is a basis for , so in particular spans . Hence , contradicting the independence of .
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 (in model theory) is a (possibly infinite) matroid (Def. , given by a set equipped with a closure operator ) that is finitary:
A geometry is a pregeometry such that, in addition:
(the empty subset is closed),
for every (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.
In a pregeometry , any two bases have the same cardinality.
We already proved this in the case where the pregeometry has a finite basis. Otherwise, if is independent and is an infinite basis, then
where the second equality follows from the finitary condition. Since each summand has cardinality less than that of by independence of (noting that is a basis of ), the union on the right has cardinality bounded above by . From it follows that any two bases have the same cardinality.
Vector spaces, algebraic closures, graphs, restrictions, localizations, …
A graphic matroid is a matroid derived from a simple graph by taking the underlying set of to be the set of edges , and taking as independent sets of those such that the edges of (and their incident vertices) form a forest, i.e., a graph without cycles.
A vector matroid is a matroid derived from a a collection of vectors in a vector space. Independent sets of are those such that 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 is derived from a collection of elements and independent sets of are those such that has transcendence degree equal to so all of are algebraically independent.
If is a (finite) matroid, then the matroid dual of has the same underlying set as , and where a basis in is precisely the complement of a basis of . It follows that (this is even an equality according to the definition).
For a topological space the exchange condition is equivalent to
In particular, every -space is a matroid.
Mnëv’s universality theorem says that any semialgebraic set in defined over integers is stably equivalent to the realization space of some oriented matroid.
(…)
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:
Tom Braden, June Huh, Jacob P. Matherne, Nicholas Proudfoot, Botong Wang, Singular Hodge theory for combinatorial geometries [arXiv:2010.06088]
June Huh, Combinatorics and Hodge theory, Proc. Int. Cong. Math. 1 (2022)
[doi:10.4171/ICM2022/205, pdf, pdf]
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.