Matroid Miscellany

by Thomas Zaslavsky

Sources

A list of places where you can get introduced to matroid theory at any level you wish.

Problems

Some open problems.

• Steve Pagano's Matroids page.

Short technical introductionss:

• Robin J. Wilson, "An introduction to matroid theory", American Mathematical Monthly Vol. 80 (1973), pp. 500-525.
• Robin J. Wilson, "Matroid theory", Ch. 9 of Introduction to Graph Theory, Academic Press, New York-London, 1972; 2nd edn., Academic Press, New York-London, 1979; 3rd edn., Longman, London, and Wiley, New York, 1985. Translated into Russian (1977; 1st edn.) and Polish (1985; 2nd edn.).

For a thorough introduction:

• James Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.
  The best introductory book. An exceptionally fine textbook. It doesn't cover everything (which would have been impossible); see the next two items for articles that make up the major omission.
• Thomas Zaslavsky, "The Möbius function and the characteristic polynomial", Ch. 7 in: White, Theory of Matroids.
  Introduces an important aspect omitted by Oxley.
• Thomas Brylawski and James Oxley, "The Tutte polynomial and its applications", Ch. 6 in: White, Matroid Applications.
  Much more of the same important aspect omitted by Oxley, extending Zaslavsky's chapter.
• Henry Crapo, "Examples and basic concepts", Ch. 1 in: White, Theory of Matroids.
• Georgio Nicoletti and Neil White, "Axiom systems", Ch. 2 in: White, Theory of Matroids.
  An overview of many of the multiplicity of "cryptomorphisms" (equivalent but seemingly wildly different ways to define matroids); an antidote to the "Let (E, X) be a matroid" style of pseudo-definition.

• Joseph P.S. Kung, "Extremal matroid theory", in: Neil Robertson and Paul Seymour, eds., Graph Structure Theory (Proc. Conf., Seattle, 1991), pp. 21-61. Contemporary Math., Vol. 147. American Mathematical Society, Providence, R.I., 1993.
  The founding paper.
• Joseph P.S. Kung, "Critical problems", in: Joseph E. Bonin, James G. Oxley, and Brigitte Servatius, eds., Matroid Theory (Proc. Conf, Seattle, 1995), pp. 1-127. Contemporary Math., Vol. 197. American Mathematical Society, Providence, R.I., 1996.
  Extremely thorough.
• Neil White, ed., Theory of Matroids, Cambridge University Press, Cambridge, 1986.
• Neil White, ed., Combinatorial Geometries, Cambridge University Press, Cambridge, 1987.
  Special topics and special types of matroids.
• Neil White, ed., Matroid Applications, Cambridge University Press, Cambridge, 1992. Highly specialized topics, except for Ch. 6 (see above). Most important:
  Anders Björner, "Homology and shellability of matroids and geometric lattices", Ch. 7;
  Anders Björner and Günter M. Ziegler, "Introduction to greedoids", Ch. 8.
• D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
  A thorough survey of the state of the theory at that time; out of date but still a valuable reference, not superseded.

• Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented Matroids, Cambridge University Press, Cambridge, 1993.
  To students of oriented matroids, this is The Book.

Best Viewed With Any Browser

Last modified 2001 Aug 23
My home page.