केली ग्राफ

File:Cayley graph of F2.svg

दो जनरेटर ए और बी पर मुक्त समूह का केली ग्राफ

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph|t-transitive, t ≥ 2]]		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

गणित में, केली ग्राफ, जिसे केली वर्ण ग्राफ, केली आरेख, समूह आरेख या वर्ण समूह के रूप में भी जाना जाता है एक ग्राफ (असतत गणित) है जो समूह (गणित) की अमूर्त संरचना को कूटबद्ध करता है। इसकी परिभाषा केली के प्रमेय (आर्थर केली के नाम पर) द्वारा सुझाई गई है, और समूह के लिए समूह के निर्दिष्ट उत्पादक समुच्चय का उपयोग करती है। यह संयोजी समूह सिद्धांत और ज्यामितीय समूह सिद्धांत में एक केंद्रीय उपकरण है। केली ग्राफ़ की संरचना और समरूपता उन्हें विस्तारक ग्राफ़ के वर्गों के निर्माण के लिए विशेष रूप से अच्छे पदान्वेषी बनाती है।

परिभाषा

माना $G$ एक समूह (गणित) है और $S$ $G$ का उत्पादक समुच्चय है। केली ग्राफ $\Gamma =\Gamma (G,S)$ एक ग्राफ वर्णना निर्देशित ग्राफ है जिसे इस प्रकार बनाया गया है:

• $G$ के प्रत्येक अवयव $g$ को शीर्ष नियत किया गया है: $\Gamma$ के शीर्ष समुच्चय की पहचान $G$ से की जाती है।
• $S$ के प्रत्येक अवयव $s$ को एक वर्ण $c_{s}$ दिया गया है।
• प्रत्येक $g\in G$ और $s\in S$ के लिए, $g$ के अनुरूप शीर्ष से वर्ण $c_{s}$ का एक निर्देशित किनारा होता है जो $gs$ के अनुरूप होता है।

हर स्रोत को इसकी आवश्यकता नहीं है $S$ समूह उत्पन्न करें। अगर $S$ के लिए उत्पादक समुच्चय नहीं है $G$, तब $\Gamma$ कनेक्टिविटी (ग्राफ़ थ्योरी) है और प्रत्येक कनेक्टेड घटक द्वारा उत्पन्न उपसमूह के एक कोसमुच्चय का प्रतिनिधित्व करता है $S$.

यदि कोई अवयव $s$ का $S$ अपना ही उलटा है, $s=s^{-1},$ तब यह आमतौर पर एक अप्रत्यक्ष किनारे द्वारा दर्शाया जाता है।

समुच्चय $S$ कभी-कभी सममित समुच्चय माना जाता है (यानी $S=S^{-1}$) और इसमें समूह का पहचान अवयव शामिल नहीं है। इस मामले में, बिना वर्ण का केली ग्राफ को एक साधारण अप्रत्यक्ष ग्राफ (असतत गणित) के रूप में दर्शाया जा सकता है।

ज्यामितीय समूह सिद्धांत में, समुच्चय $S$ अक्सर परिमित माना जाता है जो इससे मेल खाता है $\Gamma$ स्थानीय रूप से परिमित होना।

उदाहरण

