ארכיון התג: גרפים

משפט טורן והולדת תורת הגרפים האקסטרמלית

פורסם בתאריך על ידי
12

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

הפעם אני רוצה לעסוק בתחום דומה בקומבינטוריקה (תת-תחום של תורת רמזי? המעמד הרשמי לא ממש חשוב) – תורת הגרפים האקסטרמלית. כפי שניתן לנחש, האובייקטים שלנו כאן הם גרפים (אבל נו באמת – איזה אובייקט ביקום לא ניתן לתיאור על ידי גרף?) ואנחנו רוצים להבין את תכונותיהם של הגרפים הקיצוניים ביותר שמקיימים (או שלא מקיימים) תכונה כלשהי. באופן קצת יותר קונקרטי, עבור תכונה \(\Phi\) כלשהי של גרפים, שאלה מרכזית היא זו: מה המספר המקסימלי של קשתות שגרף עם \(n\) צמתים יכול להכיל ועדיין לקיים את התכונה \(\Phi\)? המספר הזה מסומן לרוב כ-\(\mbox{ex}\left(n,\Phi\right)\) (אפשר לחשוב עליו כפונקציה של \(n\) עם פרמטר \(\Phi\)). לא תמיד אפשר לדעת במדויק את \(\mbox{ex}\left(n,\Phi\right)\), כמובן, ולרוב מסתפקים בהערכה.

המקרה המעניין הראשון הוא זה שבו \(\Phi\) היא התכונה "להכיל תת-גרף מסויים". אז אנחנו שואלים את השאלה הקלאסית של תורת רמזי – מתי אובייקט הוא גדול דיו כדי שמבנה מסויים יצוץ בתוכו לבטח? ומשפט טורן מטפל בתת גרף פשוט במיוחד: קליק. קליק מגודל \(t\), שאותו אסמן ב-\(K_{t}\), הוא פשוט קבוצה של \(t\) צמתים שכולם מחוברים אלה לאלה בקשתות. שימו לב להבדל בין זה ומשפט רמזי, שמדבר על מספר הצמתים שצריך להיות בגרף לפני שיצוץ בו קליק מגודל מסויים או קבוצה בלתי תלויה מגודל מסויים; כאן מספר הצמתים \(n\) קבוע ונתון מראש ואנחנו רוצים לדעת מה מספר הקשתות; ולהבדיל ממשפט רמזי, כאן אנחנו יודעים את \(\mbox{ex}\left(n,K_{t}\right)\) במדויק וגם יודעים בדיוק איך הגרפים הקיצוניים (בעלי המספר המקסימלי של קשתות שאינם מכילים את \(K_{t}\)) נראים.

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

התעלול הוא להשתמש במה שנקרא "גרף דו צדדי". גרף דו צדדי הוא כזה שניתן לחלק את צמתיו לשתי קבוצות – הטובים והרעים – כך שכל צומת שייך לאחת מהקבוצות, וכל קשת בהכרח מחברת בין טוב ורע; אין קשת בין שני טובים, או קשת בין שני רעים. בגרף כזה לא יכול להיות משולש, כי בקבוצה של שלושה קודקודים יש שני טובים (שאינם מחוברים בקשת) או שני רעים (שאינם מחוברים בקשת). מצד שני, בגלל שאנחנו יודעים שבגרף דו צדדי מובטח לנו שלא יהיה משולש אנחנו יכולים להתפרע ולהוסיף כמה קשתות שבא לנו כל עוד הן לא מחברות שני טובים או שני רעים. באופן כללי אם יש \(a\) טובים ו-\(b\) רעים וכל טוב מחובר לרע בקשת יהיו לנו \(ab\) קשתות בגרף. מכיוון ש-\(n=a+b\), זה אומר שיהיו לנו \(a\left(n-a\right)=na-a^{2}\) קשתות בגרף, והשאלה היא איזה ערך של \(a\) ייתן לנו את המקסימום. קצת חשבון דיפרנציאלי (אני לא אומר שאין דרכים אחרות, ועוד נראה כאלו) נותן בקלות את התשובה הלא מפתיעה – \(a=\frac{n}{2}\) (אם \(n\) אי זוגי מעגלים כלפי מטה או מעלה, זה לא משנה). כלומר המספר המקסימלי של קשתות מתקבל כאשר מחלקים את הגרף לשתי קבוצות שוות של צמתים, ואז יהיו \(\frac{n^{2}}{4}\) קשתות. כלומר, \(\mbox{ex}\left(n,K_{3}\right)=\frac{n^{2}}{4}\). כל זה היה ידוע בימיו של טורן; המשפט שלו הוא פשוט הכללה רדיקלית שנותנת את \(\mbox{ex}\left(n,K_{t}\right)\)לכל \(t\).

כדי לפשט טיפה את הסימונים מכאן ואילך אניח שאנחנו מנסים למצוא את \(\mbox{ex}\left(n,K_{t+1}\right)\); עוד שניה יהיה ברור לכולם למה עדיף לדבר על \(t+1\) כאן.

הצעד הראשון הוא לנסות ולבנות גרפים גדולים ככל האפשר שאינם מכילים קליק מגודל \(t+1\). ממש מתבקש להכליל כאן את הרעיון שכבר הצגתי – במקום גרף דו-צדדי, לקחת גרף \(t\) צדדי, כלומר כזה שבו הצמתים מחולקים ל-\(t\) קבוצות ואין קשת בין שני חברי אותה קבוצה (אבל כל צומת מקבוצה מסויימת יכול להיות מחובר לכל צומת מכל קבוצה אחרת). ההוכחה שאין בגרף כזה קליק מגודל \(t+1\) זהה: אם יש \(t+1\) צמתים יש לפחות שני צמתים מאותה קבוצה (זהו עקרון שובך היונים בפעולה) ולכן זוג צמתים בלי קשת ביניהם).

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

