גרף ראדו — הגרף המקרי

גרף (אינסופי בן מנייה) $G=(V,E)$ נקרא אדיר אם לכל שתי תתי קבוצות סופיות $F_1,F_2\subset V$ יש קודקוד $v\in V$ כך ש-$v$ מחובר בצלע לכל קודקוד ב- $F_1$ ולא מחובר בצלע לאף קודקוד ב-$F_2$.

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

• אם $\Gamma$ הוא גרף אדיר ו-$G$ הוא גרף בן מנייה כלשהו, אז יש תת-גרף מושרה $H\subseteq \Gamma$ כך ש- $H$ איזומורפי ל-$G$.
• אם $\Gamma$ הוא גרף אדיר ו-$f:H_1\to H_2$ איזומורפיזם בין שני תתי-גרפים מושרים סופיים של $\Gamma$, אז יש אוטומורפיזם $\widehat{f}:\Gamma\to \Gamma$ של $\Gamma$ כך ש- $\widehat{f}\upharpoonright H_1 = f$.
• קיים גרף בן מנייה אדיר והוא יחיד עד כדי איזומורפיזם של גרפים. גרף זה נקרא ’’הגרף המקרי‘‘ הוא ’’גרף ראדו‘‘. בהמשך נראה מדוע הוא נקרא הגרף המקרי.

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