משפט לובאס-קנזר

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

היסטוריה

את המשפט שיער המתמטיקאי הגרמני מרטין קנזר ב-1955, אז הוא נודע בשם השערת קנזר. ב-1978 הציג לסלו לובאס הוכחה מפתיעה למשפט תוך שימוש בכלים טופולוגיים. הוכחה זו נחשבת לתוצאה הראשונה בענף הקומבינטוריקה טופולוגית, העוסק בשימוש בשיטות טופולוגיות בקומבינטוריקה (שימושים של קומבינטוריקה בטופולוגיה היו ידועים עוד לפניכן). מאז נמצאו הוכחות טופולוגיות רבות למשפט, רובן מבוססות על משפט בורסוק-אולם. הוכחה קומבינטורית טהורה נמצאה על ידי Matoušek ב-2004, אך גם היא מבוססת על "חיקוי" של הוכחה טופולוגית (בפרט נעשה שימוש בלמה של טקר שהיא תוצאה קומבינטורית השקולה למשפט בורסוק-אולם הטופולוגי).

נוסח המשפט

הגרף $KG_{5,2}$ - ידוע כגרף פטרסן

גרף קנזר $KG_{n,k}$ הוא גרף המוגדר באופן הבא: הצמתים בגרף הם כל התתי קבוצות של $\{1,\ldots ,n\}$ שיש בהן k איברים. יש קשת בין שני צמתים אם ורק אם הם זרים כקבוצות. למשל ב-$KG_{4,2}$ יש קשת בין $\{1,3\}$ ל-$\{2,4\}$ ואין קשת בין $\{1,3\}$ ל-$\{3,4\}$.

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

משפט לובאס-קנזר. לכל $0<2k-1\leq n$ מתקיים $\chi (KG_{n,k})=n-2k+2$.

קל להדגים צביעה שאכן משתמשת ב-$n-2k+2$ צבעים, והדבר נעשה כבר על ידי קזנר. הקושי הוא להוכיח כי זו הצביעה המוצלחת ביותר (מסמפר מינימלי של צבעים). באופן כללי מציאת מספר הצביעה של גרף נחשבת בעיה קשה, בפרט במקרים הדומים לגרף קנזר, בהם מספר הצביעה גדול יחסית ל-n-ים גדולים.

הוכחה

ההוכחה מתחלקת באופן טבעי לשני שלבים. בשלב הראשון נוכיח ש-$\chi (KG_{n,k})\leq n-2k+2$ על ידי כך שנדגמים צביעה המשתמשת ב-$n-2k+2$ צבעים. בשלב השני נוכיח ש-$\chi (KG_{n,k})\geq n-2k+2$ באמצעות טיעון טופולוגי.

שלב ראשון

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

${\mbox{color}}(A)=\min\{\min(A),n-2k+2\}$

כלומר את הצמתים שהמכילים מספרים קטנים מ-$n-2k+2$ נבצע במספר הקטן ביותר שהם מכילים, ואת כל השאר נצבע בצבע $n-2k+2$. כעת נניח ו-$A,B$ צמתים הצבועים באותו הצבע. אם זה אחד מבין הצבעים $1,\ldots ,n-2k+1$ אז יש להם איבר משותף (הצבע עצמו) ולכן אין ביניהם קשת. ואם שניהם צבועים בצבע $n-2k+2$ אז שניהם קבוצות בנות k איברים החלקיות לקבוצה $\{n-2k+2,\ldots ,n\}$ שיש בה $2k-1$ איברים, ולכן הם חולקים לפחות איבר אחד ואין ביניהם קשת.

שלב שני

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