• लगता है कि $G=\mathbb {Z}$ अनंत चक्रीय समूह और समुच्चय है $S$ मानक जनरेटर 1 और इसके व्युत्क्रम (योगात्मक संकेतन में -1) से मिलकर बनता है; तो केली ग्राफ एक अनंत पथ है।
• इसी प्रकार यदि $G=\mathbb {Z} _{n}$ क्रम का परिमित चक्रीय समूह है $n$ और समुच्चय $S$ दो अवयवों के होते हैं, के मानक जनरेटर $G$ और इसका व्युत्क्रम, तो केली ग्राफ चक्र ग्राफ है $C_{n}$. अधिक आम तौर पर, परिमित चक्रीय समूहों के केली ग्राफ वास्तव में परिपत्र ग्राफ होते हैं।
• समूहों के प्रत्यक्ष उत्पाद का केली ग्राफ (जेनरेटिंग समुच्चय के रूप में जेनरेटिंग समुच्चय के कार्टेशियन उत्पाद के साथ) संबंधित केली ग्राफ के ग्राफ का कार्टेशियन उत्पाद है। इस प्रकार एबेलियन समूह का केली ग्राफ $\mathbb {Z} ^{2}$ चार अवयवों से युक्त जनरेटर के समुच्चय के साथ $(\pm 1,0),(0,\pm 1)$ विमान पर अनंत ग्रिड ग्राफ है $\mathbb {R} ^{2}$, जबकि प्रत्यक्ष उत्पाद के लिए $\mathbb {Z} _{n}\times \mathbb {Z} _{m}$ समान जनरेटर के साथ केली ग्राफ है $n\times m$ एक टोरस्र्स पर परिमित ग्रिड।

File:Dih 4 Cayley Graph; generators a, b.svg

डायहेड्रल समूह का केली ग्राफ $D_{4}$ दो जनरेटर ए और बी पर

File:Dih 4 Cayley Graph; generators b, c.svg

का केली ग्राफ $D_{4}$, दो जनरेटर पर जो दोनों स्व-प्रतिलोम हैं

* डायहेड्रल समूह का केली ग्राफ $D_{4}$ दो जनरेटर पर $a$ और $b$ बाईं ओर दर्शाया गया है। लाल तीर रचना का प्रतिनिधित्व करते हैं $a$. तब से $b$ केली टेबल है | स्व-उलटा, नीली रेखाएँ, जो रचना का प्रतिनिधित्व करती हैं $b$, अप्रत्यक्ष हैं। इसलिए ग्राफ मिश्रित है: इसमें आठ शीर्ष, आठ तीर और चार किनारे हैं। समूह की केली टेबल $D_{4}$ एक समूह की प्रस्तुति से प्राप्त किया जा सकता है

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

का एक अलग केली ग्राफ $D_{4}$ दाईं ओर दिखाया गया है। $b$ अभी भी क्षैतिज प्रतिबिंब है और नीली रेखाओं द्वारा दर्शाया गया है, और $c$ एक विकर्ण प्रतिबिंब है और गुलाबी रेखाओं द्वारा दर्शाया गया है। चूंकि दोनों प्रतिबिंब स्व-उलटा हैं, दाईं ओर केली ग्राफ पूरी तरह से अप्रत्यक्ष है। यह ग्राफ प्रस्तुति से मेल खाता है

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

• दो जनरेटर पर मुक्त समूह का केली ग्राफ $a$ और $b$ समुच्चय के अनुरूप $S=\{a,b,a^{-1},b^{-1}\}$ लेख के शीर्ष पर दर्शाया गया है, और $e$ पहचान अवयव का प्रतिनिधित्व करता है। एक किनारे के साथ दाईं ओर यात्रा करना द्वारा सही गुणन का प्रतिनिधित्व करता है $a,$ किनारे के साथ ऊपर की ओर यात्रा करते समय गुणन से मेल खाती है $b.$ चूंकि मुक्त समूह में समूह की कोई प्रस्तुति नहीं है, केली ग्राफ में कोई चक्र (ग्राफ सिद्धांत) नहीं है। यह केली ग्राफ एक 4-नियमित ग्राफ अनंत वृक्ष (ग्राफ सिद्धांत) है और बनच-टार्स्की विरोधाभास के प्रमाण में एक प्रमुख घटक है।

File:HeisenbergCayleyGraph.png

हाइजेनबर्ग समूह के केली ग्राफ का हिस्सा। (वर्ण केवल दृश्य सहायता के लिए है।)

* असतत हाइजेनबर्ग समूह का केली ग्राफ

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

