Matroid (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
Roughly speaking, a matroid is 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 circuit is a circuit,
2. If 
and 
, then 
contains a 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 maximum independent sets contained in 
have the same number of elements.
(Harary 1994, pp. 40-41).
The number of simple matroids (or combinatorial geometries) with 
, 1, ... points are 1, 1, 2, 4, 9, 26, 101, 950, ... (OEIS A002773), and the number 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.)
See also
Combinatorial Geometry,Graphoid, Oriented 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.Crapo, H. H. and Rota, G.-C. "On the Foundations of Combinatorial Theory. II. Combinatorial Geometries." Cambridge, MA: MIT Press, 109-133, 1970.Harary, F. "Matroids." Graph Theory. Reading, MA: Addison-Wesley, pp. 40-41, 1994.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. Sequences A002773/M1197 and A055545 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M1197 in The Encyclopedia of Integer Sequences. San Diego: 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.Whitely, W. "Matroids and Rigid Structures." In Matroid Applications, Encyclopedia of Mathematics and Its Applications (Ed. N. White), Vol. 40. New York: Cambridge University Press, pp. 1-53, 1992.Whitney, H. "On the Abstract Properties of Linear Dependence." Amer. J. Math. 57, 509-533, 1935.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Matroid." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Matroid.html