In the mathematical theory of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s, 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 graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
s,
matrices
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
, and
field extension
In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...
s 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''.
* Let ''M'' be the
free matroid
In mathematics, the free matroid over a given ground-set ''E'' is the matroid in which the independent sets are all subsets of ''E''. It is a special case of a uniform matroid
In mathematics, a uniform matroid is a matroid in which the independ ...
, 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
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. ...
, 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
In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a ''capaci ...
: the elements of ''E'' are partitioned into categories, each category ''c'' has capacity ''k
c'', and the independent sets are those containing at most ''k
c'' elements of category ''c''. Then the rank function of ''M'' is: ''r''(''B'') = sum
''c'' min(''k
c'', , ''B
c'', ) where ''B
c'' is the subset ''B'' contained in category ''c''.
* Let ''M'' be a
graphic matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...
, where the independent sets are all the acyclic edge-sets (
forests
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
) of some fixed
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
''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).
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
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
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
,
.
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
for all
and
is the rank function of a matroid.
The above properties imply additional properties:
* If
, then
. That is, the rank is a
monotonic function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
.
*
.
Other matroid properties from rank
The rank function may be used to determine the other important properties of a matroid:
*A set is independent if and only if its rank equals its cardinality, and dependent if and only if it has greater cardinality than rank.
[, p. 25.]
*A nonempty set is a circuit if its cardinality equals one plus its rank and every subset formed by removing one element from the set has equal rank.
*A set is a basis if its rank equals both its cardinality and the rank of the matroid.
*A set is closed if it is
maximal for its rank, in the sense that there does not exist another element that can be added to it while maintaining the same rank.
*The difference
is called the nullity of the subset
. It is the minimum number of elements that must be removed from
to obtain an independent set.
*The corank of a subset
can refer to at least two different quantities: some authors use it to refer to the rank of
in the dual matroid,
, while other authors use corank to refer to the difference
.
Ranks of special matroids
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the
circuit rank
In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
(or cyclomatic number) of a graph is the corank of the associated
graphic matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...
; 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
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
of graph algorithms parameterized by this number.
In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
, the rank of a
linear matroid
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 repre ...
defined by
linear independence
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are ...
from the columns of a
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
is the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of the matrix, and it is also the
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
of the
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
spanned by the columns.
In
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
, the rank of a matroid defined from sets of elements in a
field extension
In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...
''L''/''K'' by
algebraic independence
In abstract algebra, a subset S of a field L is algebraically independent over a subfield K if the elements of S do not satisfy any non-trivial polynomial equation with coefficients in K.
In particular, a one element set \ is algebraically in ...
is known as the
transcendence degree
In abstract algebra, the transcendence degree of a field extension ''L'' / ''K'' is a certain rather coarse measure of the "size" of the extension. Specifically, it is defined as the largest cardinality of an algebraically independent subset of ...
.
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
Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole ...
. If the utility function of the agent is an MRF, it means that:
* The agent's utility has
diminishing returns
In economics, diminishing returns are the decrease in marginal (incremental) output of a production process as the amount of a single factor of production is incrementally increased, holding all other factors of production equal ( ceteris paribu ...
(this follows from the fact that the MRF is a submodular function);
* The agent's marginal utility for each item is dichotomous (binary) - either 0 or 1. That is, adding an item to a bundle either adds no utility, or adds a utility of 1.
The following solutions are known for this setting:
* Babaioff, Ezra and Feige design a deterministic polynomial-time
truthful mechanism In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about ...
called Prioritized Egalitarian, that outputs a Lorenz dominating allocation, which is consequently also EFX
0, maximizes the product of utilities, attains 1/2-fraction
maximin share
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into ''n'' parts and taking the part with th ...
, and attains the full maximin share when the valuations are additive. With random priorities, this mechanism is also ex-ante
envy-free Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by a ...
. They also study ''e''-dichotomous valuations, in which the marginal utility is either non-positive or in the range
,1+''e''
* Benabbou, Chakraborty, Igarashi and Zick
show that, in this setting, every
Pareto-optimal
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engine ...
allocation maximizes the sum of utilities (the ''utilitarian welfare''), the set of allocations that maximize a symmetric strictly-
concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap, or upper convex.
Definition
A real-valued function f on an in ...
''f'' over all max-sum allocations does not depend on the choice of ''f'', and all these ''f''-maximizing allocations are EF1. This implies that the max-product allocations are the
leximin-optimal allocations, and they are all max-sum and EF1. They also present a polynomial-time algorithm that computes a max-sum and EF1 allocation (which does not necessarily maximize a concave function), and a polynomial-time algorithm that maximizes a concave function for the special case of MRFs based on
maximum-cardinality matching in bipartite graphs.
The matroid-rank functions are a subclass of the
gross substitute valuations.
See also
*
Rank oracle
References
{{reflist, 2
Dimension
Rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...