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:
“But while being a mother is admittedly a lifelong preoccupation, it cannot, should not, must not be a lifelong occupation. . . .”
—Melinda M. Marshall (20th century)
“Go where he will, the wise man is at home,
His hearth the earth,—his hall the azure dome;
Where his clear spirit leads him, there’s his road,
By God’s own light illumined and foreshadowed.”
—Ralph Waldo Emerson (1803–1882)
““I am willing to die for my country” is a variant of “I am willing to kill for my country.””
—Mason Cooley (b. 1927)