दाईं ओर दर्शाया गया है। चित्र में प्रयुक्त जनरेटर तीन मैट्रिसेस हैं $X,Y,Z$ प्रविष्टियों के लिए 1, 0, 0 के तीन क्रमपरिवर्तन द्वारा दिया गया $x,y,z$. वे संबंधों को संतुष्ट करते हैं $Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY$जिसे तस्वीर से भी समझा जा सकता है। यह एक नाबेलियन समूह है। गैर-कम्यूटेटिव अनंत समूह, और तीन आयामी स्थान होने के बावजूद, केली ग्राफ में चार आयामी विकास दर (समूह सिद्धांत) है।

Error creating thumbnail:

लिंक =https://upload.wikimedia.org/wikipedia/commons/0/04/Cayley_Q8_quaternion_multiplication_graph.svgs i, j और k

विशेषता

समूह $G$ बाएँ गुणन द्वारा स्वयं पर समूह क्रिया (गणित) (केली की प्रमेय देखें)। की क्रिया के रूप में देखा जा सकता है $G$ इसके केली ग्राफ पर। स्पष्ट रूप से, एक अवयव $h\in G$ एक शीर्ष को मैप करता है $g\in V(\Gamma )$ शिखर तक $hg\in V(\Gamma ).$ केली ग्राफ के किनारों का समुच्चय और उनका वर्ण इस क्रिया द्वारा संरक्षित है: किनारा $(g,gs)$ किनारे पर मैप किया गया है $(hg,hgs)$, दोनों का वर्ण है $c_{s}$. किसी समूह की बाईं गुणन क्रिया केवल सकर्मक होती है, विशेष रूप से, केली ग्राफ़ शीर्ष-सकर्मक ग्राफ | वर्टेक्स-ट्रांसिटिव होते हैं। इसका एक प्रकार का विलोम निम्नलिखित है:

Sabidussi's Theorem — An (unlabeled and uncolored) directed graph $\Gamma$ is a Cayley graph of a group $G$ if and only if it admits a simply transitive action of $G$ by graph automorphisms (i.e., preserving the set of directed edges).

समूह को पुनर्प्राप्त करने के लिए $G$ और उत्पादक समुच्चय $S$ बिना लेबल वाले निर्देशित ग्राफ़ से $\Gamma ,$ एक शीर्ष का चयन करें $v_{1}\in V(\Gamma )$ और इसे समूह के पहचान अवयव द्वारा लेबल करें। फिर प्रत्येक शीर्ष को लेबल करें $v$ का $\Gamma$ के अनूठे अवयव द्वारा $G$ वह मानचित्र $v_{1}$ को $v.$ समुच्चय $S$ के जनरेटर के $G$ कि पैदावार $\Gamma$ केली ग्राफ के रूप में $\Gamma (G,S)$ के बाहरी पड़ोसियों के लेबल का समुच्चय है $v_{1}$.

प्राथमिक गुण

