[proofplan] Let $M := \{1,\dots,m\}$, and let $\mathcal{I}$ denote the family of all partial transversals of $(A_i)_{i=1}^m$, meaning those subsets $X \subseteq E$ for which there exists an injective map $\phi:X \to M$ such that $x \in A_{\phi(x)}$ for every $x \in X$. We verify the two matroid independence axioms for $\mathcal{I}$: hereditary closure and the exchange axiom. Hereditary closure follows by restricting a witnessing injection. For exchange, we encode a witnessing injection for $I$ as a matching in the bipartite incidence graph between elements of $E$ and indices $\{1,\dots,m\}$, orient matched edges backward and unmatched admissible edges forward, and use an alternating-path argument. If no element of $J \setminus I$ can augment $I$, the reachable indices force the injection witnessing $J$ to use too few indices, contradicting $|J|>|I|$. [/proofplan] [step:Verify that the empty set is independent and independence is hereditary] With $M$ and $\mathcal{I}$ as defined in the proof plan, the empty map $\varnothing \to M$ is injective, so $\varnothing \in \mathcal{I}$. Now let $X \in \mathcal{I}$ and let $Y \subseteq X$. By definition of $\mathcal{I}$, there exists an injective map $\phi:X \to M$ such that $x \in A_{\phi(x)}$ for every $x \in X$. The restriction $\phi|_Y:Y \to M$ is injective, and for every $y \in Y$ we still have $y \in A_{\phi|_Y(y)}$. Hence $Y \in \mathcal{I}$. [/step] [step:Build the alternating digraph from a matching of $I$] Let $I,J \in \mathcal{I}$ satisfy $|I|<|J|$. Choose injective maps $\alpha:I \to M$ and $\beta:J \to M$ such that $x \in A_{\alpha(x)}$ for every $x \in I$ and $y \in A_{\beta(y)}$ for every $y \in J$. Define a directed graph $D$ with vertex set $E \sqcup M$ as follows. For each $x \in I$, include the directed edge $\alpha(x) \to x$. For each pair $(x,i) \in E \times M$ with $x \in A_i$, include the directed edge $x \to i$ unless $x \in I$ and $i=\alpha(x)$. Thus the edges $\alpha(x) \to x$ are exactly the matched edges of $\alpha$ oriented from indices to elements, and all other admissible incidence edges are oriented from elements to indices. Let $R_E \subseteq E$ be the set of elements reachable in $D$ from some starting vertex in $J \setminus I$, and let $R_M \subseteq M$ be the set of indices reachable in $D$ from some starting vertex in $J \setminus I$. [/step] [step:Show that a reachable unused index gives the required exchange element] Suppose there exist $y \in J \setminus I$ and an index $r \in M \setminus \alpha(I)$ such that $r$ is reachable in $D$ from $y$. Choose a directed path $P=(v_0,v_1,\dots,v_\ell)$ in $D$ with $v_0=y$ and $v_\ell=r$. Since directed edges from elements go to indices and directed edges from indices go to elements, the path alternates between elements and indices. Delete repeated directed cycles if necessary, so we may assume the vertices of $P$ are distinct. Define the set of element-index pairs along $P$ by $N_P := \{(v_{2k},v_{2k+1}) : 0 \le 2k < \ell\}$. These are admissible pairs because every edge from an element to an index was included only when the element lies in the corresponding $A_i$. Define $M_P := \{(v_{2k+2},v_{2k+1}) : 0 \le 2k+1 < \ell\}$. These are exactly the matched pairs of $\alpha$ whose matched edges occur along the path, because every edge from an index to an element has the form $\alpha(x) \to x$. Now define a map $\alpha':I \cup \{y\} \to M$ as follows. If $x \in I \cup \{y\}$ occurs as an element vertex $v_{2k}$ on the path and $2k<\ell$, set $\alpha'(x):=v_{2k+1}$. If $x \in I$ does not occur as an element vertex on the path, set $\alpha'(x):=\alpha(x)$. The path has distinct vertices, so the indices assigned along the path are distinct. Also, the terminal index $r$ is not in $\alpha(I)$, while every index removed from the old assignment is precisely one of the matched indices occurring on the path. Therefore $\alpha'$ is injective. For every $x \in I \cup \{y\}$ assigned along the path, admissibility follows from the edge $x \to \alpha'(x)$; for every $x$ not on the path, admissibility follows from the original assignment $\alpha$. Hence $I \cup \{y\} \in \mathcal{I}$. [guided] We recall the objects used in this step so that the augmentation argument is self-contained. The set $M$ denotes $\{1,\dots,m\}$, the sets $I,J \subseteq E$ are partial transversals with $|I|<|J|$, and $\alpha:I \to M$ is an injective witnessing map for $I$, so $x \in A_{\alpha(x)}$ for every $x \in I$. The directed graph $D$ has vertex set $E \sqcup M$: for each $x \in I$ it contains the matched edge $\alpha(x) \to x$, and for each admissible incidence $x \in A_i$ it contains $x \to i$ unless $x \in I$ and $i=\alpha(x)$. The purpose of this directed graph is to encode exactly the operation of changing a matching. Starting from $y \in J \setminus I$, an element-to-index edge means that we try assigning this element to that set, while an index-to-element edge means that the index is already occupied by this element, so using the index forces us to move the old element somewhere else. Assume that a directed path starts at $y$ and ends at an unused index $r \in M \setminus \alpha(I)$. Write this path as $P=(v_0,v_1,\dots,v_\ell)$ with $v_0=y$ and $v_\ell=r$. Because the graph is bipartite with parts $E$ and $M$, the vertices alternate between elements and indices. We remove repeated directed cycles if needed; this keeps the same start and end vertices and makes the vertices of $P$ distinct. Along the path, each edge from an element to an index is an admissible assignment. Thus the pairs $N_P := \{(v_{2k},v_{2k+1}) : 0 \le 2k < \ell\}$ are all valid element-index assignments: if $(v_{2k},v_{2k+1}) \in N_P$, then $v_{2k} \in A_{v_{2k+1}}$. The reverse-oriented edges from indices to elements are precisely old matched edges of $\alpha$. Hence the pairs $M_P := \{(v_{2k+2},v_{2k+1}) : 0 \le 2k+1 < \ell\}$ are exactly the old assignments of $\alpha$ that the path will displace. The alternating-path move is to remove the old matched pairs in $M_P$ and insert the new admissible pairs in $N_P$. Formally, define $\alpha':I \cup \{y\} \to M$ by assigning each element vertex $v_{2k}$ on the path with $2k<\ell$ to the next index $v_{2k+1}$, and by leaving every element of $I$ not appearing on the path assigned as before by $\alpha$. This map is injective because the path has no repeated vertices, so the new indices on the path are distinct, and the only old indices that are reused are exactly the ones whose old assignments were removed. The final index $r$ was unused by $\alpha$, so no collision is introduced at the end of the path. Every new assignment is valid because it comes from an admissible edge $x \to i$, and every unchanged assignment is valid because $\alpha$ was valid. Therefore $I \cup \{y\}$ is a partial transversal. [/guided] [/step] [step:Derive a contradiction if no exchange element exists] Assume, for contradiction, that $I \cup \{y\} \notin \mathcal{I}$ for every $y \in J \setminus I$. By the previous step, no index in $M \setminus \alpha(I)$ is reachable from $J \setminus I$. Hence $R_M \subseteq \alpha(I)$. Define $K := I \cap R_E$. We show that $R_M=\alpha(K)$. Let $r \in R_M$. Since $R_M \subseteq \alpha(I)$, there is a unique $x \in I$ with $r=\alpha(x)$, because $\alpha:I\to M$ is injective. The directed edge $\alpha(x) \to x$ belongs to $D$, so reachability of $r$ implies reachability of $x$; hence $x \in K$ and $r \in \alpha(K)$. Conversely, let $x \in K$. If $x \in J \setminus I$, this contradicts $x \in K \subseteq I$, so every directed path from $J \setminus I$ to $x$ has positive length. The final edge into the element vertex $x$ must be an index-to-element edge, and the only such edge entering $x \in I$ is $\alpha(x) \to x$. Therefore $\alpha(x) \in R_M$. Thus $R_M=\alpha(K)$. Since $\alpha|_K:K\to R_M$ is bijective, we have $|R_M|=|K|$. Next we prove that the part of $J$ lying in $J \setminus I$ or in $K$ is sent by $\beta$ into $R_M$. If $y \in J \setminus I$, then $y$ is a starting vertex and hence $y \in R_E$. Since $y \in A_{\beta(y)}$ and $y \notin I$, the directed edge $y \to \beta(y)$ belongs to $D$, so $\beta(y) \in R_M$. If $x \in J \cap K$, then $x \in R_E$ and $x \in A_{\beta(x)}$. If $\beta(x)=\alpha(x)$, then $\beta(x)=\alpha(x) \in \alpha(K)=R_M$. If $\beta(x)\ne \alpha(x)$, then the directed edge $x \to \beta(x)$ belongs to $D$, so again $\beta(x) \in R_M$. Therefore $\beta\big((J \setminus I) \cup (J \cap K)\big) \subseteq R_M$. Because $\beta:J\to M$ is injective, its restriction to $(J \setminus I) \cup (J \cap K)$ is injective. Hence $|J \setminus I|+|J \cap K| \le |R_M|=|K|$. Also $J \cap (I \setminus K) \subseteq I \setminus K$, so $|J \cap (I \setminus K)| \le |I \setminus K|$. The disjoint decomposition $J=(J \setminus I) \cup (J \cap K) \cup (J \cap (I \setminus K))$ therefore gives $|J|=|J \setminus I|+|J \cap K|+|J \cap (I \setminus K)| \le |K|+|I \setminus K|=|I|$. This contradicts the hypothesis $|I|<|J|$. Hence there exists $y \in J \setminus I$ such that $I \cup \{y\}\in\mathcal{I}$. [/step] [step:Conclude that the partial transversals satisfy the matroid exchange axiom] We have shown that $\varnothing \in \mathcal{I}$, that $\mathcal{I}$ is closed under taking subsets, and that whenever $I,J \in \mathcal{I}$ satisfy $|I|<|J|$, there exists $y \in J \setminus I$ such that $I \cup \{y\}\in\mathcal{I}$. These are exactly the independence axioms for a matroid on the finite ground set $E$. Therefore the partial transversals of $(A_i)_{i=1}^m$ are the independent sets of a matroid on $E$. [/step]