גרף מרחיב

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

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

הגדרה קומבינטורית

גרף רגולרי $X=(V,E)$ בעל $n$ קדקדים ודרגה $k$ נקרא $c$-מרחיב אם לכל קבוצה של קודקודים $A\subset V$ מתקיים $|\partial A|\geq c\left(1-{\frac {|A|}{n}}\right)|A|$. כאשר מסמנים ב-$\partial A$ את קבוצת הקודקודים שאינם ב-$A$ אבל מחוברים לקודקוד ששייך ל-$A$.

קל לראות שכל גרף קשיר הוא $c$-מרחיב עבור $c>0$ קטן מספיק. לכן מתייחס לפעמים השם "גרף מרחיב" למשפחה אינסופית של גרפים שכולם מרחיבים עם אותו קבוע $c$ (ואותו $k$), ולא לגרף בודד.

הגדרה ספקטרלית

בהינתן גרף רגולרי כאמור לעיל, מטריצת השכנות שלו היא מטריצה בגודל $n\times n$ כך שהתא במיקום $(i,j)$ מכיל את הערך 1 אם קודקוד $i$ מחובר לקודקוד $j$, ואת הערך 0 אחרת. הערך העצמי המקסימלי של מטריצת שכנות של גרף k-רגולרי הוא תמיד $k$ ואם הגרף דו צדדי, גם $(-k)$ הוא ערך עצמי. ערכים עצמיים אלה נקראים טריביאלים. אומרים שהגרף הוא $\alpha$-מרחיב (במובן הספקטרלי) אם לכל ערך עצמי לא טריביאלי מתקיים $|\lambda |<k-\alpha$.

הגדרה זו של גרפים מרחיבים שקולה להגדרה הקודמת, כלומר לכל k ולכל $\alpha >0$ יש $c>0$ כך שכל גרף שהוא $\alpha$-מרחיב לפי ההגדרה הספקטרלית, הוא גם $c$-מרחיב בהגדרה הקומבינטורית ולהפך.

קיום ובניה של גרפים מרחיבים

על ידי שיקולי ספירה קל להראות שיש גרפים מרחיבים. ליתר דיוק, אם $k>5$ ואם מגרילים גרף מקרי k-רגולרי על $n$ קדקדים, אז כאשר $n$ שואף לאינסוף, ההסתברות שהגרף הוא ${\tfrac {1}{2}}$-מרחיב שואפת ל-1. בפרט, יש גרפים מרחיבים מכל סדר גדול מספיק.

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

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

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

שימושים של גרפים מרחיבים

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

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

• בנית קודים לתיקון שגיאות.

• אלגוריתמי דה-רנדומיזציה רבים משתמשים בגרפים מרחיבים.

• בניות של פונקציות ערבול בקריפטוגרפיה.

• הוכחת משפט ה-PCP משתמשת בגרפים מרחיבים.

אי שוויון צ'יגר

קבוע צ'יגר (Cheeger) הוא מדד מספרי האם גרף מכיל "צוואר בקבוק". הקבוע מוגדר על ידי $h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},$ (מהי קבוצת הקודקודים בגודל של עד חצי ממספר הקודקודים, שעבורה מספר הקשתות שיצאו ממנה ביחס לגודל שלה יהיה מינימלי).

עבור גרף G שהוא d רגולרי קיים קשר בין הפער הספקטרלי ($d-\lambda _{2}$ ) לקבוע זה, שהוכח על ידי טנר, ובאופן בלתי תלוי על ידי נוגה אלון וויטלי מילמן:

${\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}$

קישורים חיצוניים

• שלמה חורי, נתן ליניאל ואבי ויגדרזון, גרפים מרחיבים ושימושיהם