גרף קיילי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
גרף קיילי של חבורת התמורות הזוגיות \ A_4, עם יוצרים מסדר 2 (אדום) ו-3 (כחול)

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

הגרף אינו מוגדר עבור חבורה G בפני עצמה, אלא רק ביחס לקבוצת יוצרים שלה, S. גרף קיילי של G ביחס ל-S הוא הגרף שקודקודיו הם אברי החבורה, ולכל יוצר \ s\in S יש בו קשת בצבע s מכל קודקוד \ g\in G למכפלה \ gs. באופן הזה מתקבל גרף מכוון רגולרי: מכל קודקוד יוצאות ונכנסות בדיוק |S| קשתות. באיור משמאל מוצג גרף קיילי של החבורה \ A_4 ביחס ליוצרים \ a=(12)(34), באדום, ו- \ b=(123), בכחול. מקובל להשמיט את הכיוונים עבור היוצרים מסדר 2, כפי שעשינו לעיל.

בחבורות קטנות הגרף מאפשר לבצע חישובים במהירות. בגרף שלנו אפשר לחשב כי \ (ab)^3=e, משום שאם יוצאים מאיבר היחידה וצועדים בכיוון אדום-כחול-אדום-כחול-אדום-כחול, חוזרים לנקודת ההתחלה. אותה תוצאה נקבל מכל נקודת התחלה, דבר המדגים את מידת הסימטריה של הגרף. אכן, חבורת הסימטריות של גרף קיילי צבוע היא בדיוק החבורה שאותה הוא מתאר. על הגרף אפשר להגדיר את מטריקת המלה, שלפיה המרחק מקודקוד g לקודקוד h שווה למספר הקטן ביותר של יוצרים (והאיברים ההפוכים להם) הדרוש לכתיבת היחס \ g^{-1}h.

גרף קיילי כמרחב גאודזי[עריכת קוד מקור | עריכה]

אפשר להפוך את הגרף למרחב גאודזי, אם מתאימים כל קשת \ g \mapsto gs לקטע היחידה \ [0,1] (עם המטריקה הרגילה עליו). באופן הזה, כל גרפי קיילי של חבורה נוצרת סופית G (ביחס לכל קבוצת יוצרים סופית) הם קוואזי-איזומטריים זה לזה, וכך מתקבל העקרון היסודי של תורת החבורות הגאומטרית: גרף קיילי הוא אינווריאנט קוואזי-איזומטרי של החבורה. לפי הלמה של שוורץ-מילנור, כל מרחב גאודזי סימטרי די הצורך הוא גרף קיילי, במובן הבא: אם חבורה G פועלת על מרחב גאודזי X כחבורה של איזומטריות, באופן שהמרחב אינו גדול מדי (המנה \ X/G קומפקטית) ואינו קטן מדי (לכל קבוצה קומפקטית \ K\subset X, הקבוצה \ \{g\in G: g(K) \cap K \neq \emptyset\} סופית), אז X קוואזי-איזומטרי לגרף קיילי של G (על ידי ההתאמה \ g \mapsto gx, כאשר \ x\in X נקודה קבועה). לדוגמה, אם M הוא יריעת רימן פשוטת קשר אז כל סריג קו-קומפקטי בחבורת האיזומטריות של M (לחלופין, החבורה היסודית של כל יריעת רימן קומפקטית ש-M הוא מרחב הכיסוי האוניברסלי שלה) הוא קוואזי-איזומטרי ל-M.

ראו גם[עריכת קוד מקור | עריכה]