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.
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]
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]
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]
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.
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, . 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]
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.
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]
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]
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]
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.
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, . 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]