truncate(Set,Matroid) -- the truncation of a matroid with respect to a flat

Synopsis

Function: truncate
Usage:

truncate M,

truncate(F, M)
Inputs:
- F, a set, a flat of the matroid
- M, a matroid
Outputs:
- a matroid, the truncation of the matroid

Description

This function is provided by the package Matroids.

The truncation of a matroid M is the matroid T(M) on the same ground set as M whose rank function is given by taking the maximum of the rank of a set in M and the rank of M minus one. The truncation T(M) is an example of an elementary quotient of M. For a uniform matroid U_{r,n}, the truncation is just U_{r-1,n}.

i1 : M = uniformMatroid(4, 5);

i2 : TM = truncate M

o2 = a "matroid" of rank 3 on 5 elements

o2 : Matroid

i3 : quickIsomorphismTest(TM, uniformMatroid(3, 5))

o3 = true

The flats of the truncation T(M) are just the flats of M with the hyperplanes removed.

i4 : M = matroid completeGraph 5;

i5 : TM = truncate M

o5 = a "matroid" of rank 3 on 10 elements

o5 : Matroid

i6 : set flats TM === (set flats M) - hyperplanes M

o6 = true

The i-fold truncation T^i(M) can be constructed as follows.

i7 : T2M = truncate(2, M)

o7 = a "matroid" of rank 2 on 10 elements

o7 : Matroid

i8 : partition(F -> rank(T2M, F), flats T2M)

o8 = HashTable{0 => {set {}}                                                                                  }
               1 => {set {9}, set {8}, set {7}, set {6}, set {5}, set {4}, set {3}, set {2}, set {1}, set {0}}
               2 => {set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}

o8 : HashTable

We can also construct the principal truncation of M with respect to some flat F. The principal truncation of M with respect to F is the elementary quotient of M corresponding to the principal modular cut associated to F.

i9 : F = set {0, 1, 4};

i10 : TFM = truncate(F, M)

o10 = a "matroid" of rank 3 on 10 elements

o10 : Matroid

i11 : partition(G -> rank(TFM, G), flats TFM)

o11 = HashTable{0 => {set {}}                                                                                                                                                                               }
                1 => {set {9}, set {8}, set {7}, set {6}, set {5}, set {3}, set {2}, set {0, 1, 4}}
                2 => {set {7, 8, 9}, set {5, 6, 9}, set {0, 1, 4, 9}, set {2, 3, 9}, set {0, 1, 3, 4, 6, 8}, set {5, 8}, set {2, 8}, set {6, 7}, set {0, 1, 2, 4, 5, 7}, set {3, 7}, set {2, 6}, set {3, 5}}
                3 => {set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}

o11 : HashTable

Ways to use this method: