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.

• 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 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, 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).

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 and the rank of the empty set is 0.

(R2) For any two subsets ${\displaystyle A}$ and ${\displaystyle B}$ of ${\displaystyle E}$, ${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$. That is, the rank is a submodular set function.

(R3) For any set ${\displaystyle A}$ and element ${\displaystyle x}$, ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$.

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 ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$ for all ${\displaystyle A}$ and ${\displaystyle x}$ is the rank function of a matroid. ^{[1] [2]}

The above properties imply additional properties:

• If ${\displaystyle A\subset B\subset E}$, then ${\displaystyle r(A)\leq r(B)\leq r(E)}$. That is, the rank is a monotonic function.
• ${\displaystyle r(A)\leq |A|}$.

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. ^[3]
• 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. ^[3]
• A set is a basis if its rank equals both its cardinality and the rank of the matroid. ^[3]
• 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 ${\displaystyle |A|-r(A)}$ is called the nullity of the subset ${\displaystyle A}$. It is the minimum number of elements that must be removed from ${\displaystyle A}$ to obtain an independent set. ^[4]
• The corank of a subset ${\displaystyle A}$ can refer to at least two different quantities: some authors use it to refer to the rank of ${\displaystyle A}$ in the dual matroid, ${\displaystyle r^{*}(A)=|A|+r(E\setminus A)-r(E)}$, while other authors use corank to refer to the difference ${\displaystyle r(E)-r(A)}$.

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. ^[5] Several authors have studied the parameterized complexity of graph algorithms parameterized by this number. ^{[6] [7]}

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, ^[8] 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. ^[9]

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 agent's utility has diminishing returns (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 ^[10] design a deterministic polynomial-time truthful mechanism called Prioritized Egalitarian, that outputs a Lorenz dominating allocation, which is consequently also EFX₀, maximizes the product of utilities, attains 1/2-fraction maximin share, and attains the full maximin share when the valuations are additive. With random priorities, this mechanism is also ex-ante envy-free. They also study e-dichotomous valuations, in which the marginal utility is either non-positive or in the range [1,1+e].
• Benabbou, Chakraborty, Igarashi and Zick ^[11] show that, in this setting, every Pareto-optimal allocation maximizes the sum of utilities (the utilitarian welfare), the set of allocations that maximize a symmetric strictly-concave function 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

1. Shikare, M. M.; Waphare, B. N. (2004), Combinatorial Optimization, Alpha Science Int'l Ltd., p. 155, ISBN   9788173195600 .
2. Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 8, ISBN   9780486474397 .
3. Oxley (2006), p. 25.
4. Oxley (2006), p. 34.
5. Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27–30, ISBN   9780486419756 .
6. Coppersmith, Don; Vishkin, Uzi (1985), "Solving NP-hard problems in 'almost trees': Vertex cover", Discrete Applied Mathematics, 10 (1): 27–45, doi: 10.1016/0166-218X(85)90057-5 , Zbl   0573.68017 .
7. Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), "Fixed-parameter complexity of λ-labelings", Discrete Applied Mathematics, 113 (1): 59–72, doi: 10.1016/S0166-218X(00)00387-5 , Zbl   0982.05085 .
8. Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 81, ISBN   9780199202508 .
9. Lindström, B. (1988), "Matroids, algebraic and non-algebraic", Algebraic, extremal and metric combinatorics, 1986 (Montreal, PQ, 1986), London Math. Soc. Lecture Note Ser., vol. 131, Cambridge: Cambridge Univ. Press, pp. 166–174, MR   1052666 .
10. Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2020-07-27). "Fair and Truthful Mechanisms for Dichotomous Valuations". arXiv: 2002.10704 [cs.GT].
11. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). Finding Fair and Efficient Allocations When Valuations Don't Add Up. Lecture Notes in Computer Science. Vol. 12283. pp. 32–46. arXiv: 2003.07060 . doi:10.1007/978-3-030-57980-7_3. ISBN   978-3-030-57979-1. S2CID   208328700.