A matroid is, roughly speaking, a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept. For example, the finite set could be the rows of a matrix, and the generalizing concept could be linear dependence and independence of any subset of rows of the matrix.

Formally, a matroid consists of a finite set of elements together with a family of nonempty subsets of , called circuits, which satisfy the axioms

1. No proper subset of a matroid circuit is a matroid circuit,

2. If and , then contains a matroid circuit.

(Harary 1994, p. 40).

An equivalent definition considers a matroid as a finite set of elements together with a family of subsets of , called independent sets, such that

1. The empty set is independent,

2. Every subset of an independent set is independent,

3. For every subset of , all inclusion-maximal independent sets contained in have the same number of elements.

(Harary 1994, pp. 40-41).

For a finite matroid, a cyclic basis ordering is a cyclic order of its ground set in which every window of matroid rank length is a matroid basis. The Kajitani-Ueno-Miyano conjecture asserts that these orderings exist exactly for uniformly dense matroids (Kajitani et al. 1988).

Up to isomorphism, the numbers of simple matroids (or combinatorial geometries) with , 1, ... points are 1, 1, 1, 2, 4, 9, 26, 101, 950, ... (OEIS A002773), and the numbers of matroids on , 1, ... points are 1, 2, 4, 8, 17, 38, 98, 306, 1724, ... (OEIS A055545; Oxley 1993, p. 473). (The value for given by Oxley 1993, p. 42, is incorrect.)

A basic example is the uniform matroid , whose independent sets are precisely the subsets of an -element ground set of size at most . Parallel thickenings of these matroids provide explicit counterexamples to the multiplicative Merino-Welsh conjecture for matroids (Chen et al. 2026).

A Helly-type property concerns bases adapted to several matroid flats. A matroid basis is adapted to a matroid flat when is a matroid basis of . Jafari and Kaveh (2026) proved that a family of matroid flats in a matroid of matroid rank has a common adapted basis iff each subfamily of at most flats does. The number is sharp for . The result also allows infinite ground sets and families when the rank is finite. Jafari and Kaveh (2026) report AI assistance with the proof.

For an integer , a finite matroid is -entropic if there is a family of random variables indexed by its ground set, taking values in a common -element alphabet, such that the joint Shannon entropy for each subset equals its matroid rank times . Kalantari and Khazaei (2026, Theorem 1.1) proved that the 5-entropic matroids are precisely those representable over the finite field .

See also

Circuit-Cocircuit Intersection Conjecture, Combinatorial Geometry, Cyclic Basis Ordering, Dual Matroid, Graphoid, Ground Set, Kajitani-Ueno-Miyano Conjecture, Matroid Circuit, Matroid Cocircuit, Matroid Coloring, Matroid Intersection, Matroid Minor, Matroid Prophet Inequality, Merino-Welsh Conjecture, Oriented Matroid, Partition Matroid, Polymatroid, Strongly Base-Orderable Matroid, Uniformly Dense Matroid

Explore with Wolfram|Alpha

References

Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; and Ziegler, G. Oriented Matroids, 2nd ed. Cambridge, England: Cambridge University Press, 1999.Blackburn, J. E.; Crapo, H. H.; and Higgs, D. A. "A Catalogue of Combinatorial Geometries." Math. Comput. 27, 155-166, 1973.Chen, J.; Jin, X.; and Ma, T. "On Minimum-Size Matroid Counterexamples to the Multiplicative Merino-Welsh Inequality." 20 Oct 2026. https://arxiv.org/abs/2610.27706.Crapo, H. H. and Rota, G.-C. "On the Foundations of Combinatorial Theory II. Combinatorial Geometries." Stud. Appl. Math. 49, 109-133, 1970. https://doi.org/10.1002/sapm1970492109.Harary, F. "Matroids." Graph Theory. Reading, MA: Addison-Wesley, pp. 40-41, 1994.Jafari, A. and Kaveh, K. "Helly Theorems for Lattice of Flats of a Matroid." 27 Oct 2026. https://arxiv.org/abs/2610.36566.Kajitani, Y.; Ueno, S.; and Miyano, H. "Ordering of the Elements of a Matroid Such That Its Consecutive Elements Are Independent." Disc. Math. 72, 187-194, 1988. https://doi.org/10.1016/0012-365x(88)90209-9.Kalantari, M. H. and Khazaei, S. "Five-Entropic Matroids Are Quinary." 9 Nov 2026. https://arxiv.org/abs/2611.11970v1.Minty, G. "On the Axiomatic Foundations of the Theories of Directed Linear Graphs, Electric Networks, and Network-Programming." J. Math. Mech. 15, 485-520, 1966.Oxley, J. G. Matroid Theory. Oxford, England: Oxford University Press, 1993.Papadimitriou, C. H. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982.Richter-Gebert, J. and Ziegler, G. M. In Handbook of Discrete and Computational Geometry (Ed. J. E. Goodman and J. O'Rourke). Boca Raton, FL: CRC Press, pp. 111-112, 1997.Sloane, N. J. A. and Plouffe, S. Figure M1197 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Tutte, W. T. "Lectures on Matroids." J. Res. Nat. Bur. Stand. Sect. B 69, 1-47, 1965.West, D. B. "Matroids." §8.2 in Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 349-378, 2000.Whiteley, W. "Matroids and Rigid Structures." In Matroid Applications (Ed. N. White). New York: Cambridge University Press, pp. 1-53, 1992. https://doi.org/10.1017/CBO9780511662041.002.Whitney, H. "On the Abstract Properties of Linear Dependence." Amer. J. Math. 57, 509-533, 1935.Sloane, N. J. A. Sequences A002773/M1197 and A055545 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Matroid

Cite this as:

Weisstein, Eric W. "Matroid." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Matroid.html

Subject classifications