גרף שרייר

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

הגרף נקרא על שמו של אוטו שרייר.

הגדרה

תהי $G$ חבורה הנוצרת על ידי יוצרים $g_{1},\dots ,g_{n}$. בהינתן תת-חבורה $H$, נגדיר את הגרף להיות הגרף הבא:

• הקודקודים שלו יהיו המחלקות הימניות של $H$.
• מהקודקוד $Hg$, עבור כל יוצר $g_{i}$ של $G$, יוצאת קשת המסומנת ב-$g_{i}$ אל הקודקוד $Hg\cdot g_{i}$.
• השורש של הגרף הוא המחלקה $H$.

תכונות

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

כל הילוך על הגרף, לאורך הקשתות $e_{1},\dots ,e_{n}$ מקביל להכפלה באיבר המתקבל מהכפלת הסימנים על הקשתות (כאשר הליכה בכיוון ההפוך היא הכפלה בהופכי).

כאשר לוקחים $H=\{e\}$ (החבורה הטריוויאלית) מתקבל גרף קיילי של החבורה $G$ ביחס ליוצרים הללו. יותר מכך, אם $H$ נורמלית אז הגרף הוא גרף קיילי של המנה $G/H$.

שימושים

כל הילוך על הגרף מהשורש לקודקוד אחר מתאים למילה בחבורה $G/H$. אם נקח עץ פורש של הגרף, נקבל דרך הצגה יחידה לכל איבר בעזרת היוצרים.

נניח ש-$G$ החבורה החופשית. אז אפשר לראות שלאחר הסרת עץ פורש, לכל סדרת קשתות קיים הילוך יחיד שהולך דרכן בסדר ובכיוונים המתאימים (וזאת כיוון שיש רק דרך אחת לעבור מאחת לשנייה בעזרת קשתות מהעץ הפורש). זוהי הוכחה למשפט נילסן-שרייר, כיוון ש-$H$ היא החבורה החופשית הנוצרת על ידי הקשתות שנותרו. יתרה מכך, מספרן הוא דרגת החבורה. מכאן אפשר לראות את דרגת החבורה $H$ ב-$G$ כאשר $[G:H]$ סופי: בגרף היו תחילה $rk(G)\cdot [G:H]$ קשתות (מספר הקודקודים כפול מספר הקשתות היוצאות מכל אחד) והורדנו $[G:H]$ מהן. מכאן שנשארנו עם $rk(G)\cdot [G:H]-([G:H]-1)$ קשתות, ולכן $rk(H)=rk(G)\cdot [G:H]-([G:H]-1)+1$.

גרף הליבה של Stallings

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

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

בעזרת גרף הליבה אפשר למצוא בסיס לתת החבורה ולפתור את בעיית המילה.

בנוסף, אם $H,K$ שתי תתי חבורות של $G$, אז יש מורפיזם מגרף הליבה של $H$ לזה של $K$ אם ורק אם $K$ היא תת-חבורה של $H$.