קפיצת מדרגה קטנה מאוד בתורת הגרפים

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

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

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

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

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

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

קווי המפלגה

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

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

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

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

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

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

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

זה לא כל כך קשה להראות שמספר רמזי עבור קליקה בגודל 3, או R(3), הוא 6 (ראה גרפיקה). אך רק בשנת 1955 הוצמד R(4) ל-18. R(5) נותר לא ידוע - הוא לפחות 43 ולא גדול מ-48. למרות שהמספרים הללו קטנים, סינון כל הצבעים האפשריים לא יצא לפועל. של השאלה, אמר דיוויד קונלון מהמכון הטכנולוגי של קליפורניה. שקול את מספר הצביעה בגרף שלם עם 43 צמתים. "יש לך 903 קצוות; ניתן לצבוע כל אחד מהם בשתי דרכים", הסביר. "אז אתה מקבל 2⁹⁰³, שהוא פשוט גדול מבחינה אסטרונומית".

ככל שגודל הקליקה גדל, המשימה של להדביק את המספר של רמזי רק הולכת ונעשית קשה יותר. ארדס צייץ שמלחמה כוללת עם חייזרים תובעניים מתמטית תהיה קלה יותר מאשר לנסות להבין R(6), שהוא איפשהו בין 102 ל-165. טווח אי הוודאות גדל במהירות: לפי הערכות שערך סטניסלב רדזישובסקי, R(10) יכול להיות קטן כמו 798 וגדול כמו 23,556. אבל המטרות של מתמטיקאים מגיעות הרבה מעבר למספר רמזי של 10. הם רוצים נוסחה שתיתן הערכה טובה של R(k), אפילו - או במיוחד - מתי k הוא גדול במיוחד.

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

צו בבית המשפט

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

חמש שנים מאוחר יותר, Erdős ו Szekeres הראו שמספר רמזי של k פחות מ -4^k. ו-12 שנים אחרי זה, Erdős הראה שהוא גדול יותר מ-$latex sqrt{2}^k$ בערך. כדי לעשות זאת, הוא חישב את הסיכויים שגרף עם קצוות בצבע אקראי מכיל קליק מונוכרומטי. טכניקה "הסתברותית" זו הפכה למשפיעה מאוד בתורת הגרפים. זה גם לכד את R(k) בין שני עמודי יעד בצמיחה אקספוננציאלית: $latex sqrt{2}^k$ ו-$latex 4^k$.

ככל שחלפו העשורים, מתמטיקאים רבים ניסו לצמצם את הפער בין הערכים האפשריים של מספר רמזי. חלקם הצליחו: ב-1975, ג'ואל ספנסר הכפיל את הגבול התחתון. וסדרת מאמרים מאת קונלון, אנדרו תומאסון ו אשווין סאה דחף את הגבול העליון למטה לפי פקטור של כ-$latex 4^{log(k)^2}$ עד 2020. אבל בהשוואה לגדלים של הגבול על מספר Ramsey, ההתאמות הללו היו קטנות. לעומת זאת, כל הפחתה ל-4 בנוסחה של ארדס ושקרס R(k) < 4^k יהיה שיפור אקספוננציאלי, שיגדל במהירות כמו k הולך וגדל.

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

תורת המשחקים

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

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

התוכנית שלהם הייתה לבנות על רעיונות ששימשו בהוכחה המקורית של Erdős ו-Szekeres ש-$latex R(k) < 4^k$. כדי להוכיח שמספר רמזי הוא לכל היותר $latex 4^k$, דמיינו משחק על גרף שלם עם צמתים של $latex 4^k$. במשחק יש שני שחקנים. ראשית, היריב שלך צובע כל קצה אדום או כחול, בתקווה לצבוע את הקצוות בצורה שתמנע יצירת קליק מונוכרומטי של k צמתים.

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

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

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

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

כשתסיים, הסתכל לתוך הדליים. מכיוון שצומת נכנס לדלי האדום רק לאחר שהשכנים הכחולים שלו חוסלו, כל הצמתים בדלי האדום מחוברים בקצוות אדומים - הם יוצרים קליקה אדומה. כמו כן, הדלי הכחול יוצר קליק כחול. אם הגרף המקורי שלך כולל צמתים של $latex 4^k$ לפחות, אפשר להוכיח שאחד מהדליים האלה חייב להכיל לפחות k צמתים, המבטיחים קליק מונוכרומטי בגרף המקורי.

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

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

מבחן ספר פתוח

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

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

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

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

בינואר הקרוב הסכימו ארבעת המתמטיקאים לעבור לגרסה אחרת של הבעיה. הגרסה הזו נשמעת מסובכת יותר, אבל התברר שהיא קלה יותר.

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

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

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

אפסילון, אפסילון

לאחר השיחות ב-16 במרץ, המשתתפים החלו לאשר את השמועות. תמונות מהשיחה של סהאסרבודהה הופצו באמצעות שיחות טלפון והודעות פרטיות - אפילו ב פוסט מעורפל אך מרמז בבלוג של המתמטיקאי גיל קלאי. Campos, Griffiths, Sahasrabudhe ומוריס טענו שהראו ש-$latex R(k) < 3.993^k$. באותו לילה, ארבעת המחברים פרסמו את העיתון שלהם באינטרנט, המאפשר למתמטיקאים לראות את ההוכחה החדשה בעצמם.

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

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

"זו הוכחה גאונית לחלוטין, נפלאה לחלוטין, ופריצת דרך אמיתית. אז עכשיו אני מצפה שהשערים ייפתחו", אמר בולובאס. "אני משוכנע שבעוד שלוש שנים הדיון יהיה על שיפורים אפשריים. האם נוכל לשפר את 3.993 ל-3.9? אולי עד 3.4? ומה עם 3?"

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

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