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
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.)
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. B69,
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.
of elements together with a family 
of nonempty subsets of 
, called circuits, which satisfy the axioms
and 
, then 
contains a circuit.
of elements together with a family of subsets of 
, called independent sets, such that
of 
, all maximum independent sets contained
in 
have the same number of elements.
,
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.)
