ראיון עם מריה צ’ודנובסקי

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

תחום עבודתה של מריה הוא תורת הגרפים המבנית. כדי להבין את המילים האלה, יש לדעת תחילה מהו גרף: זהו אוסף זוגות מתוך קבוצה נתונה של איברים שנקראים “קדקוקדים”. למשל, אוסף שלושה הזוגות \({ab,~bc,~ac}\) הוא גרף. הזוגות בגרף נקראים “צלעות”. משמעות השם “גרף” ביוונית היא פשוט “ציור”. הסיבה לשם היא שזוגות אפשר לצייר על ידי קווים – למשל, את הגרף שלעיל אפשר לצייר כשלוש נקודות במישור, עם שלושה קטעים שמחברים ביניהן – זהו פשוט משולש. עכשיו אתם מבינים בוודאי מניין המילה “צלעות”!

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

אחד המושגים המפורסמים ביותר על גרפים הוא “צביעה”. צביעה של גרף היא צביעה של הקדקודים שלו, כך שכל שני קדקודים שמחוברים בצלע צבועים בצבעים שונים. מספר הצביעה של גרף הוא המספר הקטן ביותר של צבעים שמספיקים לצביעתו. למשל, ברור שמספר הצביעה של המשולש הוא \({3}\). נחוץ צבע נפרד לכל קדקוד. מספר הצביעה מסומן באות היוונית \({\chi}\) – זוהי ה”חת” היוונית, ומקור הסימון הוא “חרומו”, שהיא המילה היוונית ל”צבע” (מקובל יותר לכתוב “כרומו”, אבל ה”כף” צריכה להיות לא דגושה. לפחות על פי ההיגוי היווני).

קליק בגרף (“קליקה” פירושה אגודה) הוא קבוצת קדקודים שכולם מחוברים בצלעות. למשל, המשולש הוא קליק. כולם בו מחוברים. ברור שאם בגרף יש קליק בגודל \({k}\) אז נחוצים לפחות \({k}\) צבעים לצביעתו: כל אחד מקדקודי הקליק ידרוש צבע שונה. לא ייתכנו שני קדקודים באותו צבע, כי הרי כל שני קדקודים בקליק מחוברים. מספר הקליק של גרף הוא גודל הקליק המקסימלי. הוא מסומן ב-\({\omega}\) – האות האחרונה באלף בית היווני (אין לי מושג מה מקור הסימון הזה). ובכן, מה שאמרנו זה עתה הוא שבכל גרף מתקיים

\(\displaystyle \chi \ge \omega.\)

יש גרפים שבהם אי השוויון הזה הוא חד. למשל – מחומש:

fift

כאן \({\omega=2}\) בעוד ש-\({\chi=3}\) (בדקו מדוע!)

למעשה, בכל מעגל אי זוגי \({\omega=2}\) ו-\({\chi=3}\). גרף נקרא מושלם אם מתקיים בו \({\omega=\chi}\). ובכן – לא בדיוק. דורשים זאת לא רק לגרף עצמו אלא גם לכל תת גרף מושרה, כלומר גרף שמתקבל מלקיחת חלק מן הקדקודים, עם כל הצלעות בגרף המקורי שמחברות את הקדקודים שלקחנו.

דוגמאות לגרפים מושלמים: מעגל זוגי הוא מושלם. גרף שאין בו מעגלים בכלל הוא מושלם. כך גם כל גרף שמורכב משתי קבוצות \({A}\) ו-\({B}\) של קדקודים, כשכל צלע בגרף מחברת קדקוד ב-\({A}\) עם קדקוד ב-\({B}\) כלומר אין צלעות בתוך \({A}\) וצלעות בתוך \({B}\) – גרף כזה נקרא “דו צדדי”.

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

בשנת \({1978}\) הוכיחו שני מתמטיקאים, לובס ופלקרסון, בנפרד, את המשפט הבא:

משפט 1 גרף הוא מושלם אם ורק אם המשלים שלו הוא מושלם.

בכך הם פתרו את מה שנקרא אז “השערת הגרף המושלם החלשה”. בצידה הייתה השערה חזקה יותר, של המתמטיקאי הצרפתי \({Berge}\). זוהי ההשערה שהוכיחו מריה וחבריה, ואם כן היא עכשיו משפט – “משפט הגרף המושלם”:

משפט 2 גרף הוא מושלם אם ורק אם הוא אינו מכיל כתת גרף מושרה מעגל אי זוגי מאורך \({5}\) או יותר, או משלים של מעגל כזה.

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

אבל בואו נעזוב בזאת את הגרפים, ונפנה לראיון עם מריה. 

נטגר: סיפרת שכילדה בסנט פטרסבורג למדת בבית ספר מיוחד למתמטיקה. איזה חלק הוא מילא בקריירה שלך?

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

נטגר: האם הורייך דחפו אותך?

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

נטגר: האם חשוב להתחיל בגיל צעיר?

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

נטגר: האם עשית משהו מחוץ ללימודים – למשל נגינה בכלי?

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

נטגר: האם את מעדיפה לעבוד לבד או בצוות?

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

נטגר: האם את מעדיפה מתמטיקה אלמנטרית או עם מושגים מורכבים?

מריה: אני מעדיפה מתמטיקה אלמנטרית. אני רוצה לדעת את הכל על הנושא שאני חוקרת מהתחלה עד הסוף – בצורה הקונקרטית ביותר.

נטגר: מהי הבעיה שהיית רוצה יותר מכל לפתור כיום?

מריה: ההשערה שמעניינת אותי ביותר כיום היא השערת ארדש-היינל. בקווים כלליים היא אומרת שלכל גרף קטן – נאמר על \({6}\) קדקודים, אם אוסרים אותו כגרף מושרה של גרף גדול (נקרא לו “הגרף האב”), אז הגרף האב מתנהג בצורה מאוד לא מקרית. ליתר דיוק: הגרף האב חייב אז להכיל קליק גדול, או משלים של קליק גדול. “גדול”, כמובן, הוא ביחס למספר הקדקודים של הגרף האב.

תודתנו נתונה למריה שהסכימה להתראיין.