TOPICS
Search

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 M of elements together with a family C={C_1,C_2,...} of nonempty subsets of M, called circuits, which satisfy the axioms

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

2. If x in C_1 intersection C_2 and C_1!=C_2, then C_1 union C_2-{x} contains a circuit.

(Harary 1994, p. 40).

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

1. The empty set is independent,

2. Every subset of an independent set is independent,

3. For every subset A of M, all maximum independent sets contained in A have the same number of elements.

(Harary 1994, pp. 40-41).

The number of simple matroids (or combinatorial geometries) with n=0, 1, ... points are 1, 1, 2, 4, 9, 26, 101, 950, ... (OEIS A002773), and the number of matroids on n=0, 1, ... points are 1, 2, 4, 8, 17, 38, 98, 306, 1724, ... (OEIS A055545; Oxley 1993, p. 473). (The value for n=5 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

Matroid

Cite this as:

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

Subject classifications