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.

Definition

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

A matroid of rank ${\displaystyle r}$ is uniform if and only if all of its circuits have exactly ${\displaystyle r+1}$ elements. ^[3]

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

Duality and minors

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

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

Realization

The uniform matroid ${\displaystyle U{}_{n}^{r}}$ may be represented as the matroid of affinely independent subsets of ${\displaystyle n}$ points in general position in ${\displaystyle r}$-dimensional Euclidean space, or as the matroid of linearly independent subsets of ${\displaystyle n}$ vectors in general position in an ${\displaystyle (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. ^[6] However, the field must be large enough to include enough independent vectors. For instance, the ${\displaystyle n}$-point line ${\displaystyle U{}_{n}^{2}}$ can be realized only over finite fields of ${\displaystyle n-1}$ or more elements (because otherwise the projective line over that field would have fewer than ${\displaystyle n}$ points): ${\displaystyle U{}_{4}^{2}}$ is not a binary matroid, ${\displaystyle 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. ^[7]

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

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

Related matroids

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

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

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

See also

• K-set (geometry)

References

1. 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.
2. Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 10, ISBN   9780486474397 .
3. Oxley (2006), p. 27.
4. Oxley (2006), pp. 77 & 111.
5. Oxley (2006), pp. 106–107 & 111.
6. Oxley (2006), p. 100.
7. Oxley (2006), pp. 202–206.
8. 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 .
9. Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms", SIAM Journal on Computing , 11 (1): 184–190, doi:10.1137/0211014, MR   0646772 .
10. Oxley (2006), p. 126.
11. Oxley (2006 , p. 26).
12. Oxley (2006), pp. 48–49.
13. Welsh (2010), p. 30.
14. Welsh (2010), p. 297.