• केली ग्राफ $\Gamma (G,S)$ समुच्चय की पसंद पर एक आवश्यक तरीके से निर्भर करता है $S$ जनरेटर की। उदाहरण के लिए, यदि उत्पादक समुच्चय $S$ है $k$ अवयव हैं तो केली ग्राफ के प्रत्येक शीर्ष में है $k$ आने वाला और $k$ निवर्तमान निर्देशित किनारों। एक सममित उत्पादक समुच्चय के मामले में $S$ साथ $r$ अवयवों, केली ग्राफ डिग्री का एक नियमित ग्राफ है $r.$
• केली ग्राफ में साइकिल (ग्राफ थ्योरी) (या क्लोज्ड वॉक) के अवयवों के बीच एक समूह की प्रस्तुति को दर्शाता है $S.$ एक समूह के केली परिसर के अधिक विस्तृत निर्माण में, संबंधों के अनुरूप बंद पथ बहुभुजों द्वारा भरे जाते हैं। इसका मतलब यह है कि दी गई प्रस्तुति के केली ग्राफ के निर्माण की समस्या ${\mathcal {P}}$ के लिए समूहों के लिए शब्द समस्या को हल करने के बराबर है ${\mathcal {P}}$.* अगर $f:G'\to G$ एक विशेषण समूह समरूपता है और उत्पादक समुच्चय के अवयवों की छवियां हैं $S'$ के लिए $G'$ अलग हैं, तो यह ग्राफ के आवरण को प्रेरित करता है
  $${\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),$$
  कहाँ $S=f(S').$ विशेष रूप से, यदि एक समूह $G$ है $k$ जनरेटर, सभी ऑर्डर 2 से अलग हैं, और समुच्चय $S$ इन जनरेटरों के साथ उनके व्युत्क्रम होते हैं, फिर केली ग्राफ $\Gamma (G,S)$ डिग्री के अनंत नियमित वृक्ष (ग्राफ सिद्धांत) द्वारा कवर किया गया है $2k$ जनरेटर के एक ही समुच्चय पर मुक्त समूह के अनुरूप।
• किसी भी परिमित केली ग्राफ के लिए, जिसे अप्रत्यक्ष माना जाता है, कनेक्टिविटी (ग्राफ सिद्धांत) ग्राफ के डिग्री (ग्राफ सिद्धांत) के कम से कम 2/3 के बराबर है। यदि उत्पादक समुच्चय न्यूनतम है (किसी भी अवयव को हटाना और यदि मौजूद है, तो जेनरेटिंग समुच्चय से इसका व्युत्क्रम एक समुच्चय छोड़ देता है जो उत्पन्न नहीं कर रहा है), वर्टेक्स कनेक्टिविटी डिग्री के बराबर है। कनेक्टिविटी (ग्राफ सिद्धांत) सभी मामलों में डिग्री के बराबर है।
• अगर $\rho _{\text{reg}}(g)(x)=gx$ के साथ वाम-नियमित प्रतिनिधित्व है $|G|\times |G|$ मैट्रिक्स फॉर्म निरूपित $[\rho _{\text{reg}}(g)]$, का आसन्न मैट्रिक्स $\Gamma (G,S)$ है ${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(g)]}$.
• प्रत्येक समूह गुणक वर्ण $\chi$ समूह का $G$ के आसन्न मैट्रिक्स के एक eigenvector को प्रेरित करता है $\Gamma (G,S)$. कब $G$ एबेलियन है, संबंधित eigenvalue है
  $$\lambda _{\chi }=\sum _{s\in S}\chi (s),$$
  जो रूप धारण कर लेता है
  $$\sum _{s\in S}e^{2\pi ijs/|G|}$$
  पूर्णांकों के लिए $j=0,1,\dots ,|G|-1.$ विशेष रूप से, तुच्छ चरित्र (जो प्रत्येक अवयव को 1 पर भेज रहा है) का संबंधित ईजेनवेल्यू की डिग्री है $\Gamma (G,S)$, अर्थात् का क्रम $S$. अगर $G$ एक एबेलियन समूह है, बिल्कुल हैं $|G|$ वर्ण, सभी eigenvalues ​​​​का निर्धारण। ईजेनवेक्टरों के संबंधित ऑर्थोनॉर्मल आधार द्वारा दिया गया है $v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.$ यह ध्यान रखना दिलचस्प है कि यह ईजेनबेसिस उत्पादक समुच्चय से स्वतंत्र है $S$.
  अधिक आम तौर पर सममित उत्पादक समुच्चय के लिए, लें $\rho _{1},\dots ,\rho _{k}$ के अलघुकरणीय अभ्यावेदन का एक पूरा समुच्चय $G,$ और जाने ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ आइगेनवैल्यू समुच्चय के साथ $\Lambda _{i}(S)$. फिर के eigenvalues ​​​​का समुच्चय $\Gamma (G,S)$ बिल्कुल सही है ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ जहां eigenvalue $\lambda$ बहुलता से प्रकट होता है $\dim(\rho _{i})$ की प्रत्येक घटना के लिए $\lambda$ के आइगेनवैल्यू के रूप में $\rho _{i}(S).$

