केली ग्राफ

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

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

परिभाषा

माना $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}$ है। अधिक सामान्यतः, परिमित चक्रीय समूहों के केली ग्राफ यथार्थत परिपत्र ग्राफ होते हैं।
• समूहों के प्रत्यक्ष उत्पाद का केली ग्राफ(उत्पादक समुच्चय के रूप में उत्पादक समुच्चय के कार्तीय उत्पाद के साथ) संबंधित केली ग्राफ का कार्तीय उत्पाद है। इस प्रकार चार अवयवों से युक्त $(\pm 1,0),(0,\pm 1)$ उत्पाद के समुच्चय के साथ एबेलियन समूह $\mathbb {Z} ^{2}$ का केली ग्राफ समतल $\mathbb {R} ^{2}$ पर अनंत जालक ग्राफ है, जबकि समान उत्पादक के साथ प्रत्यक्ष उत्पाद $\mathbb {Z} _{n}\times \mathbb {Z} _{m}$के लिए केली ग्राफ एक टोरस्र् पर $n\times m$ परिमित जालक है।

द्वितल समूह का केली ग्राफ $D_{4}$ दो उत्पादक ए और बी पर

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

• दो उत्पादक पर $a$ और $b$ पर द्वितल समूह $D_{4}$ का केली ग्राफ बाईं ओर दर्शाया गया है। लाल तीर $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$$

से मेल खाता है।

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

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

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

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

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

लिंक =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}$ होता है। किसी समूह की बाईं गुणन क्रिया मात्र सकर्मक होती है, विशेष रूप से, केली ग्राफ़ शीर्ष-सकर्मक ग्राफ होते हैं। इसका एक प्रकार का विलोम निम्नलिखित है:

सबिदुस्स की प्रमेय — एक (बिना लेबल वाला और बिना वर्ण का) निर्देशित ग्राफ $\Gamma$ एक समूह $G$ का केली ग्राफ है यदि और मात्र यदि यह ग्राफ स्वसमाकृतिकता (अर्थात, निर्देशित किनारों के समूच्चय को संरक्षित करते हुए) द्वारा $G$ की एक सरल सकर्मक क्रिया को स्वीकार करता है।

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

प्राथमिक गुण

• केली ग्राफ $\Gamma (G,S)$ उत्पादक के समुच्चय $S$ की विकल्प पर एक आवश्यक विधि से निर्भर करता है। उदाहरण के लिए, यदि उत्पादक समुच्चय $S$ में $k$ अवयव हैं तो केली ग्राफ के प्रत्येक शीर्ष में $k$ आगामी और $k$ निर्गामी निर्देशित किनारे हैं। $r$ अवयवों के साथ एक सममित उत्पादक समुच्चय $S$ के विषय में, केली ग्राफ परिमाण $r$ का एक नियमित ग्राफ है।
• केली ग्राफ में चक्र(ग्राफ सिद्धांत)(या संवृत चाल) $S$ के अवयवों के बीच संबंधों को दर्शाता है। एक समूह के केली परिसर के अधिक विस्तृत निर्माण में, संबंधों के अनुरूप संवृत पथ बहुभुजों द्वारा "भरे" जाते हैं। इसका तात्पर्य यह है कि दी गई प्रस्तुति ${\mathcal {P}}$ के केली ग्राफ निर्माण की समस्या ${\mathcal {P}}$ समूहों के लिए शब्द समस्या को हल करने के बराबर है।
• यदि $f:G'\to G$ एक विशेषण समूह समरूपता है और $G'$ के लिए उत्पादक समुच्चय $S'$ के अवयवों के प्रतिरूप भिन्न हैं, तो यह ग्राफ
  $${\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)]}$ है।
