Uniform matroid explained
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
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. 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.
[6] 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.[7]
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.[8]
Related matroids
Unless
, a uniform matroid
is connected: it is not the direct sum of two smaller matroids.
[9] 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,[10] a transversal matroid[11] and a strict gammoid.[12]
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] See also
Notes and References
- . For the rank function, see p. 26.
- .
- , p. 27.
- , pp. 77 & 111.
- , pp. 106–107 & 111.
- , pp. 202–206.
- .
- .
- , p. 126.
- .
- , pp. 48–49.
- , p. 100.
- , p. 30.
- , p. 297.