Macaulay2 » Documentation
Packages » Matroids :: minor
next | previous | forward | backward | up | index | toc

minor -- minor of matroid

Synopsis

Description

The minor M / X \ 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)/toList

o5 = ({| 8 |}, {| 7 |, | 8 |})
       | 5 |    | 8 |  | 1 |
       | 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{...1...}
             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 \ Y), one can simply use the notation M / X \ Y0 (or (M \ 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

See also

Ways to use minor:

For the programmer

The object minor is a method function.