Matroid + Matroid -- union of matroids

Synopsis

Operator: +
Usage:

M + N
Inputs:
- M, a matroid,
- N, a matroid,
Outputs:
- a matroid, the sum, or union, of M and N

Description

The union of M and N has ground set equal to the union of those of M and N, and independent sets given by pairwise unions of independent sets of M and N.

i1 : M = uniformMatroid(2,4) + uniformMatroid(1,4)

o1 = a "matroid" of rank 3 on 4 elements

o1 : Matroid

i2 : peek M

o2 = Matroid{bases => {set {0, 1, 2}, set {0, 1, 3}, set {0, 2, 3}, set {1, 2, 3}}}
             cache => CacheTable{...1...}
             groundSet => set {0, 1, 2, 3}
             rank => 3

i3 : M == uniformMatroid(3, 4)

o3 = true

When the ground sets of M and N are disjoint, this is the direct sum of M and N. Beware of order when using == though:

i4 : M0 = uniformMatroid(2, 4) + matroid completeGraph 4

o4 = a "matroid" of rank 5 on 10 elements

o4 : Matroid

i5 : M0 == uniformMatroid(2, 4) ++ matroid completeGraph 4

o5 = true

i6 : M1 = matroid completeGraph 4 ++ uniformMatroid(2, 4)

o6 = a "matroid" of rank 5 on 10 elements

o6 : Matroid

i7 : M0 == M1

o7 = false

i8 : areIsomorphic(M0, M1)

o8 = true

Matroid union is an important operation in combinatorial optimization, and via duality, is related to the problem of matroid intersection.

With the operation of union, one can work with transversal matroids and gammoids. A matroid is transversal iff it is a union of rank 1 matroids; strict gammoids are precisely the duals of transversal matroids, and gammoids are restrictions of strict gammoids. In general the problem of determining if a given matroid is a gammoid is difficult.

A union of two uniform matroids is again uniform, but a union of two graphic matroids need not be binary:

i9 : M0 = matroid({a,b,c,d}, {{a},{b},{c}})

o9 = a "matroid" of rank 1 on 4 elements

o9 : Matroid

i10 : M1 = matroid({a,b,c,d}, {{b},{c},{d}})

o10 = a "matroid" of rank 1 on 4 elements

o10 : Matroid

i11 : M0 + M1 == uniformMatroid(2,4)

o11 = true

i12 : F7 = specificMatroid "fano"

o12 = a "matroid" of rank 3 on 7 elements

o12 : Matroid

i13 : NF = specificMatroid "nonfano"

o13 = a "matroid" of rank 3 on 7 elements

o13 : Matroid

i14 : all({F7 + NF, F7 + F7, NF + NF}, M -> M == uniformMatroid(6, 7))

o14 = true

One potential caveat: the ground set of M must not have repeated elements. If this is not the case, the user MUST rename elements of M so that they become distinct. Of course, this needs to be done for both M and N, and one should also keep track of which elements of M and N are meant to be the same after the renaming (otherwise the entire point of taking unions, as opposed to direct sums, is lost).

In the example below, M contains the vector {1,1} twice. Macaulay2 has no way of distinguishing the repeated vectors, so the second occurrence of {1,1} is relabelled to the symbol d (of course, if the symbol d also happened to be an element of N, then a different label would have to be chosen).

i15 : A = matrix{{0,1,1,1},{0,0,1,1}}

o15 = | 0 1 1 1 |
      | 0 0 1 1 |

               2       4
o15 : Matrix ZZ  <-- ZZ

i16 : M = matroid A

o16 = a "matroid" of rank 2 on 4 elements

o16 : Matroid

i17 : M_*

o17 = {0, | 1 |, | 1 |, | 1 |}
          | 0 |  | 1 |  | 1 |

o17 : List

i18 : unique M_*

o18 = {0, | 1 |, | 1 |}
          | 0 |  | 1 |

o18 : List

i19 : M0 = matroid(M_{0,1,2} | {d}, bases M)

o19 = a "matroid" of rank 2 on 4 elements

o19 : Matroid

i20 : M == M0

o20 = true

i21 : B = matrix{{0,1,2},{0,1,2}}

o21 = | 0 1 2 |
      | 0 1 2 |

               2       3
o21 : Matrix ZZ  <-- ZZ

i22 : N = matroid B

o22 = a "matroid" of rank 1 on 3 elements

o22 : Matroid

i23 : U = M0 + N

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

o23 : Matroid

i24 : peek U

o24 = Matroid{bases => {set {1, 2, 4}, set {1, 2, 3}, set {1, 3, 4}}}
              cache => CacheTable{...1...}
              groundSet => set {0, 1, 2, 3, 4}
              rank => 3

i25 : U_*

o25 = {0, | 1 |, | 1 |, d, | 2 |}
          | 0 |  | 1 |     | 2 |

o25 : List

Ways to use this method: