Hall's Marriage Theorem - Marshall Hall Jr. Variant

Marshall Hall Jr. Variant

By examining Philip Hall's original proof carefully, Marshall Hall, Jr. was able to tweak the result in a way that permitted the proof to work for infinite S. This variant refines the marriage theorem and provides a lower bound on the number of SDR's that a given S may have. This variant is:

Suppose that (A₁, A₂, ..., A_n), where the A_i are finite sets that need not be distinct, is a family of sets satisfying the marriage condition (MC), and suppose that |A_i| ≥ r for i = 1, ..., n. Then the number of different SDR's for the family is at least r ! if r ≤ n and r(r - 1) ... (r - n +1) if r > n.

Recall that a transversal for a family S is an ordered sequence, so two different SDR's could have exactly the same elements. For instance, the family A₁ = {1,2,3}, A₂ = {1,2,5} has both (1,2) and (2,1) as distinct SDR's.