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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

הכללות[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ "An Anti-Aging Pundit Solves a Decades-Old Math Problem". WIRED (באנגלית). בדיקה אחרונה ב-7 במאי 2018. 
  2. ^ אחרי 60 שנה: חידה מתמטית לקראת פתרון, באתר ynet, 6 במאי 2018