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’ll be waitin’ for you, Marshall at the OK corral.”
—Samuel G. Engel (1904–1984)
“Having children can smooth the relationship, too. Mother and daughter are now equals. That is hard to imagine, even harder to accept, for among other things, it means realizing that your own mother felt this way, too—unsure of herself, weak in the knees, terrified about what in the world to do with you. It means accepting that she was tired, inept, sometimes stupid; that she, too, sat in the dark at 2:00 A.M. with a child shrieking across the hall and no clue to the child’s trouble.”
—Anna Quindlen (20th century)
““I am willing to die for my country” is a variant of “I am willing to kill for my country.””
—Mason Cooley (b. 1927)