בעיית הדוויגר–נלסון

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

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

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

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

הכללות

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

ראו גם

• בעיית ארבעת הצבעים

הערות שוליים

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

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] בעיית הדוויגר–נלסון23009504