minor -- minor of matroid

Synopsis

• Usage:
minor(M, X, Y)
• Inputs:
• M,
• X, a set, of indices, or a list of elements in M
• Y, a set, of indices, or a list of elements in M, disjoint from X
• Outputs:
• , the minor M / X &#92; Y

Description

The minor M / X &#92; Y of M is given by contracting X and deleting Y from M. The resulting matroid is independent of the order in which deletion and contraction is done. If X (or Y) is a set (of indices in M.groundSet), then X is identified with the sublist of elements of M with indices in X: cf. groundSet for more on this package-wide convention.

 i1 : M = matroid random(ZZ^3,ZZ^6) o1 = a matroid of rank 3 on 6 elements o1 : Matroid i2 : M_* o2 = {| 8 |, | 7 |, | 3 |, | 8 |, | 8 |, | 3 |} | 1 | | 8 | | 7 | | 5 | | 5 | | 6 | | 3 | | 3 | | 8 | | 7 | | 2 | | 3 | o2 : List i3 : M.groundSet o3 = set {0, 1, 2, 3, 4, 5} o3 : Set i4 : (X, Y) = (set{3}, set{0,1}) o4 = (set {3}, set {0, 1}) o4 : Sequence i5 : (X1, Y1) = (M_X, M_Y) o5 = ({| 8 |}, {| 8 |, | 7 |}) | 5 | | 1 | | 8 | | 7 | | 3 | | 3 | o5 : Sequence i6 : N = minor(M, X, Y) o6 = a matroid of rank 2 on 3 elements o6 : Matroid i7 : peek N o7 = Matroid{bases => {set {0, 1}, set {0, 2}, set {1, 2}}} cache => CacheTable{...2...} groundSet => set {0, 1, 2} rank => 2 i8 : N == minor(M, X1, Y1) o8 = true

Note that there is potential ambiguity for the second argument - namely, whether or not Y is treated with respect to the ground set of M or M / X (which are different). This method assumes that the indices of Y (and X) are taken with respect to the ground set of M.

If one already has the indices Y0 of Y in M / X (or the indices X0 of X in M &#92; Y), one can simply use the notation M / X \ Y0 (or (M &#92; Y) / X0). Thus this method serves purely as a convenience, to save the user the (trivial) task of computing Y0 from Y.

If X and Y are not disjoint, then an error is thrown (thus one should subtract X from Y beforehand).

 i9 : M5 = matroid completeGraph 5 o9 = a matroid of rank 4 on 10 elements o9 : Matroid i10 : M5.groundSet o10 = set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} o10 : Set i11 : N = minor(M5, set{8}, set{3,4,9}) o11 = a matroid of rank 3 on 6 elements o11 : Matroid i12 : areIsomorphic(N, matroid completeGraph 4) o12 = true i13 : N == (M5 \ set{3,4,9}) / set{6} -- after deleting 3,4 (and 9), index 8 -> 6 o13 = true i14 : N == M5 / set{8} \ set{3,4,8} -- after contracting 8, index 9 -> 8 o14 = true i15 : (try minor(M5, set{8}, set{3,4,8,9})) === null o15 = true i16 : minor(M5, set{8}, set{3,4,8,9} - set{8}) o16 = a matroid of rank 3 on 6 elements o16 : Matroid