स्क्रीमर कोसमुच्चय ग्राफ

Main article: Schreier coset graph

यदि एक, इसके बजाय, एक निश्चित उपसमूह के सही सहसमुच्चय होने के लिए कोने लेता है $H,$ एक संबंधित निर्माण, श्रेयर कॉस्टेट ग्राफ प्राप्त करता है, जो कोसमुच्चय गणना या टोड-कॉक्समुच्चयर प्रक्रिया के आधार पर है।

समूह सिद्धांत से संबंध

समूह की संरचना के बारे में ज्ञान ग्राफ के आसन्न मैट्रिक्स का अध्ययन करके और विशेष रूप से वर्णक्रमीय ग्राफ सिद्धांत के प्रमेयों को लागू करके प्राप्त किया जा सकता है। इसके विपरीत, सममित उत्पादक समुच्चय के लिए, वर्णक्रमीय और प्रतिनिधित्व सिद्धांत $\Gamma (G,S)$ सीधे एक साथ बंधे हैं: लो $\rho _{1},\dots ,\rho _{k}$ के अलघुकरणीय अभ्यावेदन का एक पूरा समुच्चय $G,$ और जाने ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ आइगेनवैल्यू के साथ $\Lambda _{i}(S)$. फिर के eigenvalues ​​​​का समुच्चय $\Gamma (G,S)$ बिल्कुल सही है ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ जहां eigenvalue $\lambda$ बहुलता से प्रकट होता है $\dim(\rho _{i})$ की प्रत्येक घटना के लिए $\lambda$ के आइगेनवैल्यू के रूप में $\rho _{i}(S).$ किसी समूह का जीनस (गणित) उस समूह के किसी भी केली ग्राफ के लिए न्यूनतम जीनस है।

ज्यामितीय समूह सिद्धांत

अनंत समूहों के लिए, केली ग्राफ की मोटे संरचना ज्यामितीय समूह सिद्धांत के लिए मौलिक है। एक अंतिम रूप से उत्पन्न समूह के लिए, यह जनरेटर के परिमित समुच्चय की पसंद से स्वतंत्र है, इसलिए समूह की एक आंतरिक संपत्ति है। यह केवल अनंत समूहों के लिए दिलचस्प है: प्रत्येक परिमित समूह मोटे तौर पर एक बिंदु (या तुच्छ समूह) के बराबर होता है, क्योंकि कोई भी पूरे समूह को जनरेटर के परिमित समुच्चय के रूप में चुन सकता है।

औपचारिक रूप से, जनरेटर के दिए गए विकल्प के लिए, एक शब्द मीट्रिक (केली ग्राफ पर प्राकृतिक दूरी) होता है, जो एक मीट्रिक स्थान निर्धारित करता है। इस स्थान का मोटा तुल्यता वर्ग समूह का एक अपरिवर्तनीय है।

विस्तार गुण

