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

# minor -- minor of matroid

- Usage:
    `minor(M, X, Y)`
- Inputs:
  - M, a matroid,
  - 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:
  - a matroid, the minor M / X \ Y

## 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

- deletion -- deletion of subset of matroid
- contraction -- contraction of subset of matroid
- hasMinor -- whether a matroid has a given minor

## Ways to use minor:

- `minor(Matroid,List,List)`
- `minor(Matroid,Set,Set)`

## For the programmer

The object minor is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Matroids/doc-Matroids.m2:1486:0.