לצורך פשטות נניח מכאן ואילך ש-\(t\) מחלק את \(n\), אחרת סתם הסימונים שלנו יהיו מסורבלים בהרבה. במקרה הזה, כל הקבוצות יהיו מאותו גודל – \(\frac{n}{t}\). כמה קשתות יהיו? כמו שראינו קודם, בין כל שתי קבוצות של צמתים מחברות \(\frac{n^{2}}{t^{2}}\) קשתות; ויש לנו \({t \choose 2}=\frac{t\left(t-1\right)}{2}\) זוגות (למי שלא מכיר את הסימון הזה – נעים להכיר). לכן יש בסך הכל \(\frac{t\left(t-1\right)}{2}\cdot\frac{n^{2}}{t^{2}}=\frac{t-1}{t}\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\) קשתות.

כעת אפשר לנסח את משפט טורן. פורמלית, הוא אומר ש-\(\mbox{ex}\left(n,K_{t+1}\right)=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\), אבל ניסוחים כאלו הם אחד מהדברים השנואים עלי במתמטיקה. לא כי הוא לא נכון או לא מדויק או כל דבר אחר, אלא כי אם זה מה שתראו למישהו מבחוץ הוא לא יבין את הקטע. אוקיי, אז יש לנו איזו נוסחה לא יפה במיוחד עבור \(\mbox{ex}\left(n,K_{t+1}\right)\), אז מה? הפואנטה כאן לטעמי היא שמשפט טורן אומר שהגרפים האקסטרמליים במקרה הזה הם אכן הגרפים ה-\(t\) צדדיים שבנינו – דרך הרבה יותר ציורית ויפה להבין את המספר \(\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\) (כמובן, לערך המספרי יש חשיבות ביישומים של המשפט). כך זה תמיד במתמטיקה – המטרה היא לא איזו נוסחה סגורה מפוצצת, אלא ההבנה של התופעה שמאחורי הנוסחה (הבנה שלא תהיה שלמה עד שההוכחות לא יסייעו לנו להבין למה הגרפים ה-\(t\) צדדיים הם אכן אקסטרמליים).

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

ראשית, ניסוח מדויק של המשפט שכוחו יפה גם ל-\(n\) שלא מתחלק על ידי \(t\): אם \(G\) הוא גרף בעל \(n\) צמתים ואין בו קליק מגודל \(t+1\) (כאשר \(t\ge2\)), אז מספר הקשתות ב-\(G\) הוא לא יותר מ-\(\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\).

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

\(\frac{n\left(n-1\right)}{2}\le\left(t-1\right)\frac{n}{2}\le\frac{t-1}{t}\cdot\frac{n^{2}}{2}=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

כך שעם זה סיימנו. החלק המעניין הוא לטפל במקרה שבו \(n>t\). מספיק להראות שבגרף עם מספר קשתות מקסימלי (ביחס לתכונה "לא מכיל את \(K_{t+1}\)) מתקיים החסם הנדרש, כי לכל גרף אחר אפשר להוסיף קשתות עד שמגיעים לגרף מקסימלי שכזה. גרף מקסימלי שכזה בהכרח יכיל את \(K_{t}\) (כי אם לא, הוא לא היה מקסימלי; הוספה של קשת לא הייתה יכול ליצור את \(K_{t+1}\) כי מ-\(K_{t+1}\) אפשר לקבל את \(K_{t}\) על ידי הסרה של קשת אחת וסילוק אחד הצמתים שמחוברים אליה). הרעיון הוא כעת לחלק את הגרף לשני חלקים: \(A\) תהיה קבוצת הצמתים של הקליק מגודל \(t\) הזה, ו-\(B\) תהיה קבוצת שאר הצמתים.

ב-\(A\) יש בדיוק \({t \choose 2}\) קשתות שהרי בין כל זוג צמתים שם יש קשת. על \(B\) אנחנו יכולים להשתמש בהנחת האינדוקציה כי מספר הצמתים בה קטן מ-\(n\), כך שאנחנו יודעים שיש בה לכל היותר \(\left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2}\) קשתות. אילו עוד קשתות יכולות להתקיים בגרף? כאלו שמחברות את \(A\) עם \(B\). כל צומת ב-\(B\) יכולה להתחבר כמעט לכל הצמתים של \(A\), אבל רק כמעט; אם היא תתחבר לכל הצמתים של \(A\), אז היא יחד עם \(A\) יהוו קליק מגודל \(t+1\). לכן כל צומת מ-\(B\) מחוברת בקשת לכל היותר ל-\(t-1\) צמתים מ-\(A\). אלו כל האבחנות שצריך, והיתר הוא חשבון מכולת. אנחנו מקבלים שמספר הקשתות הכולל בגרף חסום על ידי:

\({t \choose 2}+\left(1-\frac{1}{t}\right)\frac{\left(n-t\right)^{2}}{2}+\left(n-t\right)\left(t-1\right)\)

אחרי סידור מחדש קטן מקבלים שזה שווה ל:

\(\left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)^{2}}{2t}+\left(n-t\right)\right]=\left(t-1\right)\left[\frac{t}{2}+\frac{\left(n-t\right)\left(n+t\right)}{2t}\right]\)

