Live briefing
Everything about Matroid
Abstraction of linear independence of vectors
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of independent sets, bases or circuits, rank functions, closure operators, and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: MatroidA 5-minute orientation
- Skim a recent paper: A semi-small decomposition of the Chow ring of a matroidInfluential work since 2022
- Pick up a classic book: MatroidsThe most-reprinted book on the subject
- Read the landmark paper: Global optimal eBURST analysis of multilocus typing data using a graphic matroid approachCited 580 times
- Go sideways: Matroid minorA closely related topic
- Go sideways: Uniform matroidA closely related topic
📖 Definitions
Noun A structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces and acyclicality in graphs.
🏆 Landmark papers (most cited)
Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
Minimum partition of a matroid into independent subsets
Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning
On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
Radial Network Reconfiguration Using Genetic Algorithm Based on the Matroid Theory
Transversals and matroid partition
The Bergman complex of a matroid and phylogenetic trees
🆕 Influential since 2022
A semi-small decomposition of the Chow ring of a matroid
Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid
Hilbert–Poincaré series of matroid Chow rings and intersection cohomology
Synthesis of Assur groups via group and matroid theory
Truthful and Fair Mechanisms for Matroid-Rank Valuations
📚 Books worth reading
- 📕MatroidsGary Gordon, Jennifer McNulty · 2012
Combinatorial geometriesNeil White · 1987
Combinatorial optimizationEugene L. Lawler · 1975
Theory of matroidsNeil White · 1992
Oriented matroidsAnders Björner · 1999- 📕Pattern Recognition on Oriented MatroidsAndrey O. Matveev · 2017
Matroid applicationsNeil White · 1992
Boolean Representations of Simplicial Complexes and MatroidsJohn Rhodes, Pedro V. Silva · 2015
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Matroid minor In the mathematical theory of matroids, a minor of a matroid M is another matroid N that is obtained from M by a sequence of restriction and contraction…
- Uniform matroid In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most r elements, for some fixed integer…
- Matroid representation In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given…
- Graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the…
- Matroid rank In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements…
- Regular matroid In mathematics, a regular matroid is a matroid that can be represented over all fields. A matroid is defined to be a family of subsets of a finite set…
- Oriented matroid An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane…
- Dowling geometry In combinatorial mathematics, a Dowling geometry, named after Thomas A. Dowling, is a matroid associated with a group. There is a Dowling geometry of each…