A matroid is a mathematical construct, just as a group, a field, or a topology is a construct. It has a somewhat surprisingly large number of associated operators or special collections of subsets, and perhaps just as surprisingly, one can use any one of these to "define" what a matroid actually is.

Matroid: Mathematics. a pair (E,B), where E is a nonempty finite set and B is a nonempty collection of subsets of E (called bases) such that: (a) no base is properly contained in another base, and (b) if B1 and B2 are bases and if e is any element of B1, then there is an element f of B2 with the property that (B1-{e }) {f} is also a base. It then follows as a consequence of property (b) above that any two bases of a matroid contain the same number of elements; this is the rank of the matroid.

Matroid. This is an abstraction of independence that includes vectors in linear algebra and circuits in graphs. First, we need some preliminary definitions. Let N={1, ..., n} be a finite set, and let M={S1, ..., Sm} be a collection of subsets of N. (N,M) is an independence system if Si in M implies every subset of Si is in M. Elements of M are called independent sets, and the remaining subsets of N are called dependent sets. An independent set, say Si, is maximal if Si\/{k} is not in M for any k in N\Si. The max-cardinality independent set of any subset of N, say T, is given by:

m(T) = max{|Si|: Si in M, Si a subset of T}.
A matroid is an independence system (N, M) in which for any subset of N, say T, every independent set in T that is maximal in T has cardinality m(T). The definition essentially means that maximal and maximum are the same. In other words, a system is a matroid if, and only if, a greedy algorithm yields a globally optimal solution to the associated max weight problem. An example is the spanning tree.

Matroid Links

Joe Bonin's Introduction to Matroids (35 page postscript file)

Alexandre Borovik's Coxter Matroids

Stephen Locke's Graph Theory Index

Bruce Mills' Introduction to Matroid Theory with Applications to Solid Modeling

Steve Pagano's Matroids and Signed Graphs

Lyle Ramshaw and Jim Saxe's report on Quadrangular Sets to the Budget Matroids

Neil White's page on Coxter Matroids and program to identify symplectic matroids

Thomas Zaslavsky's Matroid Miscellany

Günter M. Ziegler's dynamic survey of Oriented Matroids

 

Matroid Books

Barlotti, A., ed. (1982). Matroid theory and its applications. Liguori editore, Naples.

Björner, A., Las Vergnas, M., Strumfels, B., White, N., and Zeigler, G. M. (1989). Oriented matroids. Cambridge University Press, Cambridge.

Bonin, J., Oxley, J.G., Servatius, B., eds. (1996). Matroid Theory, Proceedings of the 1995 AMS-IMS-SIAM Joint Summer Research Conference. American Mathematical Society, Providence, RI.

Crapo, H. H. and Rota, G. C. (1970). On the foundations of combinatorial theory: Combinatorial geometries. M.I.T. Press, Cambridge, MA, RI.

Graver, E. J., Servatius, B., Servatius, H. (1993).Combinatorial Rigidity. American Mathematical Society, Providence, RI.

Korte, B. Lovász, L. and Schrader, R. (1991). Greedoids. Springer-Verlag, Berlin.

Kung, J. P. S. (1986). A source book in matroid theory. Birkhauser, Boston.

Lawler, E. (1992). Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York.

Lovász, L. and Recski, A., eds. (1985). Matroid theory. Colloquia Mathematica Societatis János Bolyai 40, North-Holland, Amsterdam.

Oxley, J. G. (1992). Matroid theory. Oxford University Press, New York.

Recski, A. (1989). Matroid theory and its applications in electrical network theory and in statics. Springer-Verlag, Berlin.

Robertson, N. and Seymour, P. D., eds. (1993). Graph Structure Theory, Proceedings of the 1991 AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors. American Mathematical Society, Providence, RI.

Truemper, K. (1992). Matroid decomposition. Academic Press, Boston.

Welsh, D. J. A. (1976). Matroid theory. Academic Press, London. [out of print]

White, N., ed. (1986). Theory of matroids. Cambridge University Press, Cambridge.

White, N., ed. (1987). Combinatorial geometries. Cambridge University Press, Cambridge.

White, N., ed. (1991). Matroid applications. Cambridge University Press, Cambridge.