משפט לובאס-קנזר: הבדלים בין גרסאות בדף

גרסה אחרונה מ־10:36, 6 באפריל 2025

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

היסטוריה

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

נוסח המשפט

גרף קנזר $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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

@@ שורה 12: / שורה 12: @@
 '''משפט לובאס-קנזר'''. לכל <math>0<2k-1\le n</math> מתקיים <math>\chi(KG_{n,k}) = n-2k+2</math>.
-קל להדגים צביעה שאכן משתמשת ב-<math>n-2k+2</math> צבעים, והדבר נעשה כבר על ידי קזנר. הקושי הוא להוכיח כי זו הצביעה המוצלחת ביותר (מסמפר מינימלי של צבעים). באופן כללי מציאת מספר הצביעה של גרף נחשבת בעיה קשה, בפרט במקרים הדומים לגרף קנזר, בהם מספר הצביעה גדול יחסית ל-n-ים גדולים.
+קל להדגים צביעה שאכן משתמשת ב-<math>n-2k+2</math> צבעים, והדבר נעשה כבר על ידי קנזר. הקושי הוא להוכיח כי זו הצביעה המוצלחת ביותר (מסמפר מינימלי של צבעים). באופן כללי מציאת מספר הצביעה של גרף נחשבת בעיה קשה, בפרט במקרים הדומים לגרף קנזר, בהם מספר הצביעה גדול יחסית ל-n-ים גדולים.
 ==הוכחה==
@@ שורה 20: / שורה 20: @@
 נדגים את הצביעה של הגרף שהוצגה על ידי קנזר. בתור שמות לצבעים נשתמש במספרים טבעיים. נגדיר את הצביעה באופן הבא: לכל צומת A,
 :<math>\mbox{color}(A) = \min\{\min(A),n-2k+2\}</math>
-כלומר את הצמתים שהמכילים מספרים קטנים מ-<math>n-2k+2</math> נבצע במספר הקטן ביותר שהם מכילים, ואת כל השאר נצבע בצבע <math>n-2k+2</math>. כעת נניח ו-<math>A,B</math> צמתים הצבועים באותו הצבע. אם זה אחד מבין הצבעים <math>1,\ldots,n-2k+1</math> אז יש להם איבר משותף (הצבע עצמו) ולכן אין ביניהם קשת. ואם שניהם צבועים בצבע <math>n-2k+2</math> אז שניהם קבוצות בנות k איברים החלקיות לקבוצה <math>\{n-2k+2,\ldots,n\}</math> שיש בה <math>2k-1</math> איברים, ולכן הם חולקים לפחות איבר אחד ואין ביניהם קשת.
+כלומר את הצמתים שמכילים מספרים קטנים מ-<math>n-2k+2</math> נצבע במספר הקטן ביותר שהם מכילים, ואת כל השאר נצבע בצבע <math>n-2k+2</math>. כעת נניח ש-<math>A,B</math> צמתים הצבועים באותו הצבע. אם זה אחד מבין הצבעים <math>1,\ldots,n-2k+1</math> אז יש להם איבר משותף (הצבע עצמו) ולכן אין ביניהם קשת. ואם שניהם צבועים בצבע <math>n-2k+2</math> אז שניהם קבוצות בנות k איברים החלקיות לקבוצה <math>\{n-2k+2,\ldots,n\}</math> שיש בה <math>2k-1</math> איברים, ולכן הם חולקים לפחות איבר אחד ואין ביניהם קשת.
 ===שלב שני===
@@ שורה 27: / שורה 27: @@
 נסמן <math>d = \chi(KG_{n,k})</math>. נסמן ב-<math>S^d</math> את [[ספירה (גאומטריה)|ספירת היחידה]] ה-d-ממדית (שפת הכדור ה-d+1-ממדי). נפזר על פני הספירה n נקודות <math>x_1,\ldots,x_n</math> במצב כללי (אין d נקודות בקבוצה שנמצאות על [[על-מישור]] יחיד שעובר דרך הראשית; אפשר לעשות זאת למשל על ידי בחירת נקודות על היטל על הספירה של [[עקום המומנטים]] <math>(1,t,t^2,\ldots,t^n)</math>). לצורך ההוכחה נניח [[ללא הגבלת הכלליות]] שהצמתים של <math>KG_{n,k}</math> הם תתי הקבוצות מגודל k של <math>X = \{x_1,\ldots,x_n\}</math>. את קבוצת הצמתים נסמן ב-<math>V</math>. תהי <math>c</math> צביעה של <math>KG_{n,k}</math> ב-d צבעים <math>1,\ldots,d</math>.
-לכל <math>x \in S^d</math> נגדיר את <math>H(x)</math> להיות ה[[המיספרה]] הפתוחה ש-x הוא הקוטב (במובן הגאוגרפי) שלה (באנלוגיה תלת-ממדית, ניתן לחשוב על זה כאילו השמש נמצאת בדיוק מעל הנקודה x, <math>H(x)</math> היא ההמספירה המוארת). פורמלית: <math>H(x) = \{y \in S^d \mid \langle x,y \rangle>0\}</math>. לכל <math>1\le i \le d</math> נגדיר:
+לכל <math>x \in S^d</math> נגדיר את <math>H(x)</math> להיות ה[[המיספירה]] הפתוחה ש-x הוא הקוטב (במובן הגאוגרפי) שלה (באנלוגיה תלת-ממדית, ניתן לחשוב על זה כאילו השמש נמצאת בדיוק מעל הנקודה x, <math>H(x)</math> היא ההמספירה המוארת). פורמלית: <math>H(x) = \{y \in S^d \mid \langle x,y \rangle>0\}</math>. לכל <math>1\le i \le d</math> נגדיר:
-:<math>A_i = \{x \in S^d \mid \exist B\in V: B\subseteq H(x) \and c(B)=i\}</math>
+:<math>A_i = \{x \in S^d \mid \exist B\in V: B\subseteq H(x) \land c(B)=i\}</math>
 כלומר <math>A_i</math> היא קבוצת הנקודות כך שבהמספירה <math>H(x)</math> יש k נקודות של <math>X</math> המגדירות צומת של הגרף שצבעו i. ברור ש-<math>A_i</math> [[קבוצה פתוחה]] כי <math>X</math> קבוצה דיסקרטית ותזוזה קטנה מספיק של ההמספירה <math>H(x)</math> לא תשנה את הנקודות מ-X שהיא מכילה.
-נגדיר כעת: <math>A_{d+1} = S^d \setminus \bigcup_{i=1}^d A_i</math>. זוהי קבוצת הנקודות שאין בהמיספרות שהן מגדירות k נקודות של X (שיגדירו צומת), ולא ניתן לשייכן לאף צבע. זוהי [[קבוצה סגורה]] (כ[[משלים (מתמטיקה)|משלים]] של [[איחוד (מתמטיקה)|איחוד]] של קבוצות פתוחות). קיבלנו [[כיסוי]] של <math>S^d</math> על ידי הקבוצות <math>A_1,\ldots,A_{d+1}</math> שכולן פתוחות או סגורות, ולכן לפי [[משפט לוסטרניק-שנירלמן]] קיים <math>l</math> כך ש-<math>A_l</math> מכילה זוג [[נקודות אנטיפודיות]] <math>-x^*,x^*\in A_l</math>.
+נגדיר כעת: <math>A_{d+1} = S^d \setminus \bigcup_{i=1}^d A_i</math>. זוהי קבוצת הנקודות שאין בהמיספרות שהן מגדירות k נקודות של X (שיגדירו צומת), ולא ניתן לשייכן לאף צבע. זוהי [[קבוצה סגורה]] (כ[[משלים (מתמטיקה)|משלים]] של [[איחוד (מתמטיקה)|איחוד]] של קבוצות פתוחות). קיבלנו [[כיסוי (טופולוגיה)|כיסוי]] של <math>S^d</math> על ידי הקבוצות <math>A_1,\ldots,A_{d+1}</math> שכולן פתוחות או סגורות, ולכן לפי [[משפט לוסטרניק-שנירלמן]] קיים <math>l</math> כך ש-<math>A_l</math> מכילה זוג [[נקודות אנטיפודיות]] <math>-x^*,x^*\in A_l</math>.
 אם <math>1\le l\le d</math> אז קיים צומת <math>B^+\in V</math> כך ש-<math>B^+ \subseteq H(x^*)</math> וקיים צומת <math>B^- \in V</math> כך ש-<math>B^- \subseteq H(-x^*)</math>, ושניהם מקיימים <math>c(B^+)=c(B^-)=l</math>. אולם <math>H(x^*)\cap H(-x^*) = \empty</math> (המיספרות הפוכות) ולכן  <math>B^+\cap B^- = \empty</math>, ויש ביניהם קשת, בסתירה לצביעה שלהם באותו הצבע.
-מכאן ש-<math>l = d+1</math>. כלומר אין k נקודות של X בהמיספרות <math>H(x^*),H(-x^*)</math>. בכל המיספרה יש <math>k-1</math> נקודות לכל היותר וכל שאר הנקודות חייבות להימצא על העל-מישור שבין שתי ההמיספרות. קיבלנו שעל העל-מישור יש לפחות <math>n-2(k-1) = n-2k+2</math> נקודות. מצד שני מהמצב הכללי ידוע שעל העל-מישור יש לכל היותר <math>d</math> נקודות. ולכן <math>n-2k+2 \le d = \chi(KG_{n,k})</math>.
+מכאן ש-<math>l = d+1</math>. כלומר אין k נקודות של X בהמיספרות <math>H(x^*),H(-x^*)</math>. בכל המיספירה יש <math>k-1</math> נקודות לכל היותר וכל שאר הנקודות חייבות להימצא על העל-מישור שבין שתי ההמיספרות. קיבלנו שעל העל-מישור יש לפחות <math>n-2(k-1) = n-2k+2</math> נקודות. מצד שני מהמצב הכללי ידוע שעל העל-מישור יש לכל היותר <math>d</math> נקודות. ולכן <math>n-2k+2 \le d = \chi(KG_{n,k})</math>.
 ==לקריאה נוספת==
 <div class="mw-content-ltr">
-*Matoušek, Jiří (2003). [http://www.maths.ed.ac.uk/~aar/papers/matousek1.pdf Using the Borsuk–Ulam theorem]. Berlin: Springer Verlag. doi:10.1007/978-3-540-76649-0. {{ISBN|3-540-00362-2}}
+*Matoušek, Jiří (2003). [https://web.archive.org/web/20150128132229/http://www.maths.ed.ac.uk/~aar/papers/matousek1.pdf Using the Borsuk–Ulam theorem]. Berlin: Springer Verlag. doi:10.1007/978-3-540-76649-0. {{ISBN|3-540-00362-2}}
 </div>
 [[קטגוריה:משפטים בתורת הגרפים|לובאס-קנזר]]
 [[קטגוריה:הוכחות]]
+{{וח}}
+{{מיון ויקיפדיה|דף=משפט לובאס-קנזר|גרסה=40323260|פריט=Q25488564}}

משפט לובאס-קנזר: הבדלים בין גרסאות בדף

גרסה אחרונה מ־10:36, 6 באפריל 2025

תוכן עניינים

היסטוריה

נוסח המשפט

הוכחה

שלב ראשון

שלב שני

לקריאה נוספת

תפריט ניווט

משפט לובאס-קנזר: הבדלים בין גרסאות בדף

גרסה אחרונה מ־10:36, 6 באפריל 2025

היסטוריה

נוסח המשפט

הוכחה

שלב ראשון

שלב שני

לקריאה נוספת

תפריט ניווט

חיפוש