Can every partial transversal be extended to a maximum partial transversal?

Question

Say we have some collection of subsets of some universal set S, denoted $\mathscr{S} = \{S_1, S_2, ..., S_m\}$, with a maximum partial transversal $C=\{c_1, ..., c_t\}$. How might I go about proving that for any partial transversal $A$, $\exists$ a maximum partial transversal $B$ such that $A \subseteq B$ ?

I think there's a graph theoretic route to this proof, where the bipartite graph $G(V,E)$ corresponds to $\mathscr{S}$ such that the vertex set $V$ is $\{1,...,m\}$ and the edge set $E$ is the set $\{(i,s)\}$ such that $i$ runs through $m$ and $s$ runs through the $S_i$'s. However, I'm unsure of where to go after defining this correspondence.

A transversal is a set $\{s_1, s_2, ..., s_m\}$, all distinct, such that $\forall i, \thinspace s_i \thinspace \epsilon \thinspace S_i$. A partial transversal is a transversal of a subfamily of $\mathscr{S}$. A maximum partial transversal is the transversal of maximum size for a certain subfamily.

Answer 1

Personally, I would go the route of proving that the partial transversals of a set system are the independent sets of a matroid. That any partial transversal can be extended to a maximal partial transversal follows from the fact that any independent set can be extended to a maximal independent set (i.e. a basis).

Here are is a paper (Bonin 2010) that gives two proofs of this theorem (see section 2.2 and theorem 2.2). The first is a proof using a matrix representation of a set system, and the second is a sketch of a proof using the idea of augmenting paths from matching theory.

I'll sketch the first proof. The idea is to represent the system with a matrix; each row corresponds to a set and each column an element. The $i, j$ entry is non-zero exactly if set $i$ contains element $j$. We call this nonzero value $x_{i, j}$; we think of the set of $x_{i, j}$ as formal variables, which functionally means we choose them to be algebraically independent values in some field. Regardless of the details, the point is to encode information about the set system into the relationship between the columns.

For example, when we take the determinant of a square submatrix, we get a sum of terms corresponding to partial transversals and their matchings. For instance, if a $2 \times 2$ submatrix has a term $x_{2, 1}x_{3, 5}$, there is a matching of the 1st and 5th element to the 2nd and 3rd sets, respectively. Therefore, a submatrix with nonzero determinant corresponds to a transversal of a subsystem of the set system. Again, the rows tell you what sets you've chosen and the columns tell you the elements in the transversal.

In other words, this shows that there's a correspondence between partial transversals and linearly-independent sets of columns in the matrix. This collection of linearly-independent sets of columns is a vector matroid; in fact, such a construction is the prototypical example of a matroid. Thus the partial transversals are the independent sets of a matroid.