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

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.

• You didn't say what $S_1,\dots,S_m$ are, but I guess they're sets. Would you mind telling me the definition of "partial transversel"? – bof May 6 '18 at 5:01
• @bof the definition you mentioned in the comment is accurate, I'll add a definition to the question statement. – John Smith May 6 '18 at 12:08
• All the sets are finite, right? I don't have time to check it now, but doesn't something like this work: Given a partial transversal $A$ find a maximum transversal $B$ containing as many elements of $A$ as possible. Then show that, if $A\not\subseteq B,$ we can get a contradiction by constructing another maximum transversal $C$ which contains one more element of $A.$ – bof May 6 '18 at 23:57
• That seems appropriate, but how would I go about constructing $C$? – John Smith May 7 '18 at 3:32

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.