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

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

היסטוריה

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

נוסח המשפט

הגרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle KG_{5,2}} - ידוע כגרף פטרסן

גרף קנזר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle KG_{n,k}} הוא גרף המוגדר באופן הבא: הצמתים בגרף הם כל התתי קבוצות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,\ldots,n\}} שיש בהן k איברים. יש קשת בין שני צמתים אם ורק אם הם זרים כקבוצות. למשל ב-$KG_{4,2}$ יש קשת בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,3\}} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{2,4\}} ואין קשת בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,3\}} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{3,4\}} .

צביעה של גרף היא התאמה של צבע לכל צומת כך שאין שני צמתים בעלי צבע זהה המחוברים בקשת. מספר הצביעה של גרף G מסומן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \chi(G)} והוא מוגדרת כמספר המינימלי של צבעים הדרושים כדי לצבוע את G.

משפט לובאס-קנזר. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<2k-1\le n} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi(KG_{n,k}) = n-2k+2} .

קל להדגים צביעה שאכן משתמשת ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2k+2} צבעים, והדבר נעשה כבר על ידי קזנר. הקושי הוא להוכיח כי זו הצביעה המוצלחת ביותר (מסמפר מינימלי של צבעים). באופן כללי מציאת מספר הצביעה של גרף נחשבת בעיה קשה, בפרט במקרים הדומים לגרף קנזר, בהם מספר הצביעה גדול יחסית ל-n-ים גדולים.

הוכחה

ההוכחה מתחלקת באופן טבעי לשני שלבים. בשלב הראשון נוכיח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi(KG_{n,k})\le n-2k+2} על ידי כך שנדגמים צביעה המשתמשת ב-$n-2k+2$ צבעים. בשלב השני נוכיח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi(KG_{n,k}) \ge n-2k+2} באמצעות טיעון טופולוגי.

שלב ראשון

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{color}(A) = \min\{\min(A),n-2k+2\}}

כלומר את הצמתים שהמכילים מספרים קטנים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2k+2} נבצע במספר הקטן ביותר שהם מכילים, ואת כל השאר נצבע בצבע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2k+2} . כעת נניח ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B} צמתים הצבועים באותו הצבע. אם זה אחד מבין הצבעים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1,\ldots,n-2k+1} אז יש להם איבר משותף (הצבע עצמו) ולכן אין ביניהם קשת. ואם שניהם צבועים בצבע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2k+2} אז שניהם קבוצות בנות k איברים החלקיות לקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{n-2k+2,\ldots,n\}} שיש בה $2k-1$ איברים, ולכן הם חולקים לפחות איבר אחד ואין ביניהם קשת.

שלב שני

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

נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = \chi(KG_{n,k})} . נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S^d} את ספירת היחידה ה-d-ממדית (שפת הכדור ה-d+1-ממדי). נפזר על פני הספירה n נקודות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1,\ldots,x_n} במצב כללי (אין d נקודות בקבוצה שנמצאות על על-מישור יחיד שעובר דרך הראשית; אפשר לעשות זאת למשל על ידי בחירת נקודות על היטל על הספירה של עקום המומנטים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1,t,t^2,\ldots,t^n)} ). לצורך ההוכחה נניח ללא הגבלת הכלליות שהצמתים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle KG_{n,k}} הם תתי הקבוצות מגודל k של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = \{x_1,\ldots,x_n\}} . את קבוצת הצמתים נסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} . תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} צביעה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle KG_{n,k}} ב-d צבעים $1,\ldots ,d$.

לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in S^d} נגדיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x)} להיות ההמיספרה הפתוחה ש-x הוא הקוטב (במובן הגאוגרפי) שלה (באנלוגיה תלת-ממדית, ניתן לחשוב על זה כאילו השמש נמצאת בדיוק מעל הנקודה x, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x)} היא ההמספירה המוארת). פורמלית: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x) = \{y \in S^d \mid \langle x,y \rangle>0\}} . לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le i \le d} נגדיר:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i = \{x \in S^d \mid \exist B\in V: B\subseteq H(x) \and c(B)=i\}}

כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i} היא קבוצת הנקודות כך שבהמספירה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x)} יש k נקודות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} המגדירות צומת של הגרף שצבעו i. ברור ש-$A_{i}$ קבוצה פתוחה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} קבוצה דיסקרטית ותזוזה קטנה מספיק של ההמספירה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x)} לא תשנה את הנקודות מ-X שהיא מכילה.

נגדיר כעת: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_{d+1} = S^d \setminus \bigcup_{i=1}^d A_i} . זוהי קבוצת הנקודות שאין בהמיספרות שהן מגדירות k נקודות של X (שיגדירו צומת), ולא ניתן לשייכן לאף צבע. זוהי קבוצה סגורה (כמשלים של איחוד של קבוצות פתוחות). קיבלנו כיסוי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S^d} על ידי הקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,\ldots,A_{d+1}} שכולן פתוחות או סגורות, ולכן לפי משפט לוסטרניק-שנירלמן קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_l} מכילה זוג נקודות אנטיפודיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -x^*,x^*\in A_l} .

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\le l\le d} אז קיים צומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^+\in V} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^+ \subseteq H(x^*)} וקיים צומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^- \in V} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^- \subseteq H(-x^*)} , ושניהם מקיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(B^+)=c(B^-)=l} . אולם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x^*)\cap H(-x^*) = \empty} (המיספרות הפוכות) ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^+\cap B^- = \empty} , ויש ביניהם קשת, בסתירה לצביעה שלהם באותו הצבע.

מכאן ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l = d+1} . כלומר אין k נקודות של X בהמיספרות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x^*),H(-x^*)} . בכל המיספרה יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} נקודות לכל היותר וכל שאר הנקודות חייבות להימצא על העל-מישור שבין שתי ההמיספרות. קיבלנו שעל העל-מישור יש לפחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2(k-1) = n-2k+2} נקודות. מצד שני מהמצב הכללי ידוע שעל העל-מישור יש לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} נקודות. ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2k+2 \le 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