גרף מרחיב

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

גרף רגולרי X=(V,E) בעל n קדקדים ודרגה k נקרא c-מרחיב אם לכל קבוצה A של קדקודים בגודל עד n/2 מתקיים שגודל ה-ברדה החיצונית שלהם (מוסמנת \partial A), כלומר הקודקודים מחוץ ל-A המחוברים ל-A, גדול לפחות ב-c פעמים מגודל A. במילים אחרות, כל קבוצה קטנה יוצרת הרבה קישורים החוצה.

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

מבחינה הסתברותית, מרבית הגרפים רגולריים הם מרחיבים. אם k>5 ומגרילים גרף k-רגולרי על n קדקדים, אז כש-n גדל ל-
אינסוף, ההסתברות שהגרף הוא חצי-מרחיב שואפת ל-1. כלומר קיימות משפחות של גרפים מרחיבים בכל סדר גדול דיו.
בניה מפורשת של משפחות כאלה קשה יותר. הבניה הראשונה ניתנה על ידי גריגורי מרגוליס ב-1975, באמצעות גרפי קיילי של חבורות מטריצות מעל שדות סופיים, וההוכחה השתמשה בתורת ההצגות של חבורות לי. בשנת 1988 בנו אלכס לובוצקי ופיטר סרנק דוגמות של גרפי רמנוג'אן שהם אקספנדרים אופטימליים. הבניות מודרניות משתמשות בקומבינטוריקה אריתמטית ובעבודות של הלפגוט, בורגיין-גמבורד-סרנק, בורגיין-ואריו וגרין-טאו-ברוליארד.

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

קבוע צ'יגר (Cheeger) מודד האם בגרף יש "צוואר בקבוק", קבוצה שממנה יוצאות מעט קשתות יחסית לגודלה. עבור גרף d-רגולרי יש יחס מספרי בין הפער הספקטרלי (d-λ_2) ובין קבוע צ'יגר. טנר הוכיח גבול תחתון, ונוגה אלון ווִיטלי מילמן הוכיחו גבול עליון, שמקשרים בין שני המדדים האלו.

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

בגרף רגולרי כל קדקוד מחובר לאותו מספר של קשתות. גרף כזה נקרא c-מרחיב אם כל קבוצה קטנה של קדקודים מחוברת החוצה להרבה קדקודים אחרים.

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

בגרפים אקראיים רגולריים רבים יוצא שהם מרחיבים. כלומר ברוב המקרים זה קורה. אבל לבנות משפחות של גרפים כאלה בצורה מפורשת קשה. מרגוליס הבין איך לבנות כאלה ב-1975. אחר כך לובוצקי וסרנק בנו גרפים טובים במיוחד בשם "רמנוג'אן".

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

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