7
$\begingroup$

I am trying to figure out why the transversal matroid is a matroid. Specifically, if $L$ and $M$ are two independent sets s.t. $|L| < |M|$, why is there an $i$ in $M \setminus L$ s.t. $L \cup \{ i \} $ is independent? thank you in advance!

$\endgroup$
7
$\begingroup$

Let me check that we have the same definition of transversal matroids. For me, the input is a bipartite graph $\Gamma$, with white vertex set $W$ and black vertex set $B$. The ground set of the matroid is $B$, with a subset of $B$ being independent if it can be matched to a subset of $W$.

Direct Proof that this is a matroid: Suppose that $M$ and $L$ are subsets of $B$ can be matched, with $|L|<|M|$. Superimpose the matchings. This gives a graph $G$ where the elements each vertex has degree $\leq 2$ -- so a union of paths and cycles (including possibly some $2$ cycles.) We'll call an edge of $G$ mauve or lavender acording to whether it comes from $M$ or $L$. In each path or cycle of $G$, the edges alternate color.

Each element of $M \setminus L$ gives a degree $1$ in $B$ at the end of a mauve edge, and each element of $L \setminus M$ gives a degree one element of $B$ at the end of a lavender edge. Since $|M| > |L|$, there must be a path one of whose ends is a mauve edge ending in $W$ and whose other end is not a lavender edge ending in $B$. The only other possibility for the end of that path is a mauve edge ending in $W$. In other words, this path has vertices $b_1$, $w_1$, $b_2$, $w_2$, ..., $b_r$, $w_r$ where $b_i$ is matched to $w_i$ in $M$, $w_i$ is matched to $b_{i+1}$ in $L$ and $b_1$ and $w_r$ are not matched in $L$. Now modify $L$ to match $b_i$ to $w_i$, leaving all other elements of $L$ matched as before. This is a matching of $L \cup \{ b_1 \}$.

Conceptual proof Take a matrix $A$ with rows labeled by $W$ and columns labeled by $B$. Place a $0$ in $A_{bw}$ if $\Gamma$ has no edge between $b$ and $w$, and place algebraically independent elements in the positions where $\Gamma$ does have an edge. The transversal matroid is realized by the columns of this matrix.

$\endgroup$
  • $\begingroup$ thank you very much! I acctually reffered to the Transversal matroid presented here: en.wikipedia.org/wiki/Gammoid#Transversal_matroids but your version is the same (if the black side are the sets A_i, the white side is the elements of E and there is an edge if the element is in A_i. $\endgroup$ – hashark May 12 '12 at 18:59
  • $\begingroup$ Among its other virtues, the conceptual proof is better because it shows that the matroid is not only a matroid, but is representable (assuming the field is large enough for the relevant scheme to have rational points). $\endgroup$ – Allen Knutson May 17 '12 at 0:48
  • $\begingroup$ Just curious how the proof of exchange property of matching matroids is different from this argument? I'm thinking they are the same. $\endgroup$ – zack Feb 18 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.