Matroid rank

The graphic matroid of a forest with 4 edges, which is the free matroid with a ground set of size 4 (also the uniform matroid $U{}_{4}^{4}$).

The rank of the given matroid is 4, the size of its largest independent set. As this matroid is a member of the graphic, free, and uniform matroid families, rank functions can be used to calculate the rank of the matroid, specifically $r(B)=|B|$ as a free matroid, $r(B)=\min(k,|B|)$ as a uniform matroid, and the number of vertices in the graph, minus the number of connected components of $B$ (including single-vertex components), as a graphic matroid.

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.