מבט מקרוב חושף את נקודת 'ההתכה' של גרף אינסופי | מגזין קוונטה

בשנת 2008, מת המתמטיקאי עודד שרם בתאונת טיול בהרי קסקייד כ-50 קילומטרים מזרחית לסיאטל. למרות שהוא היה רק ​​בן 46, הוא בנה תחומים חדשים לגמרי במתמטיקה.

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

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

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

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

"זה מאמר מדהים. זו הצטברות של עבודה ארוכה", אמר בנימין.

אשכולות אינסופיים

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

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

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

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

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

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

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

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

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

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

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

הרחבת העדשה

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

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

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

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

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

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

עבור הרשת הריבועית, ספירת הקודקודים גדלה לאט יחסית. זה בערך רוחב העדשה שלך בריבוע. לאחר 10 צעדים, תמצא כ-100 קודקודים. אבל עץ 3 רגיל גדל מהר יותר באופן אקספוננציאלי - בערך 2 מורם לעוצמה של רוחב העדשה שלך. לאחר 10 צעדים, תראה כ-1,024 קודקודים. האיור שלהלן מראה כיצד העץ ה-3 הרגיל גדול בהרבה לאחר שבעה שלבים בלבד, למרות שלרשת המרובעת יש יותר קודקודים בהתחלה. באופן כללי, לגרפים יכולים להיות קצבי צמיחה שונים בהיקפים שונים - הם עשויים להתחיל מהר, ואז להאט.

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

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

מבנה מול הרחבה

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

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

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

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

באמצע שום מקום

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

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

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

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

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

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

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

תיקון: דצמבר 18, 2023
מספר הצמתים בתוך n קישורים של צומת התחלה בגרף 3 רגיל גדל בערך ל-2ⁿ, לא 3ⁿ כפי שכתב מאמר זה במקור. המאמר תוקן.

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