הגרף הלא כל-כך מקרי וחוקי 0-1 לגרפים

בשנת 1963 ארדש ורני הוכיחו את משפט שבמבט ראשון נראה בלתי סביר:

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

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

לבסוף, נראה איך להשתמש בלוגיקה של הגרף המקרי על מנת להוכיח את הטענה הבאה:

תהי $P$ תכונה מסדר ראשון של גרפים (אנו נסביר בדיוק למה הכוונה). נסמן $P(n)$ את ההסתברות שלגרף על $n$ קודקדים יש התכונה $P$. אזי הגבול, כאשר $n$ שואף לאינסוף, של $P(n)$ הוא $0$ או $1$.