\(=\left(t-1\right)\left[\frac{t^{2}+n^{2}-t^{2}}{2t}\right]=\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

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

כמובן, אין כאן שום קסם אמיתי, זה היופי בהוכחה הזו – התוצאה חייבת להתקבל, אין מנוס מכך. יש לנו כאן דוגמה קלאסית להוכחה באינדוקציה: ראשית, טורן מזהה מרכיב כלשהו שחייב להופיע בגרף אקסטרימלי כלשהו (\(K_{t}\)). האבחנה הזו היא המפתח לנצחון, ומאותו רגע ההמשך מתבקש: לפרק את הגרף, למתוח כמה קשתות שרק אפשר בין הרכיבים, ולהשתמש בהנחת האינדוקציה על מה שנשאר. בעצם טורן מראה כאן ש-\(\mbox{ex}\left(n,K_{t+1}\right)\) מקיים את נוסחת הנסיגה \(\mbox{ex}\left(n,K_{t+1}\right)=\mbox{ex}\left(n-t,K_{t+1}\right)+{t \choose 2}+\left(n-t\right)\left(t-1\right)\) עבור \(n>t\), רק שכאן אין לנו צורך לפתור את הנוסחה הזו כי כבר היה לנו ניחוש מוצלח לגבי הערך של \(\mbox{ex}\left(n,K_{t+1}\right)\) מלכתחילה (בסיטואציות קומבינטוריות אחרות לא יהיה לנו כזה ואז נוסחת נסיגה שכזו תעזור גם להבין מה בדיוק הערך שאנחנו מחפשים).

נעבור כעת להוכחה השניה, של אלון וספנסר. הם לוקחים גרף כלשהו \(G\) בעל \(n\) צמתים שמסומנים לצורך נוחות ב-\(v_{1},\dots,v_{n}\), מסמנים ב-\(d_{i}\) את הדרגה של הצומת \(v_{i}\), כלומר מספר הקשתות שמחוברות אליו. כעת, אם נסמן ב-\(\omega\left(G\right)\) את גודל הקליק הגדול ביותר ב-\(G\), אלון וספנסר טוענים שמתקיים:

\(\omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}}\)

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

אז איך הטענה מסיימת את ההוכחה? כאן שולפים כלי מתמטי סטנדרטי מהשרוול – אי שוויון קושי-שוורץ. לאי השוויון הזה מספר ניסוחים ואבחר את הניסוח הפשוט יחסית שרלוונטי עבורנו: אם \(a_{1},\dots,a_{n}\) ו-\(b_{1},\dots,b_{n}\) הן סדרות מספרים אז:

\(\left(\sum_{i=1}^{n}a_{i}b_{i}\right)^{2}\le\left(\sum_{i=1}^{n}a_{i}^{2}\right)\left(\sum_{i=1}^{n}b_{i}^{2}\right)\)

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

השימוש כאן בקושי-שוורץ הוא פשוט יחסית. נבחר \(a_{i}=\sqrt{n-d_{i}}\) ו-\(b_{i}=\left(\sqrt{n-d_{i}}\right)^{-1}\), נציב בנוסחה ונקבל:

\(n^{2}\le\left(\sum_{i=1}^{n}\left(n-d_{i}\right)\right)\left(\sum_{i=1}^{n}\frac{1}{n-d_{i}}\right)\le\omega\left(G\right)\sum_{i=1}^{n}\left(n-d_{i}\right)\)

עכשיו יש לנו עוד שני תעלולים לשלוף מהשרוול: ראשית, אנחנו מניחים ש-\(\omega\left(G\right)\le t\) – זו ההנחה הבסיסית שלנו, לפיה הגרף לא מכיל את הקליק \(K_{t+1}\). שנית, יש לנו דרך לקשר בין הדרגות של כל הצמתים בגרף ובין מספר הקשתות בו. אם מספר הקשתות הוא \(e\), אז בכל גרף (סופי) שהוא מתקיים השוויון \(2e=\sum_{i=1}^{n}d_{i}\), שכן כל קשת בגרף תורמת 1 לדרגות של שני הצמתים שהיא מחוברת אליהם. מכל אלה אפשר להסיק כעת:

\(n^{2}\le t\cdot\left(n^{2}-2e\right)\)

וכל שנשאר הוא ללהטט קצת כדי לחלץ את \(e\). פתיחת סוגריים, העברת אגפים, ונקבל:

\(2et\le n^{2}\left(t-1\right)\)

חלוקה ונקבל:

\(e\le\left(1-\frac{1}{t}\right)\frac{n^{2}}{2}\)

בדיוק מה שרצינו.

בינתיים זה היה טכני ולא הכי מעניין, אני חייב להודות; לב ההוכחה הוא בטענה \(\omega\left(G\right)\ge\sum_{i=1}^{n}\frac{1}{n-d_{i}}\) וההוכחה ההסתברותית שלה שאציג כעת.

במבט ראשון לא ברור איך הסתברות יכולה להשתחל לכאן. הגרף \(G\) נתון וקבוע; מה בדיוק נגריל ואיך? הרעיון של אלון וספנסר הוא להגריל סדר על הצמתים – פורמלית, פרמוטציה \(\pi\) כלשהי שלהם, כשכל פרמוטציה נבחרת בהסתברות שווה, \(\frac{1}{n!}\). נניח שהצמתים \(v_{1},\dots,v_{n}\) כבר מסודרים על פי הפרמוטציה הזו, ונגדיר קבוצת צמתים \(C_{\pi}\) שמכילה את כל הצמתים \(v_{i}\) שמחוברים בקשת לכל הצמתים שבאים לפניהם בפרמוטציה, כלומר לכל \(v_{j}\) כך ש-\(j<i\).

הנקודה המהותית כאן היא ש-\(C_{\pi}\) היא קליק. למה? ובכן, קחו ב-\(C_{\pi}\) את הצומת עם האינדקס המקסימלי; על פי הגדרה, הוא מחובר לכל הצמתים עם אינדקס קטן יותר ובפרט לכל צמתי \(C_{\pi}\). כעת קחו את הצומת המקסימלי הבא בתור… הבנתם את הרעיון.

