Uniform matroid

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Definition[edit]

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 \min(|S|,r) and the rank of the matroid is r.[1][2]

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

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

Duality and minors[edit]

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.[4]

Every minor of a uniform matroid is uniform. Restricting a uniform matroid U{}^r_n by one element (as long as r < n) 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}.[5]

Realization[edit]

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.[6] 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.[7]

Algorithms[edit]

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[edit]

Unless r\in\{0,n\}, a uniform matroid U{}^r_n 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, 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 1 < r < n-1 contains U{}^2_4 as a minor and therefore is not graphic.[13]

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

See also[edit]

References[edit]

  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. ^ a b 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 646772 .
  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.