Cayley grafiği - Cayley graph

İki üreteç a ve b üzerindeki serbest grubun Cayley grafiği

Gelen matematik bir Cayley grafik olarak da bilinen, Cayley renk grafiği , Cayley diyagramı , grup diyagramı ya da renk grubu a, grafik bir soyut yapısını kodlayan bir grup . Tanımı, Cayley teoremi ( Arthur Cayley'den sonra adlandırılır) tarafından önerilir ve grup için belirli bir jeneratör seti kullanır . Kombinatoryal ve geometrik grup teorisinde merkezi bir araçtır .

Tanım

Izin bir olmak grubu ve bir olmak jeneratör arasında . Cayley grafiği , aşağıdaki gibi oluşturulmuş kenar renkli yönlendirilmiş bir grafiktir : ${\görüntüleme stili G}$${\görüntüleme stili S}$${\görüntüleme stili G}$${\görüntüleme stili \Gama =\Gama (G,S)}$

• Her eleman arasında bir köşe atanır: tepe seti ile tanımlanır${\görüntüleme stili g}$${\görüntüleme stili G}$${\görüntüleme stili \Gama }$${\görüntüleme stili G.}$
• Her eleman ait olan bir renk atanır .${\görüntüleme stili s}$${\görüntüleme stili S}$${\ Displaystyle c_{s}}$
• Her için ve , bir renk yönlendirilmiş ayrıt karşılık gelen tepe noktasından birine tekabül eden .${\görüntüleme stili g\in G}$${\görüntüleme stili s\S}$${\ Displaystyle c_{s}}$${\görüntüleme stili g}$${\görüntüleme stili gs}$

Her kaynak grubu oluşturmayı gerektirmez . Eğer bir jeneratör değildir , daha sonra bir bağlantısı kesilmiş ve her bağlı bileşen tarafından üretilen bir alt-grubu, bir eşküme temsil eder . ${\görüntüleme stili S}$${\görüntüleme stili S}$${\görüntüleme stili G}$${\görüntüleme stili \Gama }$${\görüntüleme stili S}$

Bir eleman ise ve kendi tersidir, o zaman tipik olarak, yönsüz kenarı ile temsil edilmektedir. ${\görüntüleme stili s}$${\görüntüleme stili S}$${\görüntüleme stili s=s^{-1},}$

Grubu , bazen olduğu varsayılır simetrik (yani grup kimliği elemanı ihtiva eden) olup. Bu durumda, renklendirilmemiş Cayley grafiği basit bir yönsüz grafik olarak gösterilebilir . ${\görüntüleme stili S}$${\görüntüleme stili S=S^{-1}}$

Olarak geometrik grup teorinin , grubu genellikle hangi karşılık sonlu olduğu varsayılır lokal sonlu olması. ${\görüntüleme stili S}$${\görüntüleme stili \Gama }$

Örnekler

• Bunun sonsuz döngüsel grup olduğunu ve kümenin standart üretici 1 ve bunun tersinden (toplam gösterimde -1) oluştuğunu varsayalım ; o zaman Cayley grafiği sonsuz bir yoldur.${\displaystyle G=\mathbb {Z} }$${\görüntüleme stili S}$
• Benzer şekilde, mertebenin sonlu döngüsel grubu ise ve set , standart üreteci ve tersi olmak üzere iki elemandan oluşuyorsa , Cayley grafiği döngüdür . Daha genel olarak, sonlu döngüsel grupların Cayley grafikleri tam olarak döngüsel grafiklerdir .${\displaystyle G=\mathbb {Z} _{n}}$${\görüntüleme stili n}$${\görüntüleme stili S}$${\görüntüleme stili G}$ ${\ Displaystyle C_{n}}$
• Cayley grafiği grupların direkt ürün ile ( Kartezyen ürün bir jeneratör seti olarak jeneratör setleri) olan kartezyen ürün karşılık gelen Cayley grafikler. Bu nedenle, dört elemandan oluşan jeneratör setine sahip değişmeli grubun Cayley grafiği , düzlemdeki sonsuz ızgara iken , benzer jeneratörlere sahip doğrudan çarpım için Cayley grafiği, bir torus üzerindeki sonlu ızgaradır .${\displaystyle \mathbb {Z} ^{2}}$${\görüntüleme stili (\pm 1,0),(0,\pm 1)}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$${\görüntüleme stili n\ kere m}$

İki jeneratör a ve b üzerindeki dihedral grubun Cayley grafiği${\görüntüleme stili D_{4}}$

Cayley grafiği, her ikisi de kendi kendine ters olan iki jeneratör üzerinde${\görüntüleme stili D_{4}}$

• Bir Cayley grafiği dihedral grup iki jeneratörlere ve sola gösterilmiştir. Kırmızı oklar ile kompozisyonu temsil eder . Yana olan kendi kendine ters ile bileşim temsil mavi çizgi, , yönlendirilmeyen. Bu nedenle grafik karışıktır: sekiz köşesi, sekiz oku ve dört kenarı vardır. Cayley Tablo grubunun türetilebilir grup tanıtımı${\görüntüleme stili D_{4}}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili b}$${\görüntüleme stili D_{4}}$

