next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: Matroid + Matroid

Matroid + Matroid -- union of matroids

Synopsis

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 relabel 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 relabelling (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

See also