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:
“Work is a responsibility most adults assume, a burden at times, a complication, but also a challenge that, like children, requires enormous energy and that holds the potential for qualitative, as well as quantitative, rewards. Isn’t this the only constructive perspective for women who have no choice but to work? And isn’t it a more healthy attitude for women writhing with guilt because they choose to compound the challenges of motherhood with work they enjoy?”
—Melinda M. Marshall (20th century)
“For a hundred and fifty years, in the pasture of dead horses,
roots of pine trees pushed through the pale curves of your ribs,
yellow blossoms flourished above you in autumn, and in winter
frost heaved your bones in the ground—old toilers, soil makers:
O Roger, Mackerel, Riley, Ned, Nellie, Chester, Lady Ghost.”
—Donald Hall (b. 1928)
““I am willing to die for my country” is a variant of “I am willing to kill for my country.””
—Mason Cooley (b. 1927)