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 (A1, A2, ..., An), where the Ai are finite sets that need not be distinct, is a family of sets satisfying the marriage condition (MC), and suppose that |Ai| ≥ 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 A1 = {1,2,3}, A2 = {1,2,5} has both (1,2) and (2,1) as distinct SDR's.
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the words marshall, hall and/or variant:
“Well be waitin for you, Marshall at the OK corral.”
—Samuel G. Engel (19041984)
“This is a Senate of equals, of men of individual honor and personal character, and of absolute independence. We know no masters, we acknowledge no dictators. This is a hall for mutual consultation and discussion; not an arena for the exhibition of champions.”
—Daniel Webster (17821852)
“I am willing to die for my country is a variant of I am willing to kill for my country.”
—Mason Cooley (b. 1927)