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.
The uniform matroid is defined over a set of elements. A subset of the elements is independent if and only if it contains at most elements. A subset is a basis if it has exactly elements, and it is a circuit if it has exactly elements. The rank of a subset is and the rank of the matroid is .[1][2]
A matroid of rank is uniform if and only if all of its circuits have exactly elements.[3]
The matroid is called the -point line.
Duality and minors
The dual matroid of the uniform matroid is another uniform matroid . A uniform matroid is self-dual if and only if .[4]
Every minor of a uniform matroid is uniform. Restricting a uniform matroid by one element (as long as ) produces the matroid and contracting it by one element (as long as ) produces the matroid .[5]
Realization
The uniform matroid may be represented as the matroid of affinely independent subsets of points in general position in -dimensional Euclidean space, or as the matroid of linearly independent subsets of vectors in general position in an -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 -point line can be realized only over finite fields of or more elements (because otherwise the projective line over that field would have fewer than points): is not a binary matroid, 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 , a uniform matroid 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.
Not every uniform matroid is graphic, and the uniform matroids provide the smallest example of a non-graphic matroid, . The uniform matroid is the graphic matroid of an -edge dipole graph, and the dual uniform matroid is the graphic matroid of its dual graph, the -edge cycle graph. is the graphic matroid of a graph with self-loops, and is the graphic matroid of an -edge forest. Other than these examples, every uniform matroid with contains as a minor and therefore is not graphic.[13]
The -point line provides an example of a Sylvester matroid, a matroid in which every line contains three or more points.[14]
^Oxley, James G. (2006), "Example 1.2.7", Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 19, ISBN9780199202508. For the rank function, see p. 26.
^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.
uniform, matroid, mathematics, uniform, matroid, matroid, which, independent, sets, exactly, sets, containing, most, elements, some, fixed, integer, alternative, definition, that, every, permutation, elements, symmetry, contents, definition, duality, minors, r. 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 Contents 1 Definition 2 Duality and minors 3 Realization 4 Algorithms 5 Related matroids 6 See also 7 ReferencesDefinition EditThe uniform matroid U n r displaystyle U n r is defined over a set of n displaystyle n elements A subset of the elements is independent if and only if it contains at most r displaystyle r elements A subset is a basis if it has exactly r displaystyle r elements and it is a circuit if it has exactly r 1 displaystyle r 1 elements The rank of a subset S displaystyle S is min S r displaystyle min S r and the rank of the matroid is r displaystyle r 1 2 A matroid of rank r displaystyle r is uniform if and only if all of its circuits have exactly r 1 displaystyle r 1 elements 3 The matroid U n 2 displaystyle U n 2 is called the n displaystyle n point line Duality and minors EditThe dual matroid of the uniform matroid U n r displaystyle U n r is another uniform matroid U n n r displaystyle U n n r A uniform matroid is self dual if and only if r n 2 displaystyle r n 2 4 Every minor of a uniform matroid is uniform Restricting a uniform matroid U n r displaystyle U n r by one element as long as r lt n displaystyle r lt n produces the matroid U n 1 r displaystyle U n 1 r and contracting it by one element as long as r gt 0 displaystyle r gt 0 produces the matroid U n 1 r 1 displaystyle U n 1 r 1 5 Realization EditThe uniform matroid U n r displaystyle U n r may be represented as the matroid of affinely independent subsets of n displaystyle n points in general position in r displaystyle r dimensional Euclidean space or as the matroid of linearly independent subsets of n displaystyle n vectors in general position in an r 1 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 n displaystyle n point line U n 2 displaystyle U n 2 can be realized only over finite fields of n 1 displaystyle n 1 or more elements because otherwise the projective line over that field would have fewer than n displaystyle n points U 4 2 displaystyle U 4 2 is not a binary matroid U 5 2 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 EditThe 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 EditUnless r 0 n displaystyle r in 0 n a uniform matroid U n r 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 U 4 2 displaystyle U 4 2 The uniform matroid U n 1 displaystyle U n 1 is the graphic matroid of an n displaystyle n edge dipole graph and the dual uniform matroid U n n 1 displaystyle U n n 1 is the graphic matroid of its dual graph the n displaystyle n edge cycle graph U n 0 displaystyle U n 0 is the graphic matroid of a graph with n displaystyle n self loops and U n n displaystyle U n n is the graphic matroid of an n displaystyle n edge forest Other than these examples every uniform matroid U n r displaystyle U n r with 1 lt r lt n 1 displaystyle 1 lt r lt n 1 contains U 4 2 displaystyle U 4 2 as a minor and therefore is not graphic 13 The n 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 EditK set geometry References Edit Oxley James G 2006 Example 1 2 7 Matroid Theory Oxford Graduate Texts in Mathematics vol 3 Oxford University Press p 19 ISBN 9780199202508 For the rank function see p 26 Welsh D J A 2010 Matroid Theory Courier Dover Publications p 10 ISBN 9780486474397 Oxley 2006 p 27 Oxley 2006 pp 77 amp 111 Oxley 2006 pp 106 107 amp 111 a b Oxley 2006 p 100 Oxley 2006 pp 202 206 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 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 Oxley 2006 p 126 Oxley 2006 p 26 Oxley 2006 pp 48 49 Welsh 2010 p 30 Welsh 2010 p 297 Retrieved from https en wikipedia org w index php title Uniform matroid amp oldid 968361234, wikipedia, wiki, book, books, library,