The uniform matroid is defined over a set of elements. A subset of the elements is independent if and only if it contains at most elements. A subset is a basis if it has exactly elements, and it is a circuit if it has exactly elements. The rank of a subset is and the rank of the matroid is .
A matroid of rank is uniform if and only if all of its circuits have exactly elements.
The matroid is called the -point line.
Duality and minors
The uniform matroid may be represented as the matroid of affinely independent subsets of points in general position in -dimensional Euclidean space, or as the matroid of linearly independent subsets of vectors in general position in an -dimensional real vector space.
Every uniform matroid may also be realized in projective spaces and vector spaces over all sufficiently large finite fields. However, the field must be large enough to include enough independent vectors. For instance, the -point line can be realized only over finite fields of or more elements (because otherwise the projective line over that field would have fewer than points): is not a binary matroid, is not a ternary matroid, etc. For this reason, uniform matroids play an important role in Rota's conjecture concerning the forbidden minor characterization of the matroids that can be realized over finite fields.
Any algorithm that tests whether a given matroid is uniform, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.
Unless , a uniform matroid is connected: it is not the direct sum of two smaller matroids. The direct sum of a family of uniform matroids (not necessarily all with the same parameters) is called a partition matroid.
Not every uniform matroid is graphic, and the uniform matroids provide the smallest example of a non-graphic matroid, . The uniform matroid is the graphic matroid of an -edge dipole graph, and the dual uniform matroid is the graphic matroid of its dual graph, the -edge cycle graph. is the graphic matroid of a graph with self-loops, and is the graphic matroid of an -edge forest. Other than these examples, every uniform matroid with contains as a minor and therefore is not graphic.
- Oxley, James G. (2006), "Example 1.2.7", Matroid Theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, p. 19, ISBN 9780199202508. For the rank function, see p. 26.
- Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 10, ISBN 9780486474397.
- Oxley (2006), p. 27.
- Oxley (2006), pp. 77 & 111.
- Oxley (2006), pp. 106–107 & 111.
- Oxley (2006), p. 100.
- Oxley (2006), pp. 202–206.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Chapter 9: Medians and Order Statistics", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 183–196, ISBN 0-262-03293-7.
- Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing, 11 (1): 184–190, doi:10.1137/0211014, MR 646772.
- Oxley (2006), p. 126.
- Oxley (2006, p. 26).
- Oxley (2006), pp. 48–49.
- Welsh (2010), p. 30.
- Welsh (2010), p. 297.