कब $S=S^{-1}$, केली ग्राफ $\Gamma (G,S)$ है $|S|$-नियमित, इसलिए ग्राफ के विस्तारक ग्राफ का विश्लेषण करने के लिए वर्णक्रमीय तकनीकों का उपयोग किया जा सकता है। विशेष रूप से एबेलियन समूहों के लिए, केली ग्राफ के ईगेनवेल्यू अधिक आसानी से गणना योग्य हैं और इनके द्वारा दिए गए हैं ${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$ शीर्ष eigenvalue के बराबर $|S|$, इसलिए हम वर्णक्रमीय अंतर का उपयोग करके किनारे के विस्तार अनुपात को सीमित करने के लिए स्पेक्ट्रल ग्राफ सिद्धांत#चीजर असमानता|चीजर की असमानता का उपयोग कर सकते हैं।

कज़्दान संपत्ति (टी) के रूप में, इस तरह के विस्तारित केली ग्राफ़ के निर्माण के लिए प्रतिनिधित्व सिद्धांत का उपयोग किया जा सकता है। निम्नलिखित कथन धारण करता है:

If a discrete group $G$ has Kazhdan's property (T), and $S$ is a finite, symmetric generating set of $G$, then there exists a constant $c>0$ depending only on $G,S$ such that for any finite quotient $Q$ of $G$ the Cayley graph of $Q$ with respect to the image of $S$ is a $c$-expander.

उदाहरण के लिए समूह $G=\mathrm {SL} _{3}(\mathbb {Z} )$ संपत्ति (टी) है और प्राथमिक मैट्रिक्स द्वारा उत्पन्न होती है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देती है।

अभिन्न वर्गीकरण

एक अभिन्न ग्राफ वह होता है जिसके आइगेनवैल्यू सभी पूर्णांक होते हैं। जबकि इंटीग्रल ग्राफ़ का पूर्ण वर्गीकरण एक खुली समस्या है, कुछ समूहों के केली ग्राफ़ हमेशा इंटीग्रल होते हैं। केली ग्राफ के स्पेक्ट्रम के पिछले लक्षण वर्णन का उपयोग करते हुए, ध्यान दें $\Gamma (G,S)$ अभिन्न है अगर के eigenvalues $\rho (S)$ हर प्रतिनिधित्व के लिए अभिन्न हैं $\rho$ का $G$.

केली अभिन्न सरल समूह

एक समूह $G$ केली इंटीग्रल सिंपल (CIS) है अगर कनेक्टेड केली ग्राफ $\Gamma (G,S)$ सममित उत्पादक समुच्चय होने पर बिल्कुल अभिन्न है $S$ के एक उपसमूह का पूरक है $G$. अहमदी, बेल और मोहर के परिणाम से पता चलता है कि सभी सीआईएस समूह आइसोमॉर्फिक हैं $\mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z}$, या $\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ प्राइम्स के लिए $p$. यह महत्वपूर्ण है कि $S$ वास्तव में पूरे समूह को उत्पन्न करता है $G$ केली ग्राफ को जोड़ने के लिए। (अगर $S$ उत्पन्न नहीं करता $G$, केली ग्राफ अभी भी अभिन्न हो सकता है, लेकिन इसका पूरक है $S$ जरूरी नहीं कि एक उपसमूह हो।)

के उदाहरण में $G=\mathbb {Z} /5\mathbb {Z}$, सममित उत्पादक समुच्चय (ग्राफ़ समरूपता तक) हैं

• $S=\{1,4\}$: $\Gamma (G,S)$ एक है $5$- आइगेनवैल्यू के साथ साइकिल $2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}$
• $S=\{1,2,3,4\}$: $\Gamma (G,S)$ है $K_{5}$ आइगेनवैल्यू के साथ $4,-1,-1,-1,-1$

का एकमात्र उपसमूह $\mathbb {Z} /5\mathbb {Z}$ संपूर्ण समूह और तुच्छ समूह हैं, और केवल सममित उत्पादक समुच्चय हैं $S$ जो एक अभिन्न ग्राफ का उत्पादन करता है वह तुच्छ समूह का पूरक है। इसलिए $\mathbb {Z} /5\mathbb {Z}$ एक सीआईएस समूह होना चाहिए।

पूर्ण CIS वर्गीकरण का प्रमाण इस तथ्य का उपयोग करता है कि CIS समूह का प्रत्येक उपसमूह और होमोमोर्फिक छवि भी CIS समूह है।

केली अभिन्न समूह

