Matroid

A matroid is, roughly speaking, 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 matroid circuit is a matroid circuit,

2. If and , then contains a matroid 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 inclusion-maximal independent sets contained in have the same number of elements.

(Harary 1994, pp. 40-41).

For a finite matroid, a cyclic basis ordering is a cyclic order of its ground set in which every window of matroid rank length is a matroid basis. The Kajitani-Ueno-Miyano conjecture asserts that these orderings exist exactly for uniformly dense matroids (Kajitani et al. 1988).

Up to isomorphism, the numbers of simple matroids (or combinatorial geometries) with , 1, ... points are 1, 1, 1, 2, 4, 9, 26, 101, 950, ... (OEIS A002773), and the numbers 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.)

A basic example is the uniform matroid , whose independent sets are precisely the subsets of an -element ground set of size at most . Parallel thickenings of these matroids provide explicit counterexamples to the multiplicative Merino-Welsh conjecture for matroids (Chen et al. 2026).