נסמן $d=\chi (KG_{n,k})$. נסמן ב-$S^{d}$ את ספירת היחידה ה-d-ממדית (שפת הכדור ה-d+1-ממדי). נפזר על פני הספירה n נקודות $x_{1},\ldots ,x_{n}$ במצב כללי (אין d נקודות בקבוצה שנמצאות על על-מישור יחיד שעובר דרך הראשית; אפשר לעשות זאת למשל על ידי בחירת נקודות על היטל על הספירה של עקום המומנטים $(1,t,t^{2},\ldots ,t^{n})$). לצורך ההוכחה נניח ללא הגבלת הכלליות שהצמתים של $KG_{n,k}$ הם תתי הקבוצות מגודל k של $X=\{x_{1},\ldots ,x_{n}\}$. את קבוצת הצמתים נסמן ב-$V$. תהי $c$ צביעה של $KG_{n,k}$ ב-d צבעים $1,\ldots ,d$.

לכל $x\in S^{d}$ נגדיר את $H(x)$ להיות ההמיספרה הפתוחה ש-x הוא הקוטב (במובן הגאוגרפי) שלה (באנלוגיה תלת-ממדית, ניתן לחשוב על זה כאילו השמש נמצאת בדיוק מעל הנקודה x, $H(x)$ היא ההמספירה המוארת). פורמלית: $H(x)=\{y\in S^{d}\mid \langle x,y\rangle >0\}$. לכל $1\leq i\leq d$ נגדיר:

$A_{i}=\{x\in S^{d}\mid \exists B\in V:B\subseteq H(x)\land c(B)=i\}$

כלומר $A_{i}$ היא קבוצת הנקודות כך שבהמספירה $H(x)$ יש k נקודות של $X$ המגדירות צומת של הגרף שצבעו i. ברור ש-$A_{i}$ קבוצה פתוחה כי $X$ קבוצה דיסקרטית ותזוזה קטנה מספיק של ההמספירה $H(x)$ לא תשנה את הנקודות מ-X שהיא מכילה.

נגדיר כעת: $A_{d+1}=S^{d}\setminus \bigcup _{i=1}^{d}A_{i}$. זוהי קבוצת הנקודות שאין בהמיספרות שהן מגדירות k נקודות של X (שיגדירו צומת), ולא ניתן לשייכן לאף צבע. זוהי קבוצה סגורה (כמשלים של איחוד של קבוצות פתוחות). קיבלנו כיסוי של $S^{d}$ על ידי הקבוצות $A_{1},\ldots ,A_{d+1}$ שכולן פתוחות או סגורות, ולכן לפי משפט לוסטרניק-שנירלמן קיים $l$ כך ש-$A_{l}$ מכילה זוג נקודות אנטיפודיות $-x^{*},x^{*}\in A_{l}$.

אם $1\leq l\leq d$ אז קיים צומת $B^{+}\in V$ כך ש-$B^{+}\subseteq H(x^{*})$ וקיים צומת $B^{-}\in V$ כך ש-$B^{-}\subseteq H(-x^{*})$, ושניהם מקיימים $c(B^{+})=c(B^{-})=l$. אולם $H(x^{*})\cap H(-x^{*})=\emptyset$ (המיספרות הפוכות) ולכן $B^{+}\cap B^{-}=\emptyset$, ויש ביניהם קשת, בסתירה לצביעה שלהם באותו הצבע.

מכאן ש-$l=d+1$. כלומר אין k נקודות של X בהמיספרות $H(x^{*}),H(-x^{*})$. בכל המיספרה יש $k-1$ נקודות לכל היותר וכל שאר הנקודות חייבות להימצא על העל-מישור שבין שתי ההמיספרות. קיבלנו שעל העל-מישור יש לפחות $n-2(k-1)=n-2k+2$ נקודות. מצד שני מהמצב הכללי ידוע שעל העל-מישור יש לכל היותר $d$ נקודות. ולכן $n-2k+2\leq d=\chi (KG_{n,k})$.

לקריאה נוספת

• Matoušek, Jiří (2003). Using the Borsuk–Ulam theorem. Berlin: Springer Verlag. doi:10.1007/978-3-540-76649-0. מסת"ב 3-540-00362-2