Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Matroid rank
Summary
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.
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 kc, and the independent sets are those containing at most kc elements of category c. Then the rank function of M is: r(B) = sumc min(kc, |Bc|) where Bc 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).
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 and of , . That is, the rank is a submodular set function.
(R3) For any set and element , .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.