uniform matroid

The uniform matroid $U\{\}^r\_n$ 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 $\backslash min(|S|,r)$ and the rank of the matroid is $r$.{{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.{{citation

| last = Welsh | first = D. J. A. | authorlink = Dominic Welsh

| isbn = 9780486474397

| page = 10

| publisher = Courier Dover Publications

| title = Matroid Theory

| year = 2010}}.

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

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

The dual matroid of the uniform matroid $U\{\}^r\_n$ is another uniform matroid $U\{\}^\{n-r\}\_n$. A uniform matroid is self-dual if and only if $r=n/2$.{{harvtxt|Oxley|2006}}, pp. 77 & 111.

Every minor of a uniform matroid is uniform. Restricting a uniform matroid $U\{\}^r\_n$ by one element (as long as ) produces the matroid

$U\{\}^r\_\{n-1\}$ and contracting it by one element (as long as $r\; >\; 0$) produces the matroid $U\{\}^\{r-1\}\_\{n-1\}$.{{harvtxt|Oxley|2006}}, pp. 106–107 & 111.

The uniform matroid $U\{\}^r\_n$ 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. However, the field must be large enough to include enough independent vectors. For instance, the $n$-point line $U\{\}^2\_n$ 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\{\}^2\_4$ is not a binary matroid, $U\{\}^2\_5$ 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.{{harvtxt|Oxley|2006}}, pp. 202–206.

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.{{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}}.

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.{{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}}.

The free matroid over a given ground-set {{mvar|E}} is the matroid in which the independent sets are all subsets of {{mvar|E}}. It is a special case of a uniform matroid; specifically, when {{mvar|E}} has cardinality $n$, it is the uniform matroid $U\{\}^\{n\}\_\{n\}$.{{harvtxt|Oxley|2006}}, pp. 17.

Unless $r\backslash in\backslash \{0,n\backslash \}$, a uniform matroid $U\{\}^r\_n$ is connected: it is not the direct sum of two smaller matroids.{{harvtxt|Oxley|2006}}, p. 126.

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,{{harvtxt|Oxley|2006|p=26}}. a transversal matroid{{harvtxt|Oxley|2006}}, pp. 48–49. and a strict gammoid.{{harvtxt|Oxley|2006}}, p. 100.

Not every uniform matroid is graphic, and the uniform matroids provide the smallest example of a non-graphic matroid, $U\{\}^2\_4$. The uniform matroid $U\{\}^1\_n$ is the graphic matroid of an $n$-edge dipole graph, and the dual uniform matroid $U\{\}^\{n-1\}\_n$ is the graphic matroid of its dual graph, the $n$-edge cycle graph. $U\{\}^0\_n$ 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\{\}^r\_n$ with contains $U\{\}^2\_4$ as a minor and therefore is not graphic.

The $n$-point line provides an example of a Sylvester matroid, a matroid in which every line contains three or more points.{{harvtxt|Welsh|2010}}, p. 297.

• K-set (geometry)
• Eulerian matroid

{{reflist|colwidth=30em}}

Category:Matroid theory