The intersection of these two matroids will be:
This is not a matroid because the exchange property fails. There's no
way to go from
M1 cap M2 = < d [(a) (b)] c>
[a, b] to
< d a b c > by exchanging one element.
§ Bipartite matching as matroid intersection
Matchings in a bipartite graph with partition arise
as the intersection of the independent sets of two matroids.
We will denote by the function which takes
a vertex to the set of edges incident on that vertex.
Let be a partition matroid : where is:
That is, in , every independent set has for each vertex of , at most
one edge incident. We need to check that this is an independent set.
The empty set of no edges is independent. If some collection of edges are
such that they have at most one edge incident, then removing edges can
only decrease incidence. Hence, it's also downward closed.
TODO: add picture
Similarly, we define :
Now, notice that any collection of edges is a legal
matching, since the edges cover all vertices of and at most once.
The largest element of is the maximum matching that we
are looking for.
§ Largest common independent set
Given two matroids , , with rank
functions and . Let and let .