Hall's Marriage Theorem - Discussion and Examples

Discussion and Examples

Example 1: Consider S = {A1, A2, A3} with

A1 = {1, 2, 3}
A2 = {1, 4, 5}
A3 = {3, 5}.

A valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well, for example.)

Example 2: Consider S = {A1, A2, A3, A4} with

A1 = {2, 3, 4, 5}
A2 = {4, 5}
A3 = {5}
A4 = {4}.

No valid SDR exists; the marriage condition is violated as is shown by the subcollection {A2, A3, A4}.

Example 3: Consider S= {A1, A2, A3, A4} with

A1 = {a, b, c}
A2 = {b, d}
A3 = {a, b, d}
A4 = {b, d}.

The only valid SDR's are (c, b, a, d) and (c, d, a, b).

Read more about this topic:  Hall's Marriage Theorem

Famous quotes containing the words discussion and, discussion and/or examples:

    Opinions are formed in a process of open discussion and public debate, and where no opportunity for the forming of opinions exists, there may be moods—moods of the masses and moods of individuals, the latter no less fickle and unreliable than the former—but no opinion.
    Hannah Arendt (1906–1975)

    There are answers which, in turning away wrath, only send it to the other end of the room, and to have a discussion coolly waived when you feel that justice is all on your own side is even more exasperating in marriage than in philosophy.
    George Eliot [Mary Ann (or Marian)

    There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.
    Bernard Mandeville (1670–1733)