केली इंटीग्रल ग्रुप की एक थोड़ी अलग धारणा है $G$, जिसमें प्रत्येक सममित उपसमुच्चय $S$ एक अभिन्न ग्राफ बनाता है $\Gamma (G,S)$. ध्यान दें कि $S$ अब पूरे समूह को उत्पन्न नहीं करना है।

केली अभिन्न समूहों की पूरी सूची किसके द्वारा दी गई है $\mathbb {Z} _{2}^{n}\times \mathbb {Z} _{3}^{m},\mathbb {Z} _{2}^{n}\times \mathbb {Z} _{4}^{n},Q_{8}\times \mathbb {Z} _{2}^{n},S_{3}$, और ऑर्डर का डायसाइक्लिक समूह $12$, कहाँ $m,n\in \mathbb {Z} _{\geq 0}$ और $Q_{8}$ चतुष्कोणीय समूह है।प्रमाण केली अभिन्न समूहों के दो महत्वपूर्ण गुणों पर निर्भर करता है:

• केली इंटीग्रल ग्रुप के सबग्रुप और होमोमोर्फिक इमेज भी केली इंटीग्रल ग्रुप हैं।
• एक समूह केली इंटीग्रल है अगर समूह का हर जुड़ा केली ग्राफ भी इंटीग्रल है।

सामान्य और ऑयलेरियन उत्पादक समुच्चय

एक सामान्य समूह दिया $G$, उपसमुच्चय $S\subseteq G$ सामान्य है अगर $S$ के अवयवों द्वारा संयुग्मन (समूह सिद्धांत) के तहत बंद है $G$ (एक सामान्य उपसमूह की धारणा को सामान्य बनाना), और $S$ यदि प्रत्येक के लिए ऑयलरीय है $s\in S$, चक्रीय समूह उत्पन्न करने वाले अवयवों का समूह $\langle s\rangle$ में भी निहित है $S$. गुओ, लिटकिना, माजुरोव और रेविन द्वारा 2019 का परिणाम साबित करता है कि केली ग्राफ $\Gamma (G,S)$ किसी भी ऑयलरीय प्रसामान्य उपसमुच्चय के लिए अभिन्न है $S\subseteq G$, विशुद्ध रूप से प्रतिनिधित्व सैद्धांतिक तकनीकों का उपयोग करते हुए। इस परिणाम का प्रमाण अपेक्षाकृत कम है: दिया गया $S$ एक ऑयलरीय प्रसामान्य उपसमुच्चय, चयन करें $x_{1},\dots ,x_{t}\in G$ जोड़ीदार असंयुग्मी ताकि $S$ संयुग्मी वर्गों का संघ है $\operatorname {Cl} (x_{i})$. फिर एक केली ग्राफ के स्पेक्ट्रम के लक्षण वर्णन का उपयोग करके, कोई आइगेनवेल्यू दिखा सकता है $\Gamma (G,S)$ द्वारा दिए गए हैं ${\textstyle \left\{\lambda _{\chi }=\sum _{i=1}^{t}{\frac {\chi (x_{i})\left|\operatorname {Cl} (x_{i})\right|}{\chi (1)}}\right\}}$ अप्रासंगिक पात्रों पर कब्जा कर लिया $\chi$ का $G$. प्रत्येक आइगेनवैल्यू $\lambda _{\chi }$ इस समुच्चय में का एक अवयव होना चाहिए $\mathbb {Q} (\zeta )$ के लिए $\zeta$ एक आदिम $m^{th}$ एकता की जड़ (जहाँ $m$ प्रत्येक के आदेश से विभाज्य होना चाहिए $x_{i}$). क्योंकि आइगेनमान बीजगणितीय पूर्णांक हैं, यह दर्शाने के लिए कि वे अभिन्न हैं, यह दर्शाना पर्याप्त है कि वे परिमेय हैं, और यह दर्शाने के लिए पर्याप्त है $\lambda _{\chi }$ किसी भी ऑटोमोर्फिज्म के तहत तय किया गया है $\sigma$ का $\mathbb {Q} (\zeta )$. कुछ होना चाहिए $k$ अपेक्षाकृत प्रधान $m$ ऐसा है कि $\sigma (\chi (x_{i}))=\chi (x_{i}^{k})$ सभी के लिए $i$, और क्योंकि $S$ ऑयलरीय और सामान्य दोनों है, $\sigma (\chi (x_{i}))=\chi (x_{j})$ कुछ के लिए $j$. भेजना $x\mapsto x^{k}$ bijects संयुग्मी वर्ग, इसलिए $\operatorname {Cl} (x_{i})$ और $\operatorname {Cl} (x_{j})$ एक ही आकार और है $\sigma$ केवल के योग में शर्तों की अनुमति देता है $\lambda _{\chi }$. इसलिए $\lambda _{\chi }$ के सभी ऑटोमोर्फिज्म के लिए तय है $\mathbb {Q} (\zeta )$, इसलिए $\lambda _{\chi }$ तर्कसंगत है और इस प्रकार अभिन्न है।