• समूह $G$ का प्रत्येक समूह गुणक वर्ण $\chi$, $\Gamma (G,S)$ के आसन्न आव्यूह के एक आइगेनसदिश को प्रेरित करता है । जब $G$ एबेलियन होता है, तो संबद्ध आइगेनमान
  $$\lambda _{\chi }=\sum _{s\in S}\chi (s),$$
  होता है, जो पूर्णांकों $j=0,1,\dots ,|G|-1$ के लिए
  $$\sum _{s\in S}e^{2\pi ijs/|G|}$$
  का रूप ले लेता है। विशेष रूप से,सामान्य वर्ण(जो प्रत्येक अवयव को 1 पर भेज रहा है) का संबद्ध आइगेनमान $\Gamma (G,S)$ का परिमाण है, अर्थात् $S$ का क्रम। यदि $G$ एक एबेलियन समूह है, तो यथार्थतः $|G|$ वर्ण हैं, जो सभी आइगेनमानों ​​​​का निर्धारण करते हैं। आइगेनसदिशों का संगत प्रसामान्य लांबिक विश्लेषण आधार $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$ के असमानेय निरूपण का एक पूरा समुच्चय लें, और आइगेनमान समुच्चय $\Lambda _{i}(S)$ के साथ ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ दें। तब $\Gamma (G,S)$ के आइगेनमानों ​​​​का समुच्चय ठीक ${\textstyle \bigcup _{i}\Lambda _{i}(S)}$ है, जहाँ आइगेनमान $\lambda$ $\rho _{i}(S)$ के आइगेनमान के रूप में $\lambda$ की प्रत्येक घटना के लिए बहुलता $\dim(\rho _{i})$ के साथ प्रकट होता है।

स्च्रिएर सह समुच्चय ग्राफ

Main article: स्च्रिएर सह समुच्चय ग्राफ

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

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

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

किसी समूह का जीनस(गणित) उस समूह के किसी भी केली ग्राफ के लिए न्यूनतम जीनस है।

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

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

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

विस्तार गुण

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

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

यदि एक असतत समूह $G$ के समीप काज़दान गुण (T) है, और $S$, $G$ का एक परिमित, सममित उत्पादक समूच्चय है, तो मात्र $G,S$ पर निर्भर करते हुए एक निरंतर $c>0$ स्थित है, जैसे कि $G$ के किसी भी परिमित भागफल $Q$ केली ग्राफ के लिए $S$ की प्रतिरूप के संबंध में $Q$ का एक $c$-विस्तारक है।

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

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

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

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

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

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

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

केली अभिन्न समूह $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\}}$ $G$ असमानेय वर्ण $\chi$ पर लिया गया है। इस समुच्चय में प्रत्येक आइगेनमान $\lambda _{\chi }$ का एक अवयव होना चाहिए $\zeta$ के लिए $\mathbb {Q} (\zeta )$ एक मौलिक $m^{th}$ एकात्मकता की घात(जहाँ $m$ को प्रत्येक $x_{i}$ की कोटि से विभाज्य होना चाहिए)। क्योंकि आइगेनमान बीजगणितीय पूर्णांक हैं, यह दर्शाने के लिए कि वे अभिन्न हैं, यह दर्शाना पर्याप्त है कि वे परिमेय हैं, और यह दर्शाने के लिए पर्याप्त है कि $\mathbb {Q} (\zeta )$ के किसी भी स्वसमाकृतिकता $\sigma$ के अंतर्गत $\lambda _{\chi }$ निश्चित है। कुछ $k$ अपेक्षाकृत अभाज्य होना चाहिए $m$ ऐसा है कि सभी $i$ के लिए $\sigma (\chi (x_{i}))=\chi (x_{i}^{k})$, और क्योंकि $S$ ऑयतर और सामान्य दोनों है, $\sigma (\chi (x_{i}))=\chi (x_{j})$ कुछ $j$ के लिए। $x\mapsto x^{k}$ भेजना संयुग्मन वर्गों को अलग करता है, इसलिए $\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: बेथे जालक

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

यह भी देखें

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

बाहरी संबंध

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