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

בעיית הדוויגר–נלסון היא בעיה פתוחה במתמטיקה השואלת מהו המספר הקטן ביותר של צבעים שבו יש לצבוע את כל הנקודות במישור, אם אסור לצבוע באותו צבע שתי נקודות שמרחקן זו מזו הוא 1. בלשון טכנית, השאלה היא מהו המספר הכרומטי $\chi$ של גרף מרחקי היחידה במישור האוקלידי.

את הבעיה הציג אדוארד נלסון (אנ') ב-1950, לאחר שהוגו הדוויגר (אנ') דן בבעיה דומה ב-1945. בתוך זמן קצר הוברר שמספר הצבעים מקיים $4\leq \chi \leq 7$ . את ריצוף חלת הדבש של המישור (במשושים משוכללים) אפשר לצבוע בשבעה צבעים, וזה מוכיח שאכן $\chi \leq 7$ . מאידך, מכיוון ש"הפלך של מוזר" הוא גרף מרחקי יחידה (בן 7 קודקודים) שהמספר הכרומטי שלו 4, מתקיים גם $4\leq \chi$ .

לפי תוצאה כללית של ניקולאס חוברט דה ברויין (אנ') ופול ארדש (1951), אם המספר הכרומטי של גרף הוא לפחות k, אז יש לו תת-גרף סופי כזה. לכן, כל חסם תחתון על $\ \chi$ יתקבל מהצגת גרף מרחקי יחידה בעל מספר כרומטי מתאים. ב-1998 הראה פריטיקין (Pritikin) שגרף מרחקי יחידה בעל מספר כרומטי 5 הוא בן 13 קודקודים לפחות; וגרף מרחקי יחידה בעל מספר כרומטי 6 (אם יש כזה) הוא בן 6,198 קודקודים לפחות.

ב-1981 הראה פלקונר (Falconer) שאם כל קבוצות הצבע הן מדידות, אז מספר הצבעים הוא לפחות 5. ב-2018 מצא אוברי דה גריי גרף מרחקי יחידה (בן 1,581 קודקודים)^[1] שהמספר הכרומטי שלו הוא 5, ובכך שיפר את החסם ל- $5\leq \chi$ .^[2]

הכללות

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