नतीजतन, अगर $G=A_{n}$ वैकल्पिक समूह है और $S$ द्वारा दिए गए क्रमपरिवर्तन का एक समुच्चय है $\{(12i)^{\pm 1}\}$, फिर केली ग्राफ $\Gamma (A_{n},S)$ अभिन्न है। (इससे कौरोव्का नोटबुक की पहले से खुली हुई समस्या हल हो गई।) इसके अलावा जब $G=S_{n}$ सममित समूह है और $S$ या तो सभी ट्रांसपोज़िशन का समुच्चय है या किसी विशेष अवयव, केली ग्राफ़ को शामिल करने वाले ट्रांसपोज़िशन का समुच्चय है $\Gamma (G,S)$ अभिन्न भी है।

इतिहास

1878 में आर्थर केली द्वारा परिमित समूहों के लिए केली ग्राफ पर पहली बार विचार किया गया था।मैक्स डेहन ने 1909-10 के समूह सिद्धांत पर अपने अप्रकाशित व्याख्यान में ग्रुपेनबिल्ड (समूह आरेख) नाम के तहत केली ग्राफ को फिर से प्रस्तुत किया, जिसने आज के ज्यामितीय समूह सिद्धांत को जन्म दिया। उनका सबसे महत्वपूर्ण अनुप्रयोग जीनस ≥ 2 के साथ भूतल (टोपोलॉजी) के मौलिक समूह के लिए शब्द समस्या (गणित) का समाधान था, जो सतह के अनुबंध पर एक बिंदु पर बंद घटता तय करने की सामयिक समस्या के बराबर है।

बेठे जाली

Main article: Bethe lattice

बेथे जाली या अनंत केली वृक्ष मुक्त समूह का केली ग्राफ है $n$ जनरेटर। एक समूह की प्रस्तुति $G$ द्वारा $n$ जनरेटर मुक्त समूह से एक विशेषण मानचित्र से मेल खाता है $n$ समूह के लिए जनरेटर $G,$ और केली ग्राफ के स्तर पर अनंत केली पेड़ से केली ग्राफ तक एक मानचित्र पर। इसे (बीजगणितीय टोपोलॉजी में) केली ग्राफ के सार्वभौमिक आवरण के रूप में भी व्याख्या किया जा सकता है, जो सामान्य रूप से जुड़ा नहीं है।

यह भी देखें

• वर्टेक्स-सकर्मक ग्राफ
• एक समूह का समुच्चय बनाना
• लोवाज़ अनुमान
• क्यूब से जुड़े चक्र
• बीजगणितीय ग्राफ सिद्धांत
• साइकिल ग्राफ (बीजगणित)

बाहरी संबंध

• Cayley diagrams
• Weisstein, Eric W. "Cayley graph". MathWorld.