In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.
The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. Matroid rank functions form an important subclass of the submodular set functions. The rank functions of matroids defined from certain other types of mathematical object such as undirected graphs, matrices, and field extensions are important within the study of those objects.
In all examples, E is the base set of the matroid, and B is some subset of E.
Let M be the free matroid, where the independent sets are all subsets of E. Then the rank function of M is simply: r(B) = |B|.
Let M be a uniform matroid, where the independent sets are the subsets of E with at most k elements, for some integer k. Then the rank function of M is: r(B) = min(k, |B|).
Let M be a partition matroid: the elements of E are partitioned into categories, each category c has capacity kc, and the independent sets are those containing at most kc elements of category c. Then the rank function of M is: r(B) = sumc min(kc, |Bc|) where Bc is the subset B contained in category c.
Let M be a graphic matroid, where the independent sets are all the acyclic edge-sets (forests) of some fixed undirected graph G. Then the rank function r(B) is the number of vertices in the graph, minus the number of connected components of B (including single-vertex components).
The rank function of a matroid obeys the following properties.
(R1) The value of the rank function is always a non-negative integer and the rank of the empty set is 0.
(R2) For any two subsets and of , . That is, the rank is a submodular set function.
(R3) For any set and element , .
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
In abstract algebra, a subset of a field is algebraically independent over a subfield if the elements of do not satisfy any non-trivial polynomial equation with coefficients in . In particular, a one element set is algebraically independent over if and only if is transcendental over . In general, all the elements of an algebraically independent set over are by necessity transcendental over , and over all of the field extensions over generated by the remaining elements of .
In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished manuscript in 1968. The Vámos matroid has eight elements, which may be thought of as the eight vertices of a cube or cuboid. The matroid has rank 4: all sets of three or fewer elements are independent, and 65 of the 70 possible sets of four elements are also independent.
In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra. A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F.
A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
EPFL2022
, ,
This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and ...
We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...