פורטל:מתמטיקה/משפטים והשערות/12

משפט החתונה, שמיוחס למתמטיקאי פיליפ הול, הוא משפט בקומבינטוריקה, שנותן תנאי הכרחי ומספיק לבחירת נציגים ייחודיים עבור משפחה של קבוצות.

נניח שיש לנו קבוצת נשים וקבוצת גברים וכל אישה מעוניינת בקבוצה חלקית כלשהי של הגברים. נשאלת השאלה, באילו תנאים ניתן לשדך לכל אישה גבר שהיא מעוניינת בו (באופן מונוגמי כמובן). ברור כי תנאי הכרחי הוא שמספר הגברים יהיה לפחות כמספר הנשים. ניתן להכליל דרישה זו לכל קבוצת נשים. כלומר, תנאי הכרחי הוא שכל $\!\,k$ נשים תהינה מעוניינות בלפחות $\!\,k$ גברים. משפט הול טוען כי תנאי זה הינו גם תנאי מספיק. נוסח לא פורמלי (אם כי מדויק לחלוטין) זה הוא שהעניק למשפט את כינויו.

לערך המלא