# Matroid + Matroid -- union of matroids

## Synopsis

• Operator: +
• Usage:
M + N
• Inputs:
• M, ,
• N, ,
• Outputs:
• , 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{...2...} 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{...2...} groundSet => set {0, 1, 2, 3, 4} rank => 3 i25 : U_* o25 = {0, | 1 |, | 1 |, d, | 2 |} | 0 | | 1 | | 2 | o25 : List