${\displaystyle \langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$

Sağda farklı bir Cayley grafiği gösterilmektedir. hala yatay yansımadır ve mavi çizgilerle temsil edilir ve çapraz bir yansımadır ve pembe çizgilerle temsil edilir. Her iki yansıma da kendi kendine ters olduğundan, sağdaki Cayley grafiği tamamen yönsüzdür. Bu grafik sunuma karşılık gelir${\görüntüleme stili D_{4}}$${\görüntüleme stili b}$${\görüntüleme stili c}$

${\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}$

• İki üreteç üzerindeki serbest grubun ve kümeye karşılık gelen Cayley grafiği makalenin üst kısmında gösterilmiştir ve kimlik öğesini temsil eder . Bir kenar boyunca sağa doğru hareket, sağ çarpmayı temsil eder, bir kenar boyunca yukarı doğru hareket, çarpmaya karşılık gelir Serbest grubun hiçbir ilişkisi olmadığından , Cayley grafiğinin döngüsü yoktur . Bu Cayley grafiği 4 düzenli sonsuz bir ağaçtır ve Banach-Tarski paradoksunun ispatında önemli bir bileşendir .${\görüntüleme stili bir}$${\görüntüleme stili b}$${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$${\görüntüleme stili e}$${\görüntüleme stili bir,}$${\görüntüleme stili b.}$

Heisenberg grubunun Cayley grafiğinin bir parçası. (Renklendirme sadece görsel yardım içindir.)

• Ayrık Heisenberg grubunun bir Cayley grafiği

${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \sağ\}}$

sağda tasvir edilmiştir. Resimde kullanılan üreteçler , girişler için 1, 0, 0'lık üç permütasyon tarafından verilen üç matristir . Resimden de anlaşılabilecek ilişkileri tatmin ederler . Bu, değişmeli olmayan bir sonsuz gruptur ve üç boyutlu bir uzay olmasına rağmen, Cayley grafiği dört boyutlu hacim büyümesine sahiptir .${\görüntüleme stili X,Y,Z}$${\görüntüleme stili x,y,z}$${\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}$

i , j ve k kuaterniyonları ile çarpma döngülerini gösteren Cayley Q8 grafiği

karakterizasyon

Grup , sol çarpma ile kendi kendine etki eder (bkz. Cayley teoremi ). Bu , Cayley grafiğindeki eylemi olarak görülebilir . Açıkça, bir öğe bir tepe noktasını tepe noktasına eşler Cayley grafiğinin kenar kümesi ve renkleri bu eylemle korunur: kenar kenarla eşlenir , her ikisi de renklidir . Bir grubun kendi üzerindeki sol çarpma eylemi basitçe geçişlidir , özellikle Cayley grafikleri tepe-geçişlidir . Aşağıdakiler bununla ilgili bir tür sohbettir: ${\görüntüleme stili G}$ ${\görüntüleme stili G}$${\görüntüleme stili h\G'de}$${\ Displaystyle g\in V(\Gama )}$${\görüntüleme stili hg\in V(\Gama ).}$${\görüntüleme stili (g,gs)}$${\görüntüleme stili (hg,hgs)}$${\ Displaystyle c_{s}}$

Sabidussi Teoremi. Bir (etiketsiz ve renksiz) yönlendirilmiş grafik bir grubun Cayley grafiğidir bunun basit bir geçişli bir işlem kabul ancak ve ancak ile grafik automorphisms (yani yönelmiş kenarları kümesini muhafaza)${\görüntüleme stili \Gama }$${\görüntüleme stili G}$${\görüntüleme stili G}$ .

Grubu ve üretici kümeyi etiketlenmemiş yönlendirilmiş grafikten kurtarmak için bir tepe noktası seçin ve onu grubun kimlik öğesiyle etiketleyin. Daha sonra her bir köşe etiket arasında eşsiz elemanı ile bu haritalar için grubu üreteç bu verimler Cayley grafik olarak takım-komşularının etiket kümesidir . ${\görüntüleme stili G}$${\görüntüleme stili S}$${\görüntüleme stili \Gama ,}$${\displaystyle v_{1}\in V(\Gama )}$${\görüntüleme stili v}$${\görüntüleme stili \Gama }$${\görüntüleme stili G}$${\displaystyle v_{1}}$${\görüntüleme stili v.}$${\görüntüleme stili S}$${\görüntüleme stili G}$${\görüntüleme stili \Gama }$${\görüntüleme stili \Gama (G,S)}$${\displaystyle v_{1}}$

Temel özellikler

• Cayley grafiği , temel olarak jeneratör setinin seçimine bağlıdır . Jeneratör Örneğin, var elemanları daha sonra Cayley grafiğin her köşe sahiptir gelen ve giden yönlendirilmiş kenarları. Simetrik bir jeneratörün halinde olan elemanlar, Cayley grafiktir a, düzenli yönlendirilmiş grafik derece${\görüntüleme stili \Gama (G,S)}$${\görüntüleme stili S}$${\görüntüleme stili S}$${\görüntüleme stili k}$${\görüntüleme stili k}$${\görüntüleme stili k}$${\görüntüleme stili S}$${\görüntüleme stili r}$${\görüntüleme stili r.}$
• Cayley grafiğindeki döngüler (ya da kapalı yollar) öğeleri arasındaki ilişkileri gösterir Bir grubun Cayley kompleksinin daha ayrıntılı yapısında, ilişkilere karşılık gelen kapalı yollar çokgenlerle "doldurulur" . Belirli bir sunum Cayley grafiğini oluşturmak problemi bu araçlar çözme eşdeğerdir Kelime sorunu için .${\görüntüleme stili S.}$${\görüntüleme stili {\matematiksel {P}}}$${\görüntüleme stili {\matematiksel {P}}}$
• Eğer a, örten grubu homomorfizmi ve jeneratörün elemanların görüntüleri için farklı olan, o zaman grafikler bir kaplama indükler${\görüntüleme stili f:G'\G'ye}$ ${\ Displaystyle S'}$${\görüntüleme stili G'}$

${\displaystyle {\bar {f}}:\Gama (G',S')\to \Gama (G,S),}$

burada bir grup, özellikle, sahip her 2 ila sırası, farklı üreteçlerini, ve resim bunların terslerinden birlikte, bu jeneratörlerin oluşur, daha sonra Cayley grafik sonsuz düzenli ile kaplıdır ağaç derece tekabül eden serbest grubun aynısı üzerinde jeneratör seti.${\görüntüleme stili S=f(S').}$${\görüntüleme stili G}$${\görüntüleme stili k}$${\görüntüleme stili S}$${\görüntüleme stili \Gama (G,S)}$${\görüntüleme stili 2k}$

• Yönsüz olarak kabul edilen herhangi bir sonlu Cayley grafiği için, köşe bağlantısı , grafiğin derecesinin en az 2/3'üne eşittir . Üreten küme minimum ise (herhangi bir elemanın çıkarılması ve varsa, bunun tersi üreten kümeden çıkar, üretmeyen bir küme bırakır), tepe bağlantısı dereceye eşittir. Kenar bağlantısı her durumda derecede eşit bulunmaktadır.
• Her grup karakter grubunun bir sebep özvektörünü ait bitişiklik matrisi içinde . Zaman değişmeli olan, ilişkili özdeğer olan${\görüntüleme stili \chi }$${\görüntüleme stili G}$${\görüntüleme stili \Gama (G,S)}$${\görüntüleme stili G}$

${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi(ler).}$

Özellikle, önemsiz karakterin (her öğeyi 1'e gönderen) ilişkili özdeğeri, derecesi , yani sırasıdır . Eğer bir değişmeli grup olduğu, tam olarak orada tüm öz değerlerini belirlemek karakterler.${\görüntüleme stili \Gama (G,S)}$${\görüntüleme stili S}$${\görüntüleme stili G}$${\görüntüleme stili |G|}$

Schreier koset grafiği

Bunun yerine, köşeleri sabit bir alt grubun doğru kosetleri olarak alırsa, ilgili bir yapı elde eder , koset numaralandırmasının veya Todd-Coxeter sürecinin temelindeki Schreier koset grafiği . ${\görüntüleme stili H,}$

Grup teorisine bağlantı

Grubun yapısı hakkında bilgi, grafiğin komşuluk matrisini inceleyerek ve özellikle spektral çizge teorisinin teoremlerini uygulayarak elde edilebilir .

Cinsi bir grup, bu grubun bir Cayley grafiği için en az bir cinstir.

geometrik grup teorisi

Sonsuz gruplar için, Cayley grafiğinin kaba geometrisi , geometrik grup teorisi için esastır . Bir İçin sonlu üretilmiş grubun , bu jeneratörlerin sonlu seti, grubun dolayısıyla kendine özgü bir özelliği seçimi bağımsızdır. Bu sadece sonsuz gruplar için ilginçtir: her sonlu grup kabaca bir noktaya (veya önemsiz gruba) eşdeğerdir, çünkü bir kişi tüm grubu sonlu jeneratörler kümesi olarak seçebilir.

Resmi olarak, belirli bir üretici seçimi için , bir metrik uzayı belirleyen metrik (Cayley grafiğindeki doğal mesafe) kelimesi vardır . Bu uzayın kaba denklik sınıfı, grubun değişmezidir.

Tarih

Cayley grafikleri ilk olarak 1878'de Arthur Cayley tarafından sonlu gruplar için düşünüldü. Max Dehn , 1909–10 yılları arasında grup teorisi üzerine yayınlanmamış derslerinde, Cayley grafiklerini Gruppenbild (grup diyagramı) adı altında yeniden tanıttı ve bu, günümüzün geometrik grup teorisine yol açtı. En önemli bir uygulama çözeltisi, olduğu bir kelime sorun için temel grup ve yüzeyler bir noktaya yüzey sözleşme kapalı eğrileri karar topolojik sorun eşdeğerdir cinsi ≥ 2.

kafes

Bethe kafes veya sonsuz Cayley ağaç üzerindeki serbest grubun Cayley grafiktir jeneratörler. Bir grubun üreteçler tarafından sunumu, üreteçler üzerindeki serbest gruptan gruba ve Cayley grafikleri düzeyinde sonsuz Cayley ağacından Cayley grafiğine bir haritaya bir örtük haritaya karşılık gelir . Bu aynı zamanda ( cebirsel topolojide ) , Cayley grafiğinin genel olarak basitçe bağlantılı olmayan evrensel kapağı olarak da yorumlanabilir . ${\görüntüleme stili n}$${\görüntüleme stili G}$${\görüntüleme stili n}$${\görüntüleme stili n}$${\görüntüleme stili G,}$

Ayrıca bakınız

• Vertex-geçişli grafik
• Grup oluşturma
• Lovász varsayımı
• Küp bağlantılı çevrimler
• cebirsel çizge teorisi
• Döngü grafiği (cebir)

Notlar

Dış bağlantılar

• Cayley diyagramları
• Weisstein, Eric W. "Cayley grafiği" . Matematik Dünyası .