Matroid Rank Function
Jump to navigation
Jump to search
A Matroid Rank Function is a matroid function that is a Rank Function (that returns the maximum size of an independent set in the matroid).
- See: Submodular Function, Column Vector Index, Matroid, Submodular Set Function, Undirected Graph, Matrix (Mathematics), Field Extension.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/matroid_rank Retrieved:2015-1-26.
- 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. The rank functions of matroids form an important subclass of the submodular set functions, and the rank functions of the 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 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.