ז'אק ורסטראטה וסם מתאוס, חוקרים מאוניברסיטת קליפורניה, סן דייגו, עשו פריצת דרך משמעותית בתורת רמזי על ידי פתרון בעיית r(4,t), אתגר שחמק ממתמטיקאים במשך עשרות שנים.
מתמטיקאים באוניברסיטת סן דייגו גילו את הסוד מאחורי מספרי רמזי.
כולנו היינו שם: בהייה במבחן במתמטיקה עם בעיה שנראית בלתי אפשרית לפתרון. מה אם מציאת הפתרון לבעיה לקחה כמעט מאה שנה? למתמטיקאים שמתעסקים בתיאוריית רמזי, זה מאוד המצב. למעשה, התקדמות מועטה הושגה בפתרון בעיות רמזי מאז שנות ה-30.
כעת, חוקרי אוניברסיטת קליפורניה בסן דייגו ז'אק ורסטראטה וסם מתאוס מצאו את התשובה ל-r(4,t), בעיה ארוכת שנים של רמזי שמבלבלת את עולם המתמטיקה במשך עשרות שנים.
מה הייתה הבעיה של רמזי, בכלל?
בשפה מתמטית, גרף הוא סדרה של נקודות והקווים בין הנקודות הללו. תיאוריית רמזי מציעה שאם הגרף גדול מספיק, מובטח שתמצא בתוכו סוג של סדר – או קבוצה של נקודות ללא קווים ביניהן אוֹ קבוצה של נקודות עם כל הקווים האפשריים ביניהן (קבוצות אלה נקראות "קליקות"). זה כתוב בתור r(s,t) where ס הן הנקודות עם קווים ו ט הן הנקודות ללא קווים.
לאלו מאיתנו שאינם עוסקים בתורת הגרפים, בעיית רמזי הידועה ביותר, r(3,3), נקראת לפעמים "המשפט על חברים וזרים" והיא מוסברת בדרך של מסיבה: ב קבוצה של שישה אנשים, תמצא לפחות שלושה אנשים שכולם מכירים אחד את השני או שלושה אנשים שכולם לא מכירים אחד את השני. התשובה ל-r(3,3) היא שש.
בעיות רמזי, כגון r(4,5) הן פשוטות להגדרה, אך כפי שמוצג בגרף זה, הפתרונות האפשריים הם כמעט אינסופיים, מה שהופך אותם לקשים מאוד לפתרון. קרדיט: ז'אק וסטראטה
"זו עובדת טבע, אמת מוחלטת", קובע ורסטראטה. "לא משנה מה המצב או איזה שישה אנשים תבחר – תמצא שלושה אנשים שכולם מכירים אחד את השני או שלושה אנשים שלא כולם מכירים אחד את השני. אולי תוכל למצוא עוד, אבל מובטח לך שיהיו לפחות שלושה בקליקה כזו או אחרת”.
מה קרה לאחר שמתמטיקאים גילו ש-r(3,3) = 6? באופן טבעי, הם רצו לדעת את r(4,4), r(5,5) ו-r(4,t) שבהם מספר הנקודות שאינן מחוברות משתנה. הפתרון ל-r(4,4) הוא 18 והוא מוכח באמצעות משפט שיצרו פול ארדש וג'ורג' סקרס בשנות ה-30.
נכון לעכשיו, r(5,5) עדיין לא ידוע.
בעיה טובה נלחמת
למה משהו כל כך פשוט להצהיר כל כך קשה לפתור? מסתבר שזה יותר מסובך ממה שזה נראה. נניח שידעת שהפתרון ל-r(5,5) הוא איפשהו בין 40-50. אם התחלת עם 45 נקודות, יהיו יותר מ-10234 גרפים שיש לקחת בחשבון!
"מכיוון שהמספרים האלה כל כך קשים לשמצה, מתמטיקאים מחפשים הערכות", הסביר ורסטראטה. "זה מה שסם ואני השגנו בעבודה האחרונה שלנו. איך אנחנו מוצאים לא את התשובה המדויקת, אלא את ההערכות הטובות ביותר לגבי המספרים האלה של רמזי?"
תלמידי מתמטיקה לומדים על בעיות של רמזי בשלב מוקדם, אז r(4,t) נמצא על הרדאר של ורסטראטה במשך רוב הקריירה המקצועית שלו. למעשה, הוא ראה לראשונה את הבעיה בדפוס ב ארדש על גרפים: מורשתו של בעיות בלתי פתורות, נכתב על ידי שני פרופסורים באוניברסיטת סן דייגו, פאן צ'ונג ורון גרהם המנוח. הבעיה היא השערה של Erdös, שהציע 250 דולר לאדם הראשון שיכול לפתור אותה.
"אנשים רבים חשבו על r(4,t) – זו בעיה פתוחה כבר למעלה מ-90 שנה", אמר ורסטראטה. "אבל זה לא היה משהו שהיה בחזית המחקר שלי. כולם יודעים שזה קשה וכולם ניסו להבין את זה, אז אלא אם יש לך רעיון חדש, לא סביר שתגיע לשום מקום".
ואז לפני כארבע שנים, וסטראטה עבד על בעיה אחרת של רמזי עם מתמטיקאי מאוניברסיטת אילינוי-שיקגו, דרוב מוביי. יחד הם גילו שגרפים פסאודו אקראיים יכולים לקדם את הידע הנוכחי על הבעיות הישנות הללו.
בשנת 1937 גילה Erdös ששימוש בגרפים אקראיים יכול לתת גבולות נמוכים טובים לבעיות רמזי. מה ש-Verstraete ומובאי גילו זה הדגימה הזו מדומהגרפים אקראיים נותנים לעתים קרובות גבולות טובים יותר למספרי רמזי מאשר גרפים אקראיים. הגבול הזה – הגבול העליון והתחתון של התשובה האפשרית – הקשיח את טווח ההערכות שהם יכלו לעשות. במילים אחרות, הם התקרבו לאמת.
בשנת 2019, לשמחתו של עולם המתמטיקה, וסטראטה ומובאיי השתמשו בגרפים פסאודו אקראיים כדי לפתור את r(3,t). עם זאת, Verstraete נאבק לבנות גרף פסאודו אקראי שיכול לעזור לפתור את r(4,t).
הוא החל למשוך תחומים שונים של מתמטיקה מחוץ לקומבינטוריקה, כולל גיאומטריה סופית, אלגברה והסתברות. בסופו של דבר, הוא איחד כוחות עם מתאוס, חוקר פוסט-דוקטורט בקבוצתו שהרקע שלו היה בגיאומטריה סופית.
"התברר שאפשר למצוא את הגרף הפסאודורנדומלי שהיינו צריכים בגיאומטריה סופית", קבע ורסטראטה. "סם היה האדם המושלם לבוא ולעזור לבנות את מה שהיינו צריכים."
ברגע שהיה להם את הגרף הפסאודו-אקראי, הם עדיין היו צריכים לחשוב על כמה פיסות מתמטיקה. זה לקח כמעט שנה, אבל בסופו של דבר, הם הבינו שיש להם פתרון: r(4,t) קרוב לפונקציה מעוקבת של ט. אם אתה רוצה מסיבה שבה תמיד יהיו ארבעה אנשים שכולם מכירים אחד את השני או ט אנשים שכולם לא מכירים אחד את השני, תצטרך בערך לא3 אנשים נוכחים. יש כוכבית קטנה (למעשה o) כי, זכור, זו הערכה, לא תשובה מדויקת. אבל ט3 קרוב מאוד לתשובה המדויקת.
הממצאים נמצאים כעת בבדיקה עם דברי ימי המתמטיקה.
"זה באמת לקח לנו שנים לפתור", הצהיר ורסטראטה. "והיו הרבה פעמים שבהם נתקענו ותהינו אם נוכל לפתור את זה בכלל. אבל לעולם אסור לוותר, לא משנה כמה זמן זה ייקח".
Verstraete מדגיש את החשיבות של התמדה – משהו שהוא מזכיר לתלמידיו לעתים קרובות. "אם אתה מגלה שהבעיה קשה ואתה תקוע, זה אומר שזו בעיה טובה. פאן צ'ונג אמר שבעיה טובה נלחמת. אתה לא יכול לצפות שזה רק יחשף את עצמו".
וסטראטה יודע שנחישות כה עיקשת מתוגמלת היטב: "קיבלתי טלפון ממעריץ שאומר שהיא חייבת לי 250 דולר."
