How the Matroids Module Works

The fundamental design philosophy of this Matroids module is that

• the ground set of a matroid is always of the form $\{1,2,\ldots,m\}$,
• a matroid is defined by way of its rank function, and
• the matroid data structure is immutable.

Ground Sets

We adopt the philosophy of the Graphs module: the ground set of a matroid is always of the form $\{1,2,\ldots,m\}$ where $m$ is a nonnegative integer.

Rank Functions Define Matroids

Mathematically, matroids are defined as a pair $(S,\mathcal{I})$ where $\mathcal{I}$ is the set of subsets of $S$ that are independent. However, keeping $\mathcal{I}$ as a data structure is inefficient because the number of independent sets in a matroid may be enormous.

For example, the simple uniform matroid $U(10,5)$ has a ten-element ground set and over 600 independent sets. However, the rank function of this matroid is easy to define. For any subset $X$ of the ground set $[10]$, we simply have $\rho(X) = \min\{|X|, 5\}$.

In other words, matroids are defined by providing a rank oracle.

Matroids are Immutable

Once created, a matroid cannot be modified. Operations on matroids, such as deleting an element, create a new matroid.

For example, if a matroid has 10 elements and element 3 is deleted, the new matroid's ground set is $\{1,2,\ldots,9\}$. If (say) $\{2,5,7\}$ is independent in $M$, then in the new matroid the set $\{2,4,6\}$ is independent. If $x$ is an element with $x>3$, then in the new matroid it is represented as $x-1$. This is consistent with vertex deletion in Graphs.

Creating Your Own Matroid

To create a new type of matroid, first define a structure for its rank function. This should be a subtype of AbstractRankFunction. The definition should look like this:

struct MyRankFunction <: AbstractRankFunction
    data
    function MyRankFunction(creation_data)
        # operations to create the data structure 
        return new(data)
    end 
end

Second, define how your rank function operates on a set of integers:

(r::MyRankFunction)(S::Set{T}) where {T<:Integer}
    # calculate the rank, r, of the set S
    return r
end

It is important that your rank function satisfy the matroid rank axioms or the resulting Matroid will not be a matroid.

Finally, define a function MyMatroid(parameters) that creates the matroid:

function MyMatroid(parameters)
    # create the rank function r and the size of the ground set m from the parameters
    return Matroid(m, r)
end

As an example, look at UniformRankFunction and UniformMatroid in src/RankFunctions.jl.