הצגת המקור של הדף "בעיית הדוויגר–נלסון"

'''בעיית הדוויגר–נלסון''' היא [[בעיה פתוחה במתמטיקה]] השואלת מהו המספר הקטן ביותר של צבעים שבו ניתן לצבוע את כל הנקודות במישור, אם אסור לצבוע באותו צבע שתי נקודות שמרחקן זו מזו הוא 1. בלשון טכנית, השאלה היא מהו ה[[מספר כרומטי|מספר הכרומטי]] <math>\chi</math> של '''גרף מרחקי היחידה''' במישור האוקלידי.

את הבעיה הציג [[אדוארד נלסון]] {{אנ|Edward Nelson}} ב-1950, לאחר ש[[הוגו הדוויגר]] {{אנ|Hugo Hadwiger}} דן בבעיה דומה ב-1945. בתוך זמן קצר הוברר שמספר הצבעים מקיים <math>4 \leq \chi \leq 7</math>. את ריצוף חלת הדבש של המישור (במשושים משוכללים) אפשר לצבוע בשבעה צבעים, וזה מוכיח שאכן  <math>\chi \leq 7</math>. מאידך, מכיוון ש"הפלך של מוזר" הוא גרף מרחקי יחידה (בן 7 קודקודים) שהמספר הכרומטי שלו 4, מתקיים גם <math>4 \leq \chi</math>.

לפי תוצאה כללית של [[ניקולאס חוברט דה ברויין]] {{אנ|Nicolaas Govert de Bruijn}} ו[[פול ארדש]] (1951), אם המספר הכרומטי של גרף הוא לפחות k, אז יש לו תת-גרף סופי כזה. לכן, כל חסם תחתון על <math>\ \chi</math> יתקבל מהצגת גרף מרחקי יחידה בעל מספר כרומטי מתאים. ב-[[1998]] הראה פריטיקין (Pritikin) שגרף מרחקי יחידה בעל מספר כרומטי 5 הוא בן 13 קודקודים לפחות; וגרף מרחקי יחידה בעל מספר כרומטי 6 (אם יש כזה) הוא בן 6,198 קודקודים לפחות.

ב-[[1981]] הראה פלקונר (Falconer) שאם כל קבוצות הצבע הן [[קבוצה מדידה|מדידות]], אז מספר הצבעים הוא לפחות 5. ב-[[2018]] מצא [[אוברי דה גריי]] גרף מרחקי יחידה (בן 1,581 קודקודים){{הערה|{{Cite news|url=https://www.wired.com/story/an-anti-aging-pundit-solves-a-decades-old-math-problem/|title=An Anti-Aging Pundit Solves a Decades-Old Math Problem|newspaper=WIRED|language=en-US|access-date=2018-05-07}}}} שהמספר הכרומטי שלו הוא 5, ובכך שיפר את החסם ל-<math>5 \leq  \chi</math>.{{הערה|{{ynet||אחרי 60 שנה: חידה מתמטית לקראת פתרון|5252708|6 במאי 2018}}}}

== הכללות ==

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

== ראו גם ==
* [[בעיית ארבעת הצבעים]]

==קישורים חיצוניים==
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:תורת הגרפים]]
[[קטגוריה:בעיות פתוחות במתמטיקה בדידה]]