כלל ה-0-1 של גרפים - הקדמה

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

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

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

הזכרתי שפות מסדר ראשון לא מזמן, ואחזור על כך שוב, בהקשר הספציפי של גרפים: השפה שעליה אנחנו הולכים לדבר כוללת סימנים של משתנים כמו \( v,u \) וכדומה; את הסימן \( E\left(x,y\right) \) שמסמן את הטענה “יש קשת בין \( x \) ל-\( y \)”; את סימן השוויון \( = \), כך שמשמעות \( x=y \) היא “\( x \) הוא אותה הצומת כמו \( y \)”; קשרים לוגיים, כמו \( \wedge \) (וגם), \( \vee \) (או), \( \to \)(גורר) ו-\( \neg \) (לא); וכמתים - \( \exists \) שמציין “קיים” ו-\( \forall \) שמציין “לכל”. מכל היצורים הללו בונים פסוקים - סדרות של סמלים שמייצגות טענות מתמטיות. לא אכנס לפרטים המדוייקים של איך הבניה הזו עובדת פורמלית ומה נחשב פסוק חוקי, אלא אסתפק בדוגמאות. למשל, \( \forall v\exists u\left(E\left(v,u\right)\right) \) הוא פסוק שאומר את הטענה “לכל צומת \( v \) קיים צומת \( u \) שמחובר אליו בקשת” - במילים אחרות, אין צומת מבודד. דוגמה נוספת: \( \exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right) \) פירושו “קיימים שלושה צמתים \( v_{1},v_{2},v_{3} \) שכולם מחוברים האחד אל השני” - במילים אחרות, בגרף יש משולש.

כאן נכנס לתמונה המושג של מודל עבור פסוקים. מודל (בנפנוף ידיים פרוע) הוא קבוצה של איברים, שהם הערכים שהמשתנים יכולים לקבל, ושל יחסים - במקרה הזה, יחס אחד שמותאם ליחס \( E \) שיש בשפה שתיארתי. גרף הוא מודל לגיטימי כאן, עם המשמעות הרגילה - אבריו הם הצמתים, והיחס הוא “בין \( v \) ל-\( u \) יש קשת”. מצד שני, אפשר לחשוב גם על מודלים אחרים; למשל, המספרים הטבעיים עם היחס “קטן מ-“. כלומר, \( E\left(v,u\right) \), תחת הפרשנות של “\( u,v \) הם מספרים טבעיים ו-\( E \) הוא היחס “קטן מ-“”. אם כן, קצת רימיתי קודם - \( \forall v\exists u\left(E\left(v,u\right)\right) \) לא באמת אומר “לכל צומת \( v \) קיים צומת \( u \) שמחובר אליו בקשת” - כאן אנחנו מייחסים משמעות לסמלים - אלא רק אומר “לכל \( v \) קיים \( u \) כך שמתקיים ביניהם היחס \( E \)”. מהם \( v,u \) ומהו היחס \( E \)? זה תלוי בפרשנות שלנו, וזה מה שמודל מנסה לעשות - לתת פרשנות. במודל של המספרים הטבעיים, הפסוק הזה ניתן לתרגום בתור “לכל מספר \( v \) קיים מספר \( u \) הגדול ממנו”, וזו בוודאי טענה שנכונה במספרים הטבעיים. לעומת זאת, הפסוק השני שהבאתי, עם ה”משולש”, לא נכון במספרים הטבעיים - לא קיימים שלושה מספרים טבעיים כך שכל אחד גדול מקודמו; רק בציורים של אשר, אולי.

בקיצור, מודל הוא פרשנות כלשהי של השפה, וכל פסוק יכול להיות או נכון או לא נכון ביחס לאותו מודל. אם יש לנו פסוק \( \varphi \) ו-\( M \) הוא מודל שבו \( \varphi \) נכון, אומרים ש-\( M \) מספק את \( \varphi \) ומסמנים את זה \( M\vdash\varphi \) (למעשה, זה לא הסימון הסטנדרטי אלא כזה שבו הקו המאוזן הוא כפול, אבל אני נאלץ להשתמש בסימון הזה, שבדרך כלל אומר “מוכיח”, מסיבות טכניות). באופן דומה, אם \( T \) היא קבוצה של פסוקים ו-\( M \) הוא מודל שמספק את כולם, אומרים ש-\( M \) הוא מודל של \( T \) ומסמנים \( M\vdash T \). לסיום, לאוסף פסוקים קוראים תורה.

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

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

אם כן, נצטמצם באופן הבא: ראשית, נדבר רק על גרפים עם \( n \) צמתים. שנית, הליך ההגרלה של הגרף יהיה כזה: נעבור על כל זוג צמתים \( \left(u,v\right) \) ונטיל מטבע כדי לקבוע אם תהיה בינם קשת או לא. ליצור הזה, גרף שבו כל קשת קיימת בהסתברות כלשהי, קוראים “גרף מקרי”; אסמן אותו בתור \( G_{\frac{1}{2}}\left(n\right) \), כש-\( n \) מסמן שיש בו \( n \) צמתים וה-\( \frac{1}{2} \) הוא ההסתברות לקיום קשת (כל מה שאראה בהמשך תקף גם להסתברויות קבועות אחרות, ואפילו לחלק מההסתברויות שתלויות ב-\( n \); לא ארחיב על כך). את השאלה אפשר כעת לנסח באופן יותר מדוייק - מה ההסתברות שהגרף המקרי \( G_{\frac{1}{2}}\left(n\right) \) יהיה קשיר? כלומר, מה ההסתברות שאם נבצע את אותה הגרלת קשתות שתיארתי, מה שנקבל יהיה קשיר?

