Uniform matroid

In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most r elements, for some fixed integer r. An alternative definition is that every permutation of the elements is a symmetry.

The uniform matroid $U{}_{n}^{r}$ is defined over a set of $n$ elements. A subset of the elements is independent if and only if it contains at most $r$ elements. A subset is a basis if it has exactly $r$ elements, and it is a circuit if it has exactly $r+1$ elements. The rank of a subset $S$ is $\min(|S|,r)$ and the rank of the matroid is $r$ .^[2]^[3]

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

The matroid $U{}_{n}^{2}$ is called the $n$ -point line.

Duality and minors

The dual matroid of the uniform matroid $U{}_{n}^{r}$ is another uniform matroid $U{}_{n}^{n-r}$ . A uniform matroid is self-dual if and only if $r=n/2$ .^[5]

Every minor of a uniform matroid is uniform. Restricting a uniform matroid $U{}_{n}^{r}$ by one element (as long as $r<n$ ) produces the matroid $U{}_{n-1}^{r}$ and contracting it by one element (as long as $r>0$ ) produces the matroid $U{}_{n-1}^{r-1}$ .^[6]

Realization

The uniform matroid $U{}_{n}^{r}$ may be represented as the matroid of affinely independent subsets of $n$ points in general position in $r$ -dimensional Euclidean space, or as the matroid of linearly independent subsets of $n$ vectors in general position in an $(r+1)$ -dimensional real vector space.

Every uniform matroid may also be realized in projective spaces and vector spaces over all sufficiently large finite fields.^[7] 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.^[8]

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.^[9]

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.^[10]

Related matroids

The free matroid over a given ground-set $E$ is the matroid in which the independent sets are all subsets of $E$ . It is a special case of a uniform matroid; specifically, when $E$ has cardinality $n$ , it is the uniform matroid $U{}_{n}^{n}$ .^[11]

Unless $r\in \{0,n\}$ , a uniform matroid $U{}_{n}^{r}$ is connected: it is not the direct sum of two smaller matroids.^[12] 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,^[13] a transversal matroid^[14] and a strict gammoid.^[7]

Not every uniform matroid is graphic, and the uniform matroids provide the smallest example of a non-graphic matroid, $U{}_{4}^{2}$ . The uniform matroid $U{}_{n}^{1}$ is the graphic matroid of an $n$ -edge dipole graph, and the dual uniform matroid $U{}_{n}^{n-1}$ is the graphic matroid of its dual graph, the $n$ -edge cycle graph. $U{}_{n}^{0}$ is the graphic matroid of a graph with $n$ self-loops, and $U{}_{n}^{n}$ is the graphic matroid of an $n$ -edge forest. Other than these examples, every uniform matroid $U{}_{n}^{r}$ with $1<r<n-1$ contains $U{}_{4}^{2}$ as a minor and therefore is not graphic.^[1]

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

Duality and minors

Realization

Algorithms

Related matroids

See also

References

Related Articles