Uniform matroid

From HandWiki
Short description: Matroid in which every permutation is a symmetry

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 [math]\displaystyle{ U{}^r_n }[/math] is defined over a set of [math]\displaystyle{ n }[/math] elements. A subset of the elements is independent if and only if it contains at most [math]\displaystyle{ r }[/math] elements. A subset is a basis if it has exactly [math]\displaystyle{ r }[/math] elements, and it is a circuit if it has exactly [math]\displaystyle{ r+1 }[/math] elements. The rank of a subset [math]\displaystyle{ S }[/math] is [math]\displaystyle{ \min(|S|,r) }[/math] and the rank of the matroid is [math]\displaystyle{ r }[/math].[1][2]

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

The matroid [math]\displaystyle{ U{}^2_n }[/math] is called the [math]\displaystyle{ n }[/math]-point line.

Duality and minors

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

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

Realization

The uniform matroid [math]\displaystyle{ U{}^r_n }[/math] may be represented as the matroid of affinely independent subsets of [math]\displaystyle{ n }[/math] points in general position in [math]\displaystyle{ r }[/math]-dimensional Euclidean space, or as the matroid of linearly independent subsets of [math]\displaystyle{ n }[/math] vectors in general position in an [math]\displaystyle{ (r+1) }[/math]-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 [math]\displaystyle{ n }[/math]-point line [math]\displaystyle{ U{}^2_n }[/math] can be realized only over finite fields of [math]\displaystyle{ n-1 }[/math] or more elements (because otherwise the projective line over that field would have fewer than [math]\displaystyle{ n }[/math] points): [math]\displaystyle{ U{}^2_4 }[/math] is not a binary matroid, [math]\displaystyle{ 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 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 [math]\displaystyle{ r\in\{0,n\} }[/math], a uniform matroid [math]\displaystyle{ U{}^r_n }[/math] 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, [math]\displaystyle{ U{}^2_4 }[/math]. The uniform matroid [math]\displaystyle{ U{}^1_n }[/math] is the graphic matroid of an [math]\displaystyle{ n }[/math]-edge dipole graph, and the dual uniform matroid [math]\displaystyle{ U{}^{n-1}_n }[/math] is the graphic matroid of its dual graph, the [math]\displaystyle{ n }[/math]-edge cycle graph. [math]\displaystyle{ U{}^0_n }[/math] is the graphic matroid of a graph with [math]\displaystyle{ n }[/math] self-loops, and [math]\displaystyle{ U{}^n_n }[/math] is the graphic matroid of an [math]\displaystyle{ n }[/math]-edge forest. Other than these examples, every uniform matroid [math]\displaystyle{ U{}^r_n }[/math] with [math]\displaystyle{ 1 \lt r \lt n-1 }[/math] contains [math]\displaystyle{ U{}^2_4 }[/math] as a minor and therefore is not graphic.[13]

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

See also

References

  1. ↑ "Example 1.2.7", Matroid Theory, Oxford Graduate Texts in Mathematics, 3, Oxford University Press, 2006, p. 19, ISBN 9780199202508 . For the rank function, see p. 26.
  2. ↑ Matroid Theory, Courier Dover Publications, 2010, p. 10, ISBN 9780486474397 .
  3. ↑ (Oxley 2006), p. 27.
  4. ↑ (Oxley 2006), pp. 77 & 111.
  5. ↑ (Oxley 2006), pp. 106–107 & 111.
  6. ↑ 6.0 6.1 (Oxley 2006), p. 100.
  7. ↑ (Oxley 2006), pp. 202–206.
  8. ↑ "Chapter 9: Medians and Order Statistics", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, 2001, 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 .
  10. ↑ (Oxley 2006), p. 126.
  11. ↑ (Oxley 2006).
  12. ↑ (Oxley 2006), pp. 48–49.
  13. ↑ (Welsh 2010), p. 30.
  14. ↑ (Welsh 2010), p. 297.



Retrieved from "https://handwiki.org/wiki/index.php?title=Uniform_matroid&oldid=2355900"