התשובה היא שההסתברות היא גבוהה מאוד, אך לא אוכל להראות זאת כרגע. לכן אסתפק בתכונה “צנועה” יותר - קיום משולש בגרף. הבה נסמן ב-\( p_{n} \) את ההסתברות שאם נגריל גרף מגודל \( n \) יהיה בו משולש. ברור ש-\( p_{1}=p_{2}=0 \), כי לא יכול להיות משולש בגרף שיש בו רק שני צמתים; לעומת זאת \( p_{3}=\frac{1}{8} \), כי כדי שיהיה לי משולש בגרף בן שלושה צמתים צריך שכל שלוש הקשתות ביניהם יתקיימו (יש הסתברות \( \frac{1}{2} \) לכל קשת, ולכן ההסתברות שכל הקשתות יהיו בגרף היא \( \frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{8} \)). ומהו \( p_{4} \)? כאן החישוב כבר נעשה מסובך יותר כי יש הרבה אפשרויות, והן תלויות זו בזו; אבל די ברור שההסתברות תהיה גדולה מ-\( \frac{1}{8} \), כי יש הרבה יותר “משולשים פוטנציאליים”. אם נמשיך ונגדיל את \( n \), גם \( p_{n} \) ימשיך לגדול. נשאלת השאלה - עד מתי? האם נגיע לאיזה שהוא מחסום, למשל נראה שלכל \( n \), ההסתברות \( p_{n} \) היא לא יותר מחצי? או שמא היא תשאף עוד ועוד ל-1, כלומר באופן מעשי יהיה אפשר לומר “בגרפים גדולים דיו, כמעט כולם מכילים משולש”? מסתבר שהתשובה היא ש-\( p_{n} \) אכן ישאף ל-1, והמשפט שאליו אני חותר מוכיח זאת בקלות.

הבה ונעבור לתכונה אחרת - “כל שני צמתים בגרף מחוברים” (לגרף כזה קוראים “קליק”, מלשון Clique). את התכונה הזו אפשר לתאר עם השפה מסדר ראשון שתיארתי קודם בקלות: \( \forall v,u\left(E\left(v,u\right)\right) \). מה ההסתברות של התכונה הזו? כאן החישוב הוא קל מאוד: בגרף עם \( n \) צמתים, יש \( {n \choose 2}=\frac{n\left(n-1\right)}{2} \) קשתות פוטנציאליות; מכיוון שכולן חייבות להיות בגרף, ההסתברות לכך שגרף יהיה קליק היא \( \frac{1}{2^{\frac{n\left(n-1\right)}{2}}} \). האיברים הראשונים בסדרת ההסתברויות הזו הם \( 1,\frac{1}{2},\frac{1}{8},\frac{1}{64},\dots \) ולא קשה לראות ש-\( p_{n} \) הולך וקטן בקצב מהיר למדי ככל ש-\( n \) גדל. אם כן, עבור ערכים גדולים של \( n \), \( p_{n} \) יהיה אפס לכל צורך מעשי - אם נגריל גרף גדול, ההסתברות שנקבל קליק היא אפסית.

הבה ונכליל את מה שדיברנו עליו עד כה. נניח ש-\( \mathcal{P} \) היא תכונה כלשהי של גרף. נסמן ב-\( p\left(\mathcal{P}\right) \) את הערך שאליו ההסתברות לקיום \( \mathcal{P} \) שואפת ככל שמגדילים את מספר הצמתים בגרף. פורמלית, למי שמעוניין, ההגדרה תהיה \( p\left(\mathcal{P}\right)=\lim_{n\to\infty}p_{n}\left(\mathcal{P}\right) \). ראינו כי \( p\left(\mathcal{P}\right)=1 \) עבור התכונה “הגרף מכיל משולש” ו-\( p\left(\mathcal{P}\right)=0 \) עבור התכונה “הגרף הוא קליק”. האם נוכל למצוא מקרים מעניינים יותר, שאינם 0 או 1?

ובכן, הנה תכונה “טיפשית” משהו: “מספר הקשתות בגרף הוא זוגי”. אם אנחנו מגרילים גרף, מה ההסתברות שנקבל מספר זוגי של קשתות? טיעון פשוט מראה שההסתברות הזו היא חצי; נניח שהגרלנו כבר את כל הקשתות בגרף למעט אחת. אם מספר הקשתות זוגי, אז הוא יישאר כזה אם ההגרלה של הקשת האחרונה תכריע שהיא לא תתווסף לגרף; ואם מספר הקשתות אי זוגי, אז הוא יהפוך לזוגי אם ההגרלה תכריע שהקשת כן תתווסף לגרף. בקיצור, ההסתברות שנקבל גרף זוגי היא \( \frac{1}{2} \), בהינתן שההגרלה של הקשת האחרונה נתנה את התוצאה ה”נכונה”. הנימוק הזה הוא קצת נפנוף-ידיימי, אבל לא קשה לפרמל אותו. אם כן, \( p\left(\mathcal{P}\right)=\frac{1}{2} \) במקרה הזה.

