קבוצת מחקר פתרה בעיה מתמטית פתוחה מזה 63 שנה, והוכיחה הרחבה של 'משפט ארבעת הצבעים'

אם ניתן לצבוע מפה גיאוגרפית כך שכל שתי מדינות בעלות קו גבול משותף יצבעו בצבע שונה, תוך שימוש בארבעה צבעים לכל היותר? לגבי המפות התשובה חיובית אך מה לגבי עיגולים שאינם חופפים אך יכולים להשיק?

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

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

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

רינגל הרחיב את השאלה בכך ששאל כמה צבעים יספיקו במקרה שהמעגלים חופפים? הוא הציג דוגמא בה ארבעה צבעים אינם מספיקים אך חמישה כן ושאל האם תמיד יספיקו חמישה צבעים לכל אוסף של מעגלים? אם לא, כמה צבעים יספיקו? פריצת הדרך הנוכחית גילתה שהתשובה לבעיה שהציף רינגל היא אינסוף! קבוצת המחקר בנתה דוגמא נגדית לכל מספר צבעים והוכיחה שכל מספר סופי של צבעים אינו מספיק. לבעיות צביעה כאלו השלכות על תחומים רבים כגון הקצאת תדרים לאנטנות סלולריות, שיבוץ טייסים לטיסות בחברת תעופה, שיבוץ משימות עבודה למכונה ועוד שימושים מגוונים.

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

מה שהופך את הפתרון למסתורי עוד יותר הוא הדוגמאות שהציעו החוקרים בהוכחה המתמטית. אלו מצביעות על כך שמספר הצבעים הדרוש אינו חסום. הדוגמאות אינן מפורשות מפאת המספר העצום של המעגלים בדוגמא. "בעוד שהמתמטיקאי רינגל הראה שצריך לפחות 5 צבעים בעזרת דוגמא של 9 מעגלים, על מנת להראות ש- 5 צבעים אינם מספיקים יש לצייר בצורה מסוימת 10 בחזקת 10,000 מעגלים" מסביר פרופ' שחר סמורודינסקי, מהמחלקה למתמטיקה באוניברסיטת בן-גוריון בנגב. "זה מספר הגדול בהרבה ממספר האטומים ביקום. מדהים שצריך מספר כל כך גדול ולא סביר בכדי להראות את זה".

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

מחקר זה (מס' 1065/20) נתמך על ידי הקרן הלאומית למדע.