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:
“Let us not succumb to nature. We will marshall the clouds and restrain tempests; we will bottle up pestilent exhalations; we will probe for earthquakes, grub them up, and give vent to the dangerous gas; we will disembowel the volcano, and extract its poison, take its seed out. We will wash water, and warm fire, and cool ice, and underprop the earth. We will teach birds to fly, and fishes to swim, and ruminants to chew the cud. It is time we looked into these things.”
—Henry David Thoreau (1817–1862)
“When Western people train the mind, the focus is generally on the left hemisphere of the cortex, which is the portion of the brain that is concerned with words and numbers. We enhance the logical, bounded, linear functions of the mind. In the East, exercises of this sort are for the purpose of getting in tune with the unconscious—to get rid of boundaries, not to create them.”
—Edward T. Hall (b. 1914)
““I am willing to die for my country” is a variant of “I am willing to kill for my country.””
—Mason Cooley (b. 1927)