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:
“We recognize caste in dogs because we rank ourselves by the familiar dog system, a ladderlike social arrangement wherein one individual outranks all others, the next outranks all but the first, and so on down the hierarchy. But the cat system is more like a wheel, with a high-ranking cat at the hub and the others arranged around the rim, all reluctantly acknowledging the superiority of the despot but not necessarily measuring themselves against one another.”
—Elizabeth Marshall Thomas. “Strong and Sensitive Cats,” Atlantic Monthly (July 1994)
“The statements of science are hearsay, reports from a world outside the world we know. What the poet tells us has long been known to us all, and forgotten. His knowledge is of our world, the world we are both doomed and privileged to live in, and it is a knowledge of ourselves, of the human condition, the human predicament.”
—John Hall Wheelock (1886–1978)
““I am willing to die for my country” is a variant of “I am willing to kill for my country.””
—Mason Cooley (b. 1927)