Matroid
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
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.
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:
Matroid
CITE THIS AS:
Weisstein, Eric W. "Matroid." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Matroid.html
Contact the MathWorld Team
12-wheel graph