יפה, אז הצלחנו להגדיר איכשהו מרחב הסתברות שמערב קליקים. אנחנו מעוניינים בחסם כלשהו על גדלי הקליקים, אז נגדיר משתנה מקרי \(X=\left|C_{\pi}\right|\) – גודל \(C_{\pi}\). בגלל האופן שבה \(C_{\pi}\) נבנתה, קל לפרק את \(X\) לסכום של אינדיקטורים (משתנים מקריים שמקבלים 0 או 1 בלבד): \(X=\sum_{i=1}^{n}X_{i}\) כאשר \(X_{i}\) מקבל 1 אם \(v_{i}\) מחובר בקשת לכל הצמתים שקדמו לו.

כעת השאלה הפשוטה היא – מה ההסתברות ש-\(X_{i}=1\)? מכיוון שכל הקשתות כבר נקבעו, זה תלוי בדרגה של \(v_{i}\): אם \(v_{i}\) מחובר ל-\(d_{i}\) צמתים, ההסתברות לכך שכל הצמתים שיהיו לפני \(v_{i}\) בפרמוטציה יהיו מתוך \(d_{i}\) הצמתים שהוא מחובר אליהם היא בעצם ההסתברות שמבין כל \(n-d_{i}\) הצמתים שאינם מחוברים אל \(v_{i}\), כולל \(v_{i}\) עצמו, יהיה זה \(v_{i}\) שמופיע ראשון. מכיוון שיש סימטריה בין כל \(n-d_{i}\) הצמתים הללו, ההסתברות לכך היא \(\frac{1}{n-d_{i}}\) (אתם מוזמנים לעשות חישוב פורמלי אם לא שוכנעתם).

זה מסיים את העניין אם זוכרים מה קורה בדרך כלל בשלב הזה בשיטה ההסתברותית. תוחלת של אינדיקטור היא ההסתברות שהוא יקבל 1, כלומר \(\mbox{E}\left[X_{i}\right]=\frac{1}{n-d_{i}}\). לינאריות התוחלת נותנת לנו כעת

\(\mbox{E}\left[X\right]=\mbox{E}\left[\sum_{i=1}^{n}X_{i}\right]=\sum_{i=1}^{n}\mbox{E}\left[X_{i}\right]=\sum_{i=1}^{n}\frac{1}{n-d_{i}}\)

ואנחנו מסיימים כי במרחב ההסתברות שלנו חייב להיות איבר שנותן ל-\(X\) לפחות את ערך התוחלת שלו, כלומר קליק שגודלו לפחות \(\sum_{i=1}^{n}\frac{1}{n-d_{i}}\).

שלא יהיה לכם ספק; אני לא מקבל שום אינטואיציה ל"מה הולך פה" מההוכחה הזו. היא פשוט מגניבה.

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

גרף \(k\)-צדדי כלשהו מאופיין בדרך כלל על ידי ההגדרה ה"גלובלית" שלפיה "יש חלוקה של צמתי הגרף ל-\(k\) קבוצות, כך ש…". אך למעשה, קיימת גם הגדרה "לוקלית" פשוטה במקרה שבו הגרף מכיל את כל הקשתות האפשריות: גרף הוא \(k\)-צדדי מלא, עבור \(k\) כלשהו, אם לכל זוג צמתים \(u,v\) שמחובר בקשת, וצומת נוסף \(w\), \(w\) חייב להיות מחובר ל-\(u\) או ל-\(v\).

הטענה בבירור מתקיימת בגרף \(k\) צדדי מלא – אם \(u,v\) מחוברים בקשת זה אומר שהם לא באותו צד, ולכן לא ייתכן ש-\(w\) יהיה גם בצד של \(u\) וגם בצד של \(v\) בו זמנית, ולכן הוא יהיה מחובר לאחד מהם (הרי הגרף מכיל כל קשת חוקית).

למה אם הטענה נכונה הגרף הוא \(k\) צדדי מלא? ובכן, למי שמכיר את המושג: כי היחס "\(u,v\) לא מחוברים בקשת" הוא יחס שקילות; ולמי שלא מכיר, אפשר לבנות את הצדדים כך – ניקח צומת תמים \(u\), ונגדיר את "הצד של \(u\)" בתור אוסף כל הצמתים ש-\(u\) לא מחובר אליהם. לא ייתכן שבקבוצה הזו יהיו שני צמתים \(v,w\) שמחוברים בקשת (כי אז העובדה ש-\(u\) לא מחובר לאף אחד מהם סותרת את הטענה שלנו), לכן זה אכן צד חוקי של גרף \(k\) צדדי. בנוסף, אם ניקח צומת \(v\) כלשהו בצד הזה, הוא יהיה חייב להיות מחובר לכל צומת שאינה באותו צד איתו; כי אם יש צומת \(w\) שאינה באותו צד איתו אז על פי הגדרת הצד, \(w\) מחובר ל-\(u\), ולא ייתכן ש-\(v\) לא יהיה מחובר לא ל-\(u\) ולא ל-\(w\).

יפה, אז יש לנו אפיון לוקלי פשוט, וכל שצריך להראות הוא שהאפיון מתקיים בגרף האקסטרמלי. נניח בשלילה שהוא לא, אז יש לנו שלושה צמתים בגרף: \(u,v,w\), כך ש-\(u,v\) מחוברים בקשת ואילו \(w\) לא מחובר לאף אחד מהם. הרעיון הוא לבנות עכשיו מהגרף הקיים גרף חדש שבו יש יותר קשתות ואותו מספר צמתים ועדיין אין בו את \(K_{t+1}\), בסתירה לאקסטרימליות של הגרף שלנו.

