לפני למעלה ממאתיים שנה גילו קרטוגרפים שאפשר לצבוע מפה מדינית של העולם בארבעה צבעים בלבד כך ששתי מדינות בעלות גבול משותף ייצבעו בצבעים שונים. מתמטיקאים שיערו שמצב זה אינו מהווה תכונה ייחודית של צורת המדינות בעולמנו, אלא נכון לכל מפה מישורית ולכל צורה של מדינות. ההשערה התבררה כנכונה, אבל לקח כמעט 200 שנה להוכיח אותה: רק בשנות השבעים של המאה הקודמת, ובסיוע מחשב, הצליחו המתמטיקאים אפל והאקן מאוניברסיטת אילינוי להוכיח אותה באופן פורמלי.
בעיות מסוג זה מעניינות לא רק צובעי מפות – למעשה, הן אקטואליות בתחומים רבים אחרים, כגון הקצאת תדרים לאנטנות סלולריות, חלוקת משימות בין מעבדים שונים שעובדים במקביל ועוד. בעקבות כך, בעשורים האחרונים חוקרים רבים התעניינו בבעיות צביעה בהן צובעים עצמים נוספים, ולא רק ארצות על גבי מפה. אחת המפורסמות שבבעיות אלה הוצעה על ידי החוקר הגרמני גרהרד רינגל בשנת 1959: הוא שאל, כמה צבעים מספיקים כדי לצבוע כל קבוצה של מעגלים במישור כך ששני מעגלים המשיקים זה לזה ייצבעו בצבעים שונים? תוך זמן קצר, חוקרים גילו שארבעה צבעים אינם מספיקים, אך שיערו שניתן להסתפק בחמישה. עם זאת, הבעיה נותרה לא פתורה במשך למעלה מ 60 שנה.
לאחרונה, בפרויקט משותף של חמישה חוקרים מאוניברסיטאות שונות בעולם – ד"ר חיה קלר מאוניברסיטת אריאל, פרופ' שחר סמורודינסקי מאוניברסיטת בן גוריון, הדוקטורנט ג'יימס דייויס מאוניברסיטת ווטרלו בקנדה, ד"ר לינדה קלייסט מאוניברסיטת בראונשווייג בגרמניה ופרופ' ברטוש וולצ'ק מאוניברסיטת קרקוב בפולין – נמצא הפתרון לבעיה. מתברר, שההשערה לא הייתה נכונה במקרה הזה: לא רק שחמישה צבעים לא מספיקים, אלא שגם מיליון צבעים לא יספיקו. החוקרים הראו שאין אף מספר סופי של צבעים שיספיק לכדי לצבוע כל קבוצת מעגלים כזו! כדי להראות זאת, החוקרים בנו סדרה של דוגמאות – סידורי מעגלים אותם לא ניתן לצבוע ב 5, 6, 7 צבעים וכן הלאה. את סידורי המעגלים האלה ניתן לתאר באופן מתמטי, אך לא להדגים במציאות – אפילו הסידור שנדרש כדי להוכיח שחמישה צבעים לא מספיקים, כבר מכיל יותר מעגלים ממספר החלקיקים ביקום! המחקר הופיע לאחרונה ברשת, ויוצג בכנס העולמי המרכזי בתחום הגאומטריה החישובית – Symposium on Computational Geometry, שיתקיים ביוני בברלין.
• זאת ההזדמנות שלך! נסדר לך קריירה ונלווה אותך להצלחה - לפרטים נוספים לחצו כאן
פן מעניין של המחקר הוא שכל שיתוף הפעולה המחקרי התבצע באופן מקוון, ולמעשה, רוב החוקרים בקבוצה מעולם לא נפגשו פנים אל פנים. המחקר החל בכנס מקוון בו המשתתפים התחלקו לקבוצות, כאשר כל קבוצה בחרה בעיה לעבוד עליה. חמשת החוקרים בחרו בבעיה הזו, בלי תאום מוקדם ביניהם.
ד"ר חיה קלר מרצה במחלקה למדעי המחשב באוניברסיטת אריאל.
סיימה דוקטורט באוניברסיטה העברית וביצעה מחקרים באוני' בן גוריון ובטכניון.
זכתה במספר פרסים ומלגות, בהם פרס נוריקו סקוראי לפוסט-דוקטורנט מצטיין מאוניברסיטת בן גוריון, מלגת הופמן ומלגת הברונית אריאן דה רוטשילד, פרס שפרינגר ופרס קליין מהאוניברסיטה העברית.
