Transversal Theory

• Let be a non-empty finite set and a family of not necessarily distinct, non-empty subsets of . A transversal of is a set of distinct element of , one chosen from each set .

• Given a family of subsets of , an independent transversal is a transversal that is also an independent set of a matroid .

• A partial transversal of a family of sets is a transversal of some subfamily of

  • (Wilson 26.2) has a partial transversal of size if and only if the union of any of the subsets in contains at least elements
  • (Wilson 26.3) contains a partial transversal of of size if and only if, for each subset of then
    That is, removing some elements for all members of the family does not change the Hall condition.

• Let be a non-empty finite set and and be families of non-empty subsets of , then a common transversal is a transversal for both and .

  • (Wilson 27.3) A common transversal exists if and only if for all subsets and of .

Other Theorems §

• (Wilson e26.8) Let be transversals of . . Then, there exists an element such that is also a transversal.

  • Proof: Assume and are distinct transversals. Note that, because they are of the same size, then there exists such that

    We show that , for some . Suppose by contradiction. As above we may have

    Now, since is a transversal, it must include an element . Such an element is not included in since it already includes . We argue similarly for and . In summary,

    But now, observe we are back to the same problem as before. This is effectively an argument by infinite descent, leading to the desired contradiction.

    With this, we have that . It follows that , since both and are transversals, may be properly matched to the -th element and no other element. Replacing with in indeed gives another transversal.

  • (Wilson e26.10) A family of subsets of has a transversal containing a given subset if and only if

    • has a transversal

    • is a partial transversal of .

    • (Proof) Observe that in the lens of a transversal matroid is an independent set of the transversal matroid determined by .

      Thus, by the basis definition of a matroid, can be extended to a basis of

      Since has a transversal, every basis of must be a transversal, and this basis contains as desired.

• (Wilson 33.1) Rado’s Theorem - Let be a matroid on a set , and let be a family of non-empty subsets of . Then has an independent transversal if and only if the union of any of the subsets contains an independent set of size at least .

  • Applying it to the discrete matroid on gives Hall’s Theorem.

• (Wilson 33.2) A family has an independent partial transversal of size if and only if the union of any of the subsets contains an independent set of size at least