איך עושים את זה? פשוט: מעיפים מהגרף את אחד מהצמתים \(u,v,w\) שיש לו מעט קשתות ושמים במקומו עותק של אחד מהצמתים האחרים. אם למשל מתקיים ש-\(d\left(u\right)>d\left(w\right)\), אז נעיף מהגרף את \(w\); בכך איבדנו \(d\left(w\right)\) קשתות. כפיצוי, נוסף לגרף צומת \(u^{\prime}\) שמחובר בדיוק לאותם צמתים ש-\(u\) מחובר אליהם; זה ייתן לנו עוד \(d\left(u\right)\) קשתות, כלומר הרווחנו. לא קשה לראות שהוספת \(u^{\prime}\) לגרף לא יכולה ליצור קליק מגודל \(t+1\): אם יש קליק כזה, אז היה קליק כזה גם בגרף המקורי, רק עם \(u\) במקום \(u^{\prime}\) (לא ייתכן שיש קליק שמערב הן את \(u\) והן את \(u^{\prime}\) יחד, שכן אין קשת ביניהם).

באופן דומה מטפלים במקרה שבו \(d\left(v\right)>d\left(w\right)\). המקרה היחיד שנותר לנו הוא זה שבו \(d\left(w\right)\ge d\left(u\right),d\left(v\right)\). כאן נעיף מהגרף את \(u,v\) שניהם גם יחד ונשים שני עותקים של \(w\); הסיבה שבגללה נרוויח כך קשת היא שכשמסירים את \(u,v\) לא מאבדים \(d\left(u\right)+d\left(v\right)\) קשתות אלא רק \(d\left(u\right)+d\left(v\right)-1\) קשתות, שכן הקשת המשותפת של \(u,v\) מוסרת רק פעם אחת. זה מסיים את ההוכחה הזו.

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

כלל ה-0-1 של גרפים – ההוכחה

פורסם בתאריך על ידי
10

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה \(T\), שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות \(\mathcal{P}\) עם הסתברות 1. למשל, הפסוק \(\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)\) שמתאר את "בגרף קיים משולש" שראינו בפוסט הקודם נמצא בתורה זו. את ההוכחה כעת ניתן לסכם, למי שבקיא במושגים, בתור "התורה הזו עקבית ושלמה, ולכן כל תכונה שניתן לנסח בשפה או נובעת ממנה ואז הסתברותה 1, או ששלילתה נובעת ממנה ואז הסתברותה 0". כעת ניגש לפרטים ובראש ובראשונה למה שאני מתכוון אליו ב"תורה שלמה".

לפני מספר פוסטים דיברתי על שני מושגים שונים – "שלמות סמנטית" ו"שלמות סינטקטית". המושג של "שלמות סמנטית" התייחס לשלמות של מערכת ההוכחה שלנו, שבאופן אינטואיטיבי ניתן לנסח כ"כל מה שנכון – ניתן להוכחה". זו לא השלמות שאני מדבר עליה כאן – בפרט, מדובר בשלמות של מערכת הוכחה וכאן אני מדבר על שלמות של תורה. אם כן, אני מתכוון למה שכיניתי אז "שלמות סינטקטית"; תורה \(T\) היא שלמה סינטקטית אם כל פסוק \(\varphi\) ניתן להוכחה ממנה, או ששלילתו \(\neg\varphi\) ניתנת להוכחה ממנה. גם כאן אני משתמש במושג ה"הוכחה" אך אין לי בו צורך של ממש; מכיוון שמערכת ההוכחה שלנו היא שלמה (סמנטית) ונאותה אז "אפשר להוכיח את \(\varphi\) מ-\(T\)" שקול ל"\(T\) גוררת לוגית את \(\varphi\)" שהגדרתי בפוסט הקודם ופירושו היה "כל מודל של \(T\) הוא גם מודל של \(\varphi\)" (סימנתי זאת \(T\vdash\varphi\) – וכזכור, זה לא הסימן המקובל ואני משתמש בו כי את הסימן הנכון יותר אני לא מצליח להציג כאן).

אם כן, סיכום: אם \(T\) היא עקבית ושלמה, אז אפשר להראות כי נובע מכך שכל פסוק \(\varphi\) שייך לה, או ש-\(\neg\varphi\) שייך לה. זה מסיים את העניין מייד, כי אז לכל תכונה של גרף – שכזכור, מוגדרת באמצעות פסוק \(\varphi\) – או ש-\(\varphi\in T\) ואז הסתברות התכונה היא 1, או ש-\(\neg\varphi\in T\) ואז ההסתברות שהתכונה לא מתקיימת היא 1, כלומר הסתברות התכונה היא 0. שימו לב לקשר היפה שיש כאן בין לוגיקה וקומבינטוריקה – כדי להוכיח את טענת ה-0-1 הקומבינטורית, הכל מצטצמם בסופו של דבר להוכחה שתורה מסויימת היא שלמה. זו גם דוגמה נאה לתורה "מעניינת" שאינה נופלת קורבן למשפט אי השלמות של גדל; הסיבה לכך שהיא חומקת ממנו היא שלא מדובר בתורה אריתמטית, כלומר היא אינה ממדלת את המספרים הטבעיים עם פעולת החיבור והכפל. זו כמובן לא התורה המעניינת היחידה שעושה זאת, אך עוד דוגמה לאוסף כדי להשתיק את מי שאומר "משפט גדל מראה שכל תורה מתמטית איננה שלמה" היא תמיד דבר טוב.

