next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: rank(Matroid,Set)

rank(Matroid,Set) -- rank of a subset of a matroid

Synopsis

Description

The rank of a subset S of a matroid is the size of a maximal independent subset of S. The map 2^E $\to \mathbb{N}$, S $\mapsto$ rank(S), is called the rank function, and completely determines the matroid.

Once the rank of a given subset is computed, it is cached in the matroid (under M.cache#"ranks"), so future computations of the rank of the same set are (essentially) instant.

The user may choose to install a custom rank function for a matroid (which should take in a list of integers (corresponding to a subset of M.groundSet), and output an integer), under M.cache#"rankFunction". This is done automatically when a matroid is constructed from a matrix or graph, or with setRepresentation.

i1 : M = matroid({a,b,c,d},{{a,b},{a,c}})

o1 = a "matroid" of rank 2 on 4 elements

o1 : Matroid
i2 : for s in subsets M_* do print(toString s | " has rank " | rank_M s)
{} has rank 0
{a} has rank 1
{b} has rank 1
{a, b} has rank 2
{c} has rank 1
{a, c} has rank 2
{b, c} has rank 1
{a, b, c} has rank 2
{d} has rank 0
{a, d} has rank 1
{b, d} has rank 1
{a, b, d} has rank 2
{c, d} has rank 1
{a, c, d} has rank 2
{b, c, d} has rank 1
{a, b, c, d} has rank 2

See also

Ways to use this method: