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!
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.

$\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