# Uniform matroid

In mathematics, a uniform matroid is a matroid in which every permutation of the elements is a symmetry.

## Definition

A matroid of rank $r$ is uniform if and only if all of its circuits have exactly $r+1$ elements.

## Realization

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 $n$ -point line $U{}_{n}^{2}$ can be realized only over finite fields of $n-1$ or more elements (because otherwise the projective line over that field would have fewer than $n$ points): $U{}_{4}^{2}$ is not a binary matroid, $U{}_{5}^{2}$ 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.

## Algorithms

The problem of finding the minimum-weight basis of a weighted uniform matroid is well-studied in computer science as the selection problem. It may be solved in linear time.

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.

## Related matroids

Unless $r\in \{0,n\}$ , a uniform matroid $U{}_{n}^{r}$ 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.

Every uniform matroid is a paving matroid, a transversal matroid and a strict gammoid.

The $n$ -point line provides an example of a Sylvester matroid, a matroid in which every line contains three or more points.