Rank (Matroid)

Definition

Rank (Matroid)

The rank of a matroid is defined as the cardinality of any basis of , i.e.,

Submodularity

Submodularity

Let be a finite matroid with rank function . For all ,

Submodularity

Fix . We construct one independent set in whose intersection with already has the largest possible size.

Fill the intersection, then extend to the union

Choose an independent set with . Extend by adding elements of while preserving independence, until no further element can be added. Call the resulting set .

By exchangeability, a maximal independent subset of has maximum size: a larger independent subset would supply another element to add. Hence

Why the intersection stays exactly

Suppose extending to added some . Since , we would have

By heredity, deleting elements from the independent set leaves an independent set. In particular, delete everything except and :

Schematic: and are outside . The orange region contains the retained elements , not necessarily all of . Deleting exposes an independent subset that is too large; the same argument works for any size of .

The remaining set would therefore satisfy all three conditions:

But an independent subset of has size at most . This would force

a contradiction. Adding elements outside cannot repair the dependent subset . Thus extending to adds no further element of :

Bound the two portions

Both and are independent, since they are subsets of . By the definition of rank,

Count the overlap twice

The two portions and cover and overlap exactly in . Adding their sizes counts every element of once, and every element of once more:

Shown for and : each column is one element, and each dot is one occurrence in the sum. The same count gives, for arbitrary and ,

This is the required inequality.

Function

Definition

Rank Function (Matroid)

The notion of ranks extends to arbitrary subsets. The rank function is

the size of the largest independent set inside . The rank is .

Link to original