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.)

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.T

utte, 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.