Matroid rank

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.
Examples.
In all examples, "E" is the base set of the matroid, and "B" is some subset of "E".
Properties and axiomatization.
The rank function of a matroid obeys the following properties.
(R1) The value of the rank function is always a non-negative integer.
(R2) For any two subsets formula_1 and formula_2 of formula_3, formula_4. That is, the rank is a submodular set function.
(R3) For any set formula_1 and element formula_6, formula_7.
These properties may be used as axioms to characterize the rank function of matroids: every integer-valued submodular set function on the subsets of a finite set that obeys the inequalities formula_7 for all formula_1 and formula_6 is the rank function of a matroid.
The above properties imply additional properties:
Other matroid properties from rank.
The rank function may be used to determine the other important properties of a matroid:
Ranks of special matroids.
In graph theory, the circuit rank (or cyclomatic number) of a graph is the corank of the associated graphic matroid; it measures the minimum number of edges that must be removed from the graph to make the remaining edges form a forest. Several authors have studied the parameterized complexity of graph algorithms parameterized by this number.
In linear algebra, the rank of a linear matroid defined by linear independence from the columns of a matrix is the rank of the matrix, and it is also the dimension of the vector space spanned by the columns.
In abstract algebra, the rank of a matroid defined from sets of elements in a field extension "L"/"K" by algebraic independence is known as the transcendence degree.
Matroid rank functions as utility functions.
Matroid rank functions (MRF) has been used to represent utility functions of agents in problems of fair item allocation. If the utility function of the agent is an MRF, it means that:
The following solutions are known for this setting:
The matroid-rank functions are a subclass of the gross substitute valuations.