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 |