Hall's Marriage Theorem - Marshall Hall Jr. Variant

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 rn 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:

    I have a lifetime appointment and I intend to serve it. I expect to die at 110, shot by a jealous husband.
    —Thurgood Marshall (1908–1993)

    This is a Senate of equals, of men of individual honor and personal character, and of absolute independence. We know no masters, we acknowledge no dictators. This is a hall for mutual consultation and discussion; not an arena for the exhibition of champions.
    Daniel Webster (1782–1852)

    “I am willing to die for my country” is a variant of “I am willing to kill for my country.”
    Mason Cooley (b. 1927)