והנה עוד תכונה טיפשית: “בגרף יש מספר זוגי של צמתים”. למה טיפשית? כי היא בכלל לא תלויה בקשתות, שזה מה שאנחנו מגרילים כאן. אם \( n \) הוא זוגי, אז \( p_{n}=1 \) כי בכל גרף שנגריל על \( n \) צמתים נקבל גרף עם מספר זוגי של צמתים, ואם \( n \) אי זוגי אז \( p_{n}=0 \). זה מראה לנו שאי אפשר להגיד שההסתברות “הולכת” לשום מקום - היא מזפזפת כל הזמן בין 0 ו-1, והגבול \( \lim_{n\to\infty}p_{n}\left(\mathcal{P}\right) \) בכלל לא קיים; במקרה הזה אומרים ש-\( p\left(\mathcal{P}\right) \) לא מוגדר.

תכונה אחת לסיום, שגם בה יש “זפזופ” שכזה אבל הוא מזיק הרבה פחות - התכונה “הגרף הוא שידוך מושלם”. שידוך מושלם הוא גרף שבו הצמתים מחולקים לזוגות-זוגות, כך שבין כל זוג יש קשת ואין עוד קשתות (תחשבו על קשת כמייצגת שני בני זוג; השידוך הוא “מושלם” למי שתומך בנישואים מונוגמיים). די ברור שבגרף עם מספר אי זוגי של צמתים נקבל שוב \( p_{n}\left(\mathcal{P}\right)=0 \), כי בכל חלוקה לזוגות יישאר רווק הולל; ואילו עבור מספר זוגי של צמתים נקבל ש-\( p_{n}\left(\mathcal{P}\right) \) גדול מאפס (זה תרגיל נחמד בקומבינטוריקה לחשב אותו במדוייק), אבל לא “יותר מדי”; לא קשה להראות ש-\( p_{n}\left(\mathcal{P}\right) \) שואף לאפס, כאשר \( n \) מקבל ערכים זוגיים. אם כן, למרות שיש “זפזופ” בין הסתברות אפס והסתברות שאינה אפס, אנחנו עדיין מקבלים \( p\left(\mathcal{P}\right)=0 \).

גם את התכונה של השידוך המושלם אני יכול לתאר באמצעות השפה שלי: \( \forall v\exists u\left(E\left(v,u\right)\wedge\forall w\left(E\left(v,w\right)\to u=w\right)\right) \), כלומר “לכל צומת \( v \) קיים שכן \( u \), והשכן הזה הוא יחיד, דהיינו אם גם \( w \) הוא שכן של \( v \) אז \( u=w \)”.

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

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

אפשר “להשתמש” במשפט בכמה דרכים. ראשית, מכיוון שהתכונה “יש בגרף מספר זוגי של צמתים” מובילה להסתברות לא מוגדרת (ובפרט לא ל-0 או 1) נובע מיידית שהתכונה הזו לא ניתנת לתיאור באמצעות לוגיקה של סדר ראשון. אם כן, אפשר להוכיח עם המשפט שתכונות מסויימות של גרפים אינן בנות-הגדרה בלוגיקה מסדר ראשון. שנית, את התכונה של “הגרף הוא שידוך מושלם” ראיתי שניתן להגדיר בלוגיקה מסדר ראשון, וגם ראיתי שעל אינסוף ערכים של \( n \) מקבלים \( p_{n}\left(\mathcal{P}\right)=0 \); מכאן שבהכרח \( p\left(\mathcal{P}\right)=0 \), ולכן אני יודע שההסתברות לקבלת גרף שהוא שידוך מושלם, גם כאשר מגרילים גרף על מספר זוגי של צמתים, שואפת לאפס - וזאת מבלי שהייתי צריך לחשב את ההסתברות הזו בכלל! זה “שימוש” אחר של המשפט. באופן דומה אפשר לראות שההסתברות שבגרף יהיה משולש שואפת ל-1, בלי להיכנס לחישובים מסובכים יותר מאלו שהצגתי כאן: ההסתברות היא תמיד גדולה מ-\( \frac{1}{8} \) (כי בגרף עם שלושה צמתים היא \( \frac{1}{8} \), ובגרף גדול יותר היא תהיה רק גדולה יותר כי יש עוד הזדמנויות לקיום משולש), ומכיוון שנתתי נוסחה מסדר ראשון לתיאור התכונה של “בגרף יש משולש”, היא או 0 או 1, אבל 0 היא לא יכולה להיות כי היא גדולה מ-\( \frac{1}{8} \), ולכן היא 1.

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

כך או כך, מדובר במשפט יפה; אבל מה שהופך אותו ליפה עוד יותר הוא ההוכחה שלו, שאציג בפוסט הבא.