next | previous | forward | backward | up | index | toc

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,
• Outputs:
• , 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 {4, 0, 1}} 2 => {set {8, 9, 7}, set {9, 5, 6}, set {0, 9, 1, 4}, set {9, 2, 3}, set {8, 0, 1, 3, 4, 6}, set {8, 5}, set {8, 2}, set {6, 7}, set {0, 1, 2, 4, 5, 7}, set {7, 3}, set {6, 2}, set {5, 3}} 3 => {set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}} o11 : HashTable

See also

• elementaryQuotient -- associated to a modular cut or linear subclass
• modularCut -- associated to an elementary quotient or linear subclass