# Matroid -- the class of all matroids

## Description

To see how to specify a matroid, see matroid.

In this package, the ground set of the matroid is always (internally) assumed to be a set of the form $\{0, ..., n-1\}$. This means that although the actual elements of the ground set can be arbitrary, all subsets of the ground set are specified by their indices, i.e. as a subset of $\{0, ..., n-1\}$ (this includes bases, circuits, flats, loops, etc.).

For convenience, the user can specify a subset of the ground set either by indices (which are integers between 0 and n-1), or as actual elements. If indices are used, they should be given as a Set, and if elements are used, they should be given as a List.

One can use the function indicesOf to convert elements of the ground set to their indices. Conversely, use subscripts to obtain the elements from their indices.

A recommended way to circumvent this distinction between indices and elements is to make the elements of M equal to integers from 0 to n-1, in which case an element is equal to its index in M.groundSet.

For more on this package-wide convention, see groundSet.

 i1 : U24 = uniformMatroid(2, 4) o1 = a matroid of rank 2 on 4 elements o1 : Matroid i2 : U24 == dual U24 o2 = true i3 : ideal U24 o3 = monomialIdeal (x x x , x x x , x x x , x x x ) 0 1 2 0 1 3 0 2 3 1 2 3 o3 : MonomialIdeal of QQ[x ..x ] 0 3 i4 : peek U24 o4 = Matroid{bases => {set {0, 1}, set {0, 2}, set {1, 2}, set {0, 3}, set {1, 3}, set {2, 3}}} cache => CacheTable{...4...} groundSet => set {0, 1, 2, 3} rank => 2 i5 : tuttePolynomial U24 2 2 o5 = x + y + 2x + 2y o5 : ZZ[x..y] i6 : N = U24 / {0} o6 = a matroid of rank 1 on 3 elements o6 : Matroid i7 : areIsomorphic(N, uniformMatroid(1, 3)) o7 = true

Many computations performed in this package are cached in order to speed up subsequent calculations (as well as avoiding redundancy). These include the circuits, flats, ideal, rank function, and Tutte polynomial of a matroid, and are stored in the CacheTable of the matroid. Since the cache is a MutableHashTable, the user can also manually cache data (e.g. if it has been computed in a previous session), which can greatly speed up computation.

 i8 : R10 = specificMatroid "R10" o8 = a matroid of rank 5 on 10 elements o8 : Matroid i9 : keys R10.cache o9 = {groundSet, rankFunction} o9 : List i10 : time isWellDefined R10 -- used 0.0562218 seconds o10 = true i11 : time fVector R10 -- used 0.258441 seconds o11 = HashTable{0 => 1 } 1 => 10 2 => 45 3 => 75 4 => 30 5 => 1 o11 : HashTable i12 : keys R10.cache o12 = {hyperplanes, groundSet, rankFunction, dual, ideal, flats} o12 : List i13 : time fVector R10 -- used 0.000118655 seconds o13 = HashTable{0 => 1 } 1 => 10 2 => 45 3 => 75 4 => 30 5 => 1 o13 : HashTable

## Functions and methods returning a matroid :

• "affineGeometry(ZZ,ZZ)" -- see affineGeometry -- affine geometry of rank n+1 over F_p
• "contraction(Matroid,List)" -- see contraction -- contraction of subset of matroid
• "contraction(Matroid,Set)" -- see contraction -- contraction of subset of matroid
• "deletion(Matroid,List)" -- see deletion -- deletion of subset of matroid
• "deletion(Matroid,Set)" -- see deletion -- deletion of subset of matroid
• dual(Matroid) -- dual matroid
• "matroid(Graph)" -- see matroid -- constructs a matroid
• "matroid(Ideal)" -- see matroid -- constructs a matroid
• "matroid(List)" -- see matroid -- constructs a matroid
• "matroid(List,List)" -- see matroid -- constructs a matroid
• "matroid(List,MonomialIdeal)" -- see matroid -- constructs a matroid
• "matroid(Matrix)" -- see matroid -- constructs a matroid
• "minor(Matroid,List,List)" -- see minor -- minor of matroid
• "minor(Matroid,Set,Set)" -- see minor -- minor of matroid
• "projectiveGeometry(ZZ,ZZ)" -- see projectiveGeometry -- projective geometry of dimension n over F_p
• "relaxation(Matroid,List)" -- see relaxation -- relaxation of matroid
• "relaxation(Matroid,Set)" -- see relaxation -- relaxation of matroid
• "restriction(Matroid,List)" -- see restriction -- restriction to subset of matroid
• "restriction(Matroid,Set)" -- see restriction -- restriction to subset of matroid
• "simpleMatroid(Matroid)" -- see simpleMatroid -- simple matroid associated to a matroid
• "specificMatroid(String)" -- see specificMatroid -- creates built-in matroid
• "uniformMatroid(ZZ,ZZ)" -- see uniformMatroid -- uniform matroid

## For the programmer

The object Matroid is a type, with ancestor classes HashTable < Thing.