next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: Matroid

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 :

Methods that use a matroid :

For the programmer

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