ראשית אני רוצה לטפל בשאלה מדוע אם \(T\) עקבית ושלמה נובע מכך שכל פסוק נמצא בה או ששלילתו נמצאת בה. לשם כך מספיק להראות שהתורה היא "סגורה" במובן זה שאם \(T\vdash\varphi\), אז \(\varphi\in T\). הנה נימוק פשוט לכך: אם \(T\vdash\varphi\) נובע מכך שקיימת קבוצה סופית של פסוקים \(\psi_{1},\dots,\psi_{n}\in T\) כך ש-\(\left\{ \psi_{1},\dots,\psi_{n}\right\} \vdash\varphi\) (למה? ההוכחה שאני חושב עליה היא "אם \(T\vdash\varphi\) אז קיימת הוכחה ל-\(\varphi\) עם אקסיומות מ-\(T\). מכיוון שזו הוכחה סופית, יש בה רק מספר סופי של אקסיומות \(\psi_{1},\dots,\psi_{n}\), ומכיוון שהן מוכיחות את \(\varphi\) הן גם גוררות אותו לוגית" – אבל אני בטוח שיש עוד הוכחות). כלומר, כל מודל של הפסוק \(\psi_{1}\wedge\dots\wedge\psi_{n}\) הוא גם מודל של \(\varphi\), ולכן ההסתברות ש-\(\varphi\) יתקיים גדולה לפחות כמו ההסתברות ש-\(\psi_{1}\wedge\dots\wedge\psi_{n}\) יתקיים (כי כל גרף שנגריל ויקיים את התכונה \(\psi_{1}\wedge\dots\wedge\psi_{n}\) יקיים גם את התכונה \(\varphi\)). לא קשה להראות שההסתברות ש-\(\psi_{1}\wedge\dots\wedge\psi_{n}\) יתקיים היא 1, כי ההסתברות של כל \(\psi_{i}\) היא 1 (נסו להוכיח זאת – זה תרגיל קצר ונחמד).

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

ובכן, מה שמראה ש-\(T\) שלמה הוא מבחן Los-Vaught. לצורך כך, הגדרה: תורה נקראת \(\kappa\)-קטגורית אם כל שני מודלים שלה שהן מעוצמה \(\kappa\) הם איזומורפיים. מי שאינו מכיר עוצמות ("גודל אינסופי") או מבין את הכוונה המדוייקת ב"איזומורפיים" ("הם אותו דבר פרט אולי לשינוי הסימונים") – לא נורא. מה שהמבחן אומר הוא שאם תורה היא \(\kappa\)-קטגורית, לא משנה עבור איזה \(\kappa\), ואין לה מודלים סופיים – אז היא שלמה. ההוכחה לטענה הזו מתבססת על משפט לוונהיים-סקולם, שכבר הזכרתי פעם, שמראה שאם לתורה (מסדר ראשון, כאן זה חשוב) יש מודל אינסופי, אז יש לה מודל אינסופי מכל עוצמה אינסופית (כלומר, שפות מסדר ראשון לא מסוגלות "להבדיל" בין עוצמות שונות של מודלים אינסופיים).

כעתת נניח כי \(T\) אינה שלמה. אז יש פסוק \(\varphi\) שאינו נובע ממנה, וגם \(\neg\varphi\) אינו נובע ממנה. אז אפשר לבנות שתי תורות חדשות, \(T_{1}=T\cup\left\{ \varphi\right\} \) ו-\(T_{2}=T\cup\left\{ \neg\varphi\right\} \) שיהיו שתיהן עקביות (אם אחת מהן לא הייתה עקבית, פירוש הדבר היה ש-\(\varphi\) או \(\neg\varphi\) נובע מ-\(T\)). לכן יש לשתיהן מודל אינסופי (כי אין ל-\(T\) מודלים סופיים, וכל מודל של \(T_{1}\)ושל \(T_{2}\) הוא גם מודל של \(T\)) ועל פי לוונהיים סקולם, לשתיהן יש מודל מעוצמה \(\kappa\); אבל אמרנו ש-\(T\) היא \(\kappa\)-קטגורית, ולכן שני המודלים הללו (שהם, כאמור, מודלים גם של \(T\)) הם איזומורפיים. זה בלתי אפשרי שכן הם שונים מהותית – באחד \(\varphi\) מתקיים, ובשני \(\neg\varphi\) מתקיים. סתירה.

אם כן, סיימנו את המבוא הלוגי הכללי, ואפשר סוף סוף לגשת ל"בשר" של ההוכחה – האופן שבו מראים שיש ל-\(T\) מודל בן מניה יחיד, ואין לה מודלים סופיים. בתור התחלה כדאי לעצור ולחשוב לרגע – מה זה בכלל אומר, "מודל ל-\(T\)"? הרי \(T\) מלכתחילה היא אוסף של פסוקים, שכל אחד בנפרד אמור להגדיר לנו גרפים; אם \(\varphi\in T\) אז המודלים של \(\varphi\) שהיו לנו בראש מלכתחילה היו של גרפים – וגרפים סופיים. אם כך, איך פתאום נכנסים מודלים אינסופיים לתמונה?

ובכן, די בבירור ל-\(T\) פשוט לא יכול להיות מודל סופי. זאת מכיוון שהתכונה "בגרף יש לפחות \(n\) צמתים" ניתנת לתיאור בלוגיקה מסדר ראשון, ובוודאי שיש לה הסתברות 1 (כזכור, ההסתברות נלקחת על גרף "אקראי" כשמספר הצמתים שואף לאינסוף). הפסוק \(\varphi_{n}\) המתאים הוא פשוט \(\exists v_{1},\dots,v_{n}\left(\bigwedge_{i\ne j}v_{i}\ne v_{j}\right)\). אם ל-\(T\) היה מודל סופי, עם נניח \(n\) איברים, הוא לא היה יכול לספק את \(\varphi_{n+1}\in T\) – סתירה. אז ל-\(T\) אין מודל סופי. לכן היצורים היחידים שכן מספקים את כל הפסוקים שב-\(\varphi\) בו זמנית הם גרפים אינסופיים. אין קושי רעיוני במושג כזה – אנחנו פשוט לא מגבילים את קבוצת הצמתים להיות סופית, וגרפים אינסופיים הם יצורים מאוד נפוצים במתמטיקה. עם זאת, המעורבות שלהם כאן היא עדיין מעניינת – אנחנו מראים שקיים גרף בן מניה יחיד שמקיים בו זמנית את כל התכונות שמתקיימות "כמעט בכל הגרפים הסופיים", וזה מראה לנו את נכונות כלל ה-0-1.

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

איך מוכיחים ששני מודלים הם איזומורפיים? לצורך הפשטות מספיק לדבר על שני גרפים אינסופיים (בני מניה) \(A,B\) ולא להיכנס לתורה הכללית. מה שצריך להראות הוא פשוט התאמה של אחד-לאחד בין הצמתים של \(A\) והצמתים של \(B\) שמשמרים את הקשתות. כלומר, אם \(V_{A}=\left\{ a_{1},a_{2},a_{3},\dots\right\} \) הם צמתי \(A\) ואילו \(V_{B}=\left\{ b_{1},b_{2},b_{3},\dots\right\} \) הם צמתי \(B\) אנחנו רוצים למצוא פונקציה \(f:V_{A}\to V_{B}\) שהיא חד חד ערכית ועל, ומקיימת ש-\(\left(a_{i},a_{j}\right)\in E_{A}\) אם ורק אם \(\left(f\left(a_{i}\right),f\left(a_{j}\right)\right)\in E_{B}\).

מה שנעשה הוא לשחק משחק באופן הבא. ראשית, נתאים את \(a_{1}\) ל-\(b_{1}\), פשוט כי לעת עתה אין שום מהלך נבון יותר שניתן לעשות. כעת, למי נתאים את \(a_{2}\)? זה כבר נהיה מורכב מעט יותר – אם \(a_{1}\) מחובר ל-\(a_{2}\), נרצה לבחור \(b_{i}\in V_{B}\) שמחובר ל-\(b_{1}\). מה מבטיח לנו שקיים כזה? ובכן, אם לא היה קיים כזה, אז \(B\) לא היה מודל טוב עבור התכונה "לכל צומת יש לפחות שכן אחד", שלא קשה לראות שניתן לנסח בשפה מסדר ראשון ושיש לו הסתברות 1 (בגרף עם \(n+1\) צמתים, לכל צומת יש \(n\) שכנים פוטנציאליים, ולכן ההסתברות שלא יהיה לו אף שכן היא \(\frac{1}{2^{n}}\) – שואפת לאפס).

בואו נעבור לדבר על משהו כללי יותר. נניח שעד כה טיפלתי בכל הצמתים \(a_{1},a_{2},\dots,a_{n}\) ועכשיו אני תוהה לאן להעביר את \(a_{n+1}\). בואו נניח לצורך נוחות ש-\(a_{1}\) עבר ל-\(b_{1}\), ש-\(a_{2}\) עבר ל-\(b_{2}\) וכן הלאה (אם לא, פשוט נשנה את המספור של הצמתים של \(B\)). עכשיו, הצומת החדש \(a_{n+1}\) הולך להיות מחובר לחלק מהצמתים הקיימים, ולחלק מהם – לא. נסמן ב-\(S_{A}\) את קבוצת הצמתים שאליהם \(a_{n+1}\) מחובר, וב-\(S_{B}\) את קבוצת ה"תמונות" שלהם (ה-\(b_{i}\)-ים שמחוברים לאיברים של \(S_{A}\)). מה שאנחנו רוצים לעשות הוא למצוא צומת כלשהו ב-\(V_{B}\) שמחובר לכל הצמתים ב-\(S_{B}\), ולא מחובר לאף צומת מבין \(b_{1},\dots,b_{n}\) שאיננו ב-\(S_{B}\). האם קיים צומת שכזה? אנחנו חייבים שהתשובה תהיה חיובית כדי שהשיטה תצליח; וזה מוביל אותנו לניסוח התכונות שב-\(T\) שיעניינו אותנו, שהן בדיוק התכונות שאומרות "כן! בכל תרחיש דוגמת זה שתיארת למעלה, אפשר למצוא צומת \(b_{n+1}\) מתאים". מה שצריך להראות הוא שהתכונות הללו ניתנות לניסוח בשפה מסדר ראשון שלנו, ושההסתברות לכך שהן יתקיימו בגרף היא 1. ברגע שהראנו זאת, סיימנו; כי אז התהליך שתיארתי לעיל, אחרי שמכלילים אותו עוד טיפה, מגדיר באופן מושלם את האיזומורפיזם (אם רוצים לדעת לאן \(a_{n}\) עבר, "מריצים" את התהליך במשך \(n\) צעדים ורואים מה קורה; כדי להבטיח שגם כל ה-\(b_n\)-ים יותאמו לאחד מה-\(a_n\)-ים צריך לבחור גם עבורם איברים, לסירוגין).

הבה ננסח במפורש את התכונות שאנחנו רוצים. נסמן ב-\(\mbox{EA}_{n,m}\) את התכונה "לכל קבוצה \(X\) מגודל \(n\) ותת קבוצה \(Y\) מגודל \(m\) שלה, קיים איבר שאינו ב-\(X\) שמחובר לכל אברי \(Y\) ואינו מחובר לאף איבר ב-\(X\) שאינו ב-\(Y\)" (למה \(\mbox{EA}\)? מלשון Extension Axiom, שכן זוהי אקסיומה שאומרת שניתן "להרחיב" את הקבוצה \(X\) באופן שמעניין אותנו – דהיינו, חיבור בדיוק לצמתי \(Y\)). את התכונה הזו אפשר לכתוב בקלות יחסית בשפה מסדר ראשון:

\(\forall v_{1},\dots,v_{n}\)
\(\left[\left(\bigwedge_{i\ne j}v_{i}\ne v_{j}\right)\to\exists u\left(\bigwedge_{i}^{n}u\ne v_{i}\wedge\bigwedge_{i\le m}E\left(u,v_{i}\right)\wedge\bigwedge_{i>m}^{n}\neg E\left(u,v_{i}\right)\right)\right]\)

אז נשאר רק להראות שכל תכונה כזו מתקיימת בהסתברות 1 בכל גרף. האינטואיציה ברורה – \(n,m\) הם קבועים, ואנחנו שואלים את עצמנו מה קורה בגרפים אקראיים שגודלם שואף לאינסוף. אם נקבע את \(X,Y\), בגרפים כאלו יש כמעט "אינסוף" צמתים \(u\) פוטנציאליים להתאים ל-\(X,Y\), ולכן צומת שכזה אכן יופיע. כך זה בתורת הגרפים (ובמקומות רבים אחרים…) – ברגע שהמבנה שלך גדול מספיק, כל מה שתוכל להעלות על דעתך יווצר בתוכו, כל עוד מה שמעניין אותך הוא תכונה מקומית.

כדי להקל על החישוב נפשט קצת עניינים. אין צורך לדבר על \(\mbox{EA}_{n,m}\) עבור \(n,m\) כלליים – שימו לב שאם \(\mbox{EA}_{2m,m}\) מתקיים בהסתברות 1, אז בוודאי גם \(\mbox{EA}_{n,m}\) מתקיים בהסתברות 1 עבור \(m\le n\le2m\), כי אנחנו מקלים קצת על הדרישות – הקבוצה \(Y\) נותרת זהה, ואנחנו פשוט דורשים פחות דרישות על שאר האיברים ב-\(X\) (כלומר, מעיפים לכל הרוחות את חלקם). לכן די להוכיח כי \(\mbox{EA}_{2m,m}\) מתקיים בהסתברות 1. נקבע את מספר הצמתים בגרף כולו להיות \(n\) (כי השתמשנו ב-\(n\) עד כה למטרה זו וחבל להפסיק – רק צריך לזכור שזה לא אותו \(n\) שהופיע ב-\(\mbox{EA}_{n,m}\)).

מכאן זו באמת קומבינטוריקה פשוטה וקצת אינפי. ניקח צומת שאיננו ב-\(X\). מה ההסתברות שהוא מחובר לכל \(m\) צמתי \(Y\), ואינו מחובר לכל הצמתים של \(X\) שאינם ב-\(Y\)? בדיוק \(\frac{1}{2^{2m}}\), כי יש \(2m\) הגרלות של קשתות שבכל אחת אנחנו צריכים שתתקבל תוצאה ספציפית. אם כן, ההסתברות שצומת כלשהו לא יקיים את התכונה הרצויה היא \(1-\frac{1}{2^{2m}}\). על פניו הסתברות גדולה – אבל כאמור, יש המון צמתים שונים. כמה המון? \(n-2m\) צמתים שבגרף אך אינם ב-\(X\). ההסתברות שאף אחד מהם לא יהיה בסדר היא מכפלת ההסתברויות של כל אחד להיות לא בסדר, כלומר \(\left(1-\frac{1}{2^{2m}}\right)^{n}\). זה בפני עצמו שואף לאפס כשמשאיפים את \(n\) לאינסוף, אבל צריך לשים לב שלא סיימנו – אנחנו לא טוענים טענה על קבוצה \(X\) ספיצפית, אלא על כל קבוצה \(X\) מגודל \(2m\) וכל תת קבוצה \(Y\) שלה מגודל \(m\). אז ההסתברות שמשהו ישתבש הוא שתהיה קבוצה \(X\) כלשהי ותת קבוצה \(Y\) שלה שעבורן האירוע ה"רע" שהסתברותו \(\left(1-\frac{1}{2^{2m}}\right)^{n}\) מתרחש. ההסתברות לכל זה חסומה על ידי מספר תת הקבוצות הללו כפול \(\left(1-\frac{1}{2^{2m}}\right)^{n}\) (בהינתן קבוצת מאורעות, ההסתברות שאחד מהם יתרחש חסומה על ידי סכום ההסתברויות שלהם – זה מה שנקרא Union bound).

אז הסתברות הכישלון שלנו חסומה על ידי \({n \choose 2m}{2m \choose m}\left(1-\frac{1}{2^{2m}}\right)^{n}\). את כל זה אפשר לחסום על ידי \(n^{2m}\cdot c^{n}\) כש-\(c\) הוא קבוע קטן מ-1. המסקנה ברורה – פולינום כמו \(n^{2m}\) גדל הרבה יותר לאט מאשר פונקציה אקספוננציאלית כמו \(c^{n}\) גדלה, ומכיוון ש-\(c<1\), \(c^{n}\) שואף לאפס, ולכן \(n^{2m}\cdot c^{n}\) כולו שואף לאפס כש-\(n\) שואף לאינסוף, כלומר ההסתברות ש"משהו יתקלקל" שואפת לאפס, ולכן ההסתברות שהתכונה תתקיים שואפת ל-1. זהו.

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

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

פורסם בתאריך על ידי
8

הצגתי לא מזמן תוצאה מקסימה שקישרה בין קומבינטוריקה ותורת האוטומטים (איך ניתן למצוא, בעזרת תיאור של אוטומט עבור שפה מסויימת, את הפונקציה היוצרת של השפה). זוהי דוגמה אחת לאופן שבו הלוגיקה המתמטית, על שלל ענפיה (אפשר לראות את תורת האוטומטים כענף של הלוגיקה המתמטית) מסייעת לקומבינטוריקה. הפעם אני רוצה לתת דוגמה נוספת, מקסימה במיוחד לטעמי.ראשית נציג את זירת המשחק הקומבינטורית – גרפים. תזכורת קצרה: גרף \(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 אומר אומר שהתכונות היחידות של גרפים שניתן לתאר באמצעות לוגיקה מסדר ראשון הן טריוויאליות במובן זה שהן מתקיימות "כמעט לכל הגרפים" או שאינן מתקיימות "כמעט עבור אף גרף".

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