View source for Five-limit tuning

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

==Definition==
The uniform matroid <math>U{}^r_n</math> is defined over a set of <math>n</math> elements. A subset of the elements is independent if and only if it contains at most <math>r</math> elements. A subset is a basis if it has exactly <math>r</math> elements, and it is a circuit if it has exactly <math>r+1</math> elements. The [[matroid rank|rank]] of a subset <math>S</math> is <math>\min(|S|,r)</math> and the rank of the matroid is <math>r</math>.<ref>{{citation
 | last = Oxley | first = James G. | authorlink = James Oxley
 | contribution = Example 1.2.7
 | isbn = 9780199202508
 | page = 19
 | publisher = Oxford University Press
 | series = Oxford Graduate Texts in Mathematics
 | title = Matroid Theory
 | volume = 3
 | year = 2006}}. For the rank function, see p. 26.</ref><ref>{{citation
 | last = Welsh | first = D. J. A. | authorlink = Dominic Welsh
 | isbn = 9780486474397
 | page = 10
 | publisher = Courier Dover Publications
 | title = Matroid Theory
 | year = 2010}}.</ref>

A matroid of rank <math>r</math> is uniform if and only if all of its circuits have exactly <math>r+1</math> elements.<ref>{{harvtxt|Oxley|2006}}, p. 27.</ref>

The matroid <math>U{}^2_n</math> is called the '''<math>n</math>-point line'''.

==Duality and minors==
The [[dual matroid]] of the uniform matroid <math>U{}^r_n</math> is another uniform matroid <math>U{}^{n-r}_n</math>. A uniform matroid is self-dual if and only if <math>r=n/2</math>.<ref>{{harvtxt|Oxley|2006}}, pp. 77 & 111.</ref>

Every [[matroid minor|minor]] of a uniform matroid is uniform. Restricting a uniform matroid <math>U{}^r_n</math> by one element (as long as <math>r < n</math>) produces the matroid
<math>U{}^r_{n-1}</math> and contracting it by one element (as long as <math>r > 0</math>) produces the matroid <math>U{}^{r-1}_{n-1}</math>.<ref>{{harvtxt|Oxley|2006}}, pp. 106–107 & 111.</ref>

==Realization==
The uniform matroid <math>U{}^r_n</math> may be [[Matroid representation|represented]] as the matroid of affinely independent subsets of <math>n</math> points in [[general position]] in <math>r</math>-dimensional [[Euclidean space]], or as the matroid of linearly independent subsets of <math>n</math> vectors in general position in an <math>(r+1)</math>-dimensional real [[vector space]].

Every uniform matroid may also be realized in [[projective space]]s and vector spaces over all sufficiently large [[finite field]]s.<ref name="Ox100"/> However, the field must be large enough to include enough independent vectors. For instance, the <math>n</math>-point line <math>U{}^2_n</math> can be realized only over finite fields of <math>n-1</math> or more elements (because otherwise the projective line over that field would have fewer than <math>n</math> points): <math>U{}^2_4</math> is not a [[binary matroid]], <math>U{}^2_5</math> is not a ternary matroid, etc. For this reason, uniform matroids play an important role in [[Rota's conjecture]] concerning the [[matroid minor|forbidden minor]] characterization of the matroids that can be realized over finite fields.<ref>{{harvtxt|Oxley|2006}}, pp. 202–206.</ref>

==Algorithms==
The problem of finding the minimum-weight basis of a [[weighted matroid|weighted]] uniform matroid is well-studied in computer science as the [[Selection algorithm|selection problem]]. It may be solved in [[linear time]].<ref>{{citation
 | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
 | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
 | last3 = Rivest | first3 = Ronald L. | author3-link = Ron Rivest
 | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein
 | contribution = Chapter 9: Medians and Order Statistics
 | edition = 2nd
 | isbn = 0-262-03293-7
 | pages = 183–196
 | publisher = MIT Press and McGraw-Hill
 | title = [[Introduction to Algorithms]]
 | year = 2001}}.</ref>

Any algorithm that tests whether a given matroid is uniform, given access to the matroid via an [[matroid oracle|independence oracle]], must perform an exponential number of oracle queries, and therefore cannot take polynomial time.<ref>{{citation
 | last1 = Jensen | first1 = Per M.
 | last2 = Korte | first2 = Bernhard
 | doi = 10.1137/0211014
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 646772
 | pages = 184–190
 | title = Complexity of matroid property algorithms
 | volume = 11
 | year = 1982}}.</ref>

==Related matroids==
Unless <math>r\in\{0,n\}</math>, a uniform matroid <math>U{}^r_n</math> is connected: it is not the direct sum of two smaller matroids.<ref>{{harvtxt|Oxley|2006}}, p. 126.</ref>
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]],<ref name=Ox26>{{harvtxt|Oxley|2006|p=26}}.</ref> a [[transversal matroid]]<ref>{{harvtxt|Oxley|2006}}, pp. 48–49.</ref> and a [[gammoid|strict gammoid]].<ref name="Ox100">{{harvtxt|Oxley|2006}}, p. 100.</ref>

Not every uniform matroid is [[graphic matroid|graphic]], and the uniform matroids provide the smallest example of a non-graphic matroid, <math>U{}^2_4</math>. The uniform matroid <math>U{}^1_n</math> is the graphic matroid of an <math>n</math>-edge [[dipole graph]], and the dual uniform matroid <math>U{}^{n-1}_n</math> is the graphic matroid of its [[dual graph]], the <math>n</math>-edge [[cycle graph]]. <math>U{}^0_n</math> is the graphic matroid of a graph with <math>n</math> self-loops, and <math>U{}^n_n</math> is the graphic matroid of an <math>n</math>-edge [[tree (graph theory)|forest]]. Other than these examples, every uniform matroid <math>U{}^r_n</math> with <math>1 < r < n-1</math> contains <math>U{}^2_4</math> as a minor and therefore is not graphic.<ref>{{harvtxt|Welsh|2010}}, p. 30.</ref>

The <math>n</math>-point line provides an example of a [[Sylvester matroid]], a matroid in which every line contains three or more points.<ref>{{harvtxt|Welsh|2010}}, p. 297.</ref>

==See also==
*[[K-set (geometry)]]

==References==
{{reflist|colwidth=30em}}

[[Category:Matroid theory]]