משפט החתונה

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

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

ניסוח פורמלי

תהא $\!\,S_{1},\dots ,S_{n}$ משפחה של קבוצות סופיות. קבוצת נציגים ייחודיים של המשפחה הזו היא קבוצה של איברים $\!\,a_{1},\dots ,a_{n}$ כך שכל שני איברים שונים זה מזה, $\!\,i\neq j\Rightarrow a_{i}\neq a_{j}$ וכן $\!\,a_{i}\in S_{i}$ (איבר זה הוא הנציג של אותה קבוצה).

על פי משפט החתונה, תנאי הכרחי ומספיק לקיום של קבוצת נציגים ייחודיים למשפחת קבוצות נתונה הוא שלכל תת-קבוצה של המשפחה, $\!\,T=\left\{S_{i_{1}},\dots ,S_{i_{t}}\right\}$ יתקיים $\!\,\left|\cup S_{i_{k}}\right|\geq t$, כלומר בכל $\!\,t$ קבוצות שונות של המשפחה יש לפחות $\!\,t$ איברים שונים בכל הקבוצות.

קל לראות שהתנאי הכרחי - אם עבור $\!\,t$ קבוצות כלשהן יש פחות מ$\!\,t$ איברים שונים, בהכרח כל בחירת נציגים עבור הקבוצות תהיה כזו שבה נציג אחד נבחר לפחות פעמיים.

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

למשפט יש גם הרבה שימושים מעניינים שאינם קשורים ישירות לשידוכים. לדוגמה, בהינתן חפיסת קלפים סטנדרטית, שמחולקת באופן שרירותי ל-13 רביעיות, ניתן להראות באמצעות משפט החתונה שניתן לבחור קלף אחד בדיוק מכל רביעייה כך ש-13 הקלפים הנבחרים יכילו בדיוק קלף אחד מכל 'מספר' (אס, 2, 3, 4, 5, 6, 7, 8, 9, 10, נסיך, מלכה ומלך).

ניסוח עבור גרפים

דרך אחרת לנסח את המשפט היא עבור גרפים דו צדדיים. אם $\ G=(S+T,E)$ הוא גרף דו צדדי, אז קיים בו שידוך המכסה את צד $\ S$ אם ורק אם לכל תת-קבוצה $\ X\subseteq S$ מתקיים $\ \|X\|\leq \|N_{G}(X)\|$, כאשר $\ N_{G}(X)$ הוא אוסף השכנים של צמתים ב-$\ X$. הדמיון לניסוח הקודם ברור - הקבוצה $\ S$ מייצגת את משפחת הקבוצות שעבורן בוחרים נציגים, הקבוצה $\ T$ את אוסף האיברים שהקבוצות במשפחה יכולות להכיל, וקשת מייצג קשר של הכלה.

הוכחה

ההוכחה היא לפי הניסוח של המשפט עבור שידוך בגרף דו צדדי.

נתון גרף דו צדדי $\ G$ עם צדדים $\ S,T$ ונניח את תנאי המשפט - לכל $S'\subseteq S$ מתקיים ש $|N(S')|\geq |S'|$.

נסתכל על שידוך בגודל מקסימלי $\ M$ לצמתי $\ S$. נסמן את הצמתים שאינם משודכים ב $\ S$ על ידי ${\tilde {S}}$. נניח בשלילה ש ${\tilde {S}}\neq \emptyset$.

מסלול מתחלף הוא מסלול (שיכול להיות ריק) $\ P=(v_{1},v_{2},...,v_{n})$ בגרף המתחיל בצומת מ $\ {\tilde {S}}$ כך שהקשתות האי זוגיות $\ (v_{2i-1},v_{2i})$ שייכות ל $\ E-M$ והקשתות הזוגיות $\ (v_{2i},v_{2i+1})$ שייכות ל $\ M$.

נניח שקיים מסלול מתחלף המסתיים בצומת ב $\ T$ שאינו משודך. נוכל להגדיר שידוך חדש $M'=M\triangle P$ שגודלו יהיה $\ |M|+1$ בסתירה לכך שהשידוך $\ M$ הוא מגודל מקסימלי. לכן כל מסלול מתחלף שמסתיים ב $\ T$ חייב להסתיים בצומת ששייך לשידוך $\ M$.

נגדיר את $S'\subseteq S$ להיות כל הצמתים מ $\ S$ שניתן להגיע אליהם עם מסלולים מתחלפים ונסמן $\ T'=N(S')$.

אם $\ u\in T'$ אז הוא שכן של $v\in S'$ כלשהו. אם הקשת $\ e_{1}$ המחברת ביניהם אינה שייכת לשידוך, אז קיים מסלול מתחלף P המגיע ל- v, ויחד עם הקשת $\ e_{1}$ מקבלים מסלול מתחלף המגיע ל- u. ממה שהוכחנו קודם, u בהכרח משודך לצומת $w\in S$ כלשהו על ידי קשת $\ e_{2}\in M$. נקבל, ש- P יחד עם הקשתות $\ e_{1},e_{2}$ הוא מסלול מתחלף המגיע אל w ולכן $\ w\in S'$. קיבלנו, אם כן, ש- $\ T'$ מכיל רק צמתים משודכים ב- M, ובנוסף כי כל הצמתים שמשודכים אליו נמצאים ב $\ S'$. נוכל איפוא לרשום:

$\ |S'|=|S'-{\tilde {S}}|+|{\tilde {S}}|\geq |T'|+|{\tilde {S}}|>|T'|=|N(S')|$

ומקבלים סתירה לכך ש $\ |S'|\leq |N(S')|$

מספר האפשרויות

מהוכחת המשפט ניתן גם לתת חסם תחתון למספר האפשרויות שבהן ניתן לבחור נציגים ייחודיים. אם $\!\,t$ הוא גודלה המינימלי של הקבוצה הקטנה מכל הקבוצות ו-$\!\,n$ הוא מספר הקבוצות, הרי שאם מתקיים $\!\,t\geq n$, מספר האפשרויות הוא לפחות $\!\,t\cdot (t-1)\cdot \dots \cdot (t-n+1)$ אפשרויות. אם $\!\,t<n$, הרי שיש לפחות $\!\,t!$ אפשרויות. נשים לב כי זהו חסם נמוך מאוד, ולעיתים קרובות מספר האפשרויות גדול ממנו בהרבה.

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

ראו גם

• שידוך (תורת הגרפים)