केली ग्राफ: Difference between revisions

Latest revision as of 09:22, 20 February 2023

Error creating thumbnail:

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

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

परिभाषा

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

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

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

दो उत्पादक पर $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-नियमित ग्राफ अनंत वृक्ष(ग्राफ सिद्धांत) है और बनच-टार्स्की विरोधाभास के प्रमाण में एक प्रमुख घटक है।

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

हैं जो प्रविष्टियों

x,y,z

के लिए 1, 0, 0 के तीन क्रमपरिवर्तन द्वारा दिए गए हैं। वे संबंधों

Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY

को संतुष्ट करते हैं जिसे चित्र से भी समझा जा सकता है। यह एक गैर विनिमेय अनंत समूह है,और त्रि-आयामी स्थान होने के अतिरिक्त, केली ग्राफ में चतुर्थ-आयामी विकास दर(समूह सिद्धांत) है।^{[citation needed]}

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

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

समूह $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}}$ समूहों के लिए शब्द समस्या को हल करने के बराबर है।^[1]
यदि $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 के बराबर है। यदि उत्पादक समुच्चय न्यूनतम है(किसी भी अवयव को हटाना और यदि स्थित है, तो उत्पादक समुच्चय से इसका व्युत्क्रम एक समुच्चय छोड़ देता है जो उत्पन्न नहीं कर रहा है), शीर्ष संयोजकता परिमाण के बराबर है। संयोजकता(ग्राफ सिद्धांत) सभी विषयों में परिमाण के बराबर है।^[5]
यदि $\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})$ के साथ प्रकट होता है।

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

यदि कोई, इसके अतिरिक्त, एक निश्चित उपसमूह $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})$ के साथ प्रकट होता है।

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

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

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

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

विस्तार गुण

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

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

यदि एक असतत समूह $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}$ समरूपी हैं ।^[8] यह महत्वपूर्ण है कि केली ग्राफ को जोड़ने के लिए $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}$ एक सीआईएस समूह होना चाहिए।

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

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

केली अभिन्न समूह $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}$ चतुष्कोणीय समूह है।^[8] प्रमाण केली अभिन्न समूहों के दो महत्वपूर्ण गुणों पर निर्भर करता है:

केली अभिन्न समूह के उपसमूह और समरूपी प्रतिरूप भी केली अभिन्न समूह हैं।
एक समूह केली अभिन्न है यदि समूह का प्रत्येक संयुक्त केली ग्राफ भी अभिन्न है।

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

एक सामान्य समूह $G$ दिया गया है, एक उपसमुच्चय $S\subseteq G$ सामान्य है यदि $S$ $G$ के अवयवों(एक सामान्य उपसमूह की धारणा को सामान्य बनाने) के संयुग्मन(समूह सिद्धांत) के अंतर्गत संवृत है, और $S$ ऑयतर है यदि प्रत्येक $s\in S$ के लिए, चक्रीय समूह उत्पन्न करने वाले अवयवों का समुच्चय $\langle s\rangle$ भी $S$ में निहित है। गुओ, लिटकिना, माजुरोव और रेवेन द्वारा 2019 का परिणाम सिद्ध करता है कि केली ग्राफ $\Gamma (G,S)$ किसी भी ऑयतर प्रसामान्य उपसमुच्चय $S\subseteq G$ के लिए अभिन्न है, जो विशुद्ध रूप से प्रतिनिधित्व सैद्धांतिक तकनीकों का उपयोग करता है।^[9]

इस परिणाम का प्रमाण अपेक्षाकृत कम है: $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 में आर्थर केली द्वारा परिमित समूहों के लिए केली ग्राफ पर पहली बार विचार किया गया था।^[2] मैक्स डेहन ने 1909-10 के समूह सिद्धांत पर अपने अप्रकाशित व्याख्यान में ग्रुपेनबिल्ड(समूह आरेख) नाम के अंतर्गत केली ग्राफ को फिर से प्रस्तुत किया, जिसने आज के ज्यामितीय समूह सिद्धांत को जन्म दिया। उनका सबसे महत्वपूर्ण अनुप्रयोग जीनस ≥ 2 के साथ भूतल(टोपोलॉजी) के मौलिक समूह के लिए शब्द समस्या(गणित) का हल था, जो सतह के अनुबंध पर एक बिंदु पर संवृत घटता निश्चित करने की सामयिक समस्या के बराबर है।^[10]

बेथे जालक

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

यह भी देखें

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

↑ ^1.0 ^1.1 Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.
↑ ^2.0 ^2.1 Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.
↑ Theron, Daniel Peter (1988), An extension of the concept of graphically regular representations, Ph.D. thesis, University of Wisconsin, Madison, p. 46, MR 2636729.
↑ Sabidussi, Gert (October 1958). "On a class of fixed-point-free graphs". Proceedings of the American Mathematical Society. 9 (5): 800–4. doi:10.1090/s0002-9939-1958-0097068-7. JSTOR 2033090.
↑ See Theorem 3.7 of Babai, László (1995). "27. Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.). Handbook of Combinatorics. Vol. 1. Elsevier. pp. 1447–1540. ISBN 9780444823465.
↑ White, Arthur T. (1972). "On the genus of a group". Transactions of the American Mathematical Society. 173: 203–214. doi:10.1090/S0002-9947-1972-0317980-2. MR 0317980.
↑ Proposition 1.12 in Lubotzky, Alexander (2012). "Expander graphs in pure and applied mathematics". Bulletin of the American Mathematical Society. 49: 113–162. arXiv:1105.2389. doi:10.1090/S0273-0979-2011-01359-3.
↑ ^8.0 ^8.1 ^8.2 Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). "Integral Cayley graphs and groups". SIAM Journal on Discrete Mathematics. 28 (2): 685–701. arXiv:1307.6155. doi:10.1137/130925487. S2CID 207067134.
↑ Guo, W.; Lytkina, D.V.; Mazurov, V.D.; Revin, D.O. (2019). "Integral Cayley graphs" (PDF). Algebra and Logic. 58 (4): 297–305. doi:10.1007/s10469-019-09550-2.
↑ Dehn, Max (2012) [1987]. Papers on Group Theory and Topology. Springer-Verlag. ISBN 978-1461291077. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.

बाहरी संबंध

[CGT-1] 1.0 ^1.1 Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.

[Cayley78-2] 2.0 ^2.1 Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.

[3] Theron, Daniel Peter (1988), An extension of the concept of graphically regular representations, Ph.D. thesis, University of Wisconsin, Madison, p. 46, MR 2636729.

[4] Sabidussi, Gert (October 1958). "On a class of fixed-point-free graphs". Proceedings of the American Mathematical Society. 9 (5): 800–4. doi:10.1090/s0002-9939-1958-0097068-7. JSTOR 2033090.

[5] See Theorem 3.7 of Babai, László (1995). "27. Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.). Handbook of Combinatorics. Vol. 1. Elsevier. pp. 1447–1540. ISBN 9780444823465.

[6] White, Arthur T. (1972). "On the genus of a group". Transactions of the American Mathematical Society. 173: 203–214. doi:10.1090/S0002-9947-1972-0317980-2. MR 0317980.

[7] Proposition 1.12 in Lubotzky, Alexander (2012). "Expander graphs in pure and applied mathematics". Bulletin of the American Mathematical Society. 49: 113–162. arXiv:1105.2389. doi:10.1090/S0273-0979-2011-01359-3.

[CIS-8] 8.0 ^8.1 ^8.2 Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). "Integral Cayley graphs and groups". SIAM Journal on Discrete Mathematics. 28 (2): 685–701. arXiv:1307.6155. doi:10.1137/130925487. S2CID 207067134.

[9] Guo, W.; Lytkina, D.V.; Mazurov, V.D.; Revin, D.O. (2019). "Integral Cayley graphs" (PDF). Algebra and Logic. 58 (4): 297–305. doi:10.1007/s10469-019-09550-2.

[10] Dehn, Max (2012) [1987]. Papers on Group Theory and Topology. Springer-Verlag. ISBN 978-1461291077. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{Short description|Graph defined from a mathematical group}}
 [[Image:Cayley graph of F2.svg|right|thumb|दो उत्पादक ए और बी पर [[मुक्त समूह]] का केली ग्राफ]]
-{{Graph families defined by their automorphisms}}
+गणित में, केली ग्राफ, जिसे केली वर्ण ग्राफ, केली आरेख, समूह आरेख या वर्ण समूह के रूप में भी जाना जाता है<ref name = CGT>{{cite book |author-link=Wilhelm Magnus |first1=Wilhelm |last1=Magnus |first2=Abraham |last2=Karrass |author3-link=Baumslag–Solitar group |first3=Donald |last3=Solitar |title=Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations |url=https://books.google.com/books?id=1LW4s1RDRHQC&pg=PR2 |year=2004 |orig-year=1966 |publisher=Courier |isbn=978-0-486-43830-6 }}</ref> एक [[ग्राफ (असतत गणित)|ग्राफ(असतत गणित)]] है जो [[समूह (गणित)|समूह(गणित)]] की अमूर्त संरचना को कूटबद्ध करता है। इसकी परिभाषा केली के प्रमेय([[आर्थर केली]] के नाम पर) द्वारा सुझाई गई है, और समूह के लिए समूह के निर्दिष्ट उत्पादक समुच्चय का उपयोग करती है। यह संयोजी समूह सिद्धांत और [[ज्यामितीय समूह सिद्धांत]] में एक केंद्रीय साधन है। केली ग्राफ़ की संरचना और समरूपता उन्हें विस्तारक ग्राफ़ के वर्गों के निर्माण के लिए विशेष रूप से अच्छे पदान्वेषी बनाती है।
-गणित में, केली ग्राफ, जिसे केली वर्ण ग्राफ, केली आरेख, समूह आरेख या वर्ण समूह के रूप में भी जाना जाता है<ref name = CGT>{{cite book |author-link=Wilhelm Magnus |first1=Wilhelm |last1=Magnus |first2=Abraham |last2=Karrass |author3-link=Baumslag–Solitar group |first3=Donald |last3=Solitar |title=Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations |url=https://books.google.com/books?id=1LW4s1RDRHQC&pg=PR2 |year=2004 |orig-year=1966 |publisher=Courier |isbn=978-0-486-43830-6 }}</ref> एक [[ग्राफ (असतत गणित)]] है जो  [[समूह (गणित)]] की अमूर्त संरचना को कूटबद्ध करता है। इसकी परिभाषा केली के प्रमेय ([[आर्थर केली]] के नाम पर) द्वारा सुझाई गई है, और समूह के लिए समूह के निर्दिष्ट उत्पादक समुच्चय का उपयोग करती है। यह संयोजी समूह सिद्धांत और [[ज्यामितीय समूह सिद्धांत]] में एक केंद्रीय उपकरण है। केली ग्राफ़ की संरचना और समरूपता उन्हें विस्तारक ग्राफ़ के वर्गों के निर्माण के लिए विशेष रूप से अच्छे  पदान्वेषी बनाती है।
 == परिभाषा ==
-माना <math>G</math> एक समूह (गणित)  है और <math>S</math>  <math>G</math>   का  उत्पादक समुच्चय है। केली ग्राफ <math>\Gamma = \Gamma(G,S)</math> एक [[ग्राफ रंगना|ग्राफ वर्णना]]  [[निर्देशित ग्राफ]] है जिसे इस प्रकार बनाया गया है:<ref name=Cayley78>{{cite journal|first1= Arthur |last1=Cayley|journal= American Journal of Mathematics | year=1878|volume=1|issue=2|pages=174–6|title=Desiderata and suggestions: No. 2. The Theory of groups: graphical representation | url=https://babel.hathitrust.org/cgi/pt?id=uc1.$c239465;view=1up;seq=194|jstor=2369306|doi=10.2307/2369306}} In his Collected Mathematical Papers 10: 403–405.</ref>
+माना <math>G</math> एक समूह(गणित) है और <math>S</math> <math>G</math> का उत्पादक समुच्चय है। केली ग्राफ <math>\Gamma = \Gamma(G,S)</math> एक [[ग्राफ रंगना|ग्राफ वर्णना]] [[निर्देशित ग्राफ]] है जिसे इस प्रकार बनाया गया है:<ref name=Cayley78>{{cite journal|first1= Arthur |last1=Cayley|journal= American Journal of Mathematics | year=1878|volume=1|issue=2|pages=174–6|title=Desiderata and suggestions: No. 2. The Theory of groups: graphical representation | url=https://babel.hathitrust.org/cgi/pt?id=uc1.$c239465;view=1up;seq=194|jstor=2369306|doi=10.2307/2369306}} In his Collected Mathematical Papers 10: 403–405.</ref>
-* <math>G</math> के प्रत्येक अवयव <math>g</math> को शीर्ष नियत किया गया है: <math>\Gamma</math> के शीर्ष समुच्चय की पहचान   <math>G</math> से की जाती है।
+* <math>G</math> के प्रत्येक अवयव <math>g</math> को शीर्ष नियत किया गया है: <math>\Gamma</math> के शीर्ष समुच्चय की तत्समक <math>G</math> से की जाती है।
-* <math>S</math> के प्रत्येक अवयव  <math>s</math> को एक वर्ण  <math>c_s</math> दिया गया है।
+* <math>S</math> के प्रत्येक अवयव <math>s</math> को एक वर्ण <math>c_s</math> दिया गया है।
-* प्रत्येक <math>g \in G</math> और <math>s \in S</math> के लिए, <math>g</math> के अनुरूप शीर्ष से वर्ण  <math>c_s</math> का एक निर्देशित किनारा होता है जो <math>gs</math> के अनुरूप होता है।
+* प्रत्येक <math>g \in G</math> और <math>s \in S</math> के लिए, <math>g</math> के अनुरूप शीर्ष से वर्ण <math>c_s</math> का एक निर्देशित किनारा होता है जो <math>gs</math> के अनुरूप होता है।
-प्रत्येक स्रोत के लिए आवश्यक नहीं है कि <math>S</math> समूह उत्पन्न करें। यदि  <math>S</math>  <math>G</math> के लिए उत्पादक समुच्चय नहीं है, तो <math>\Gamma</math> वियोजित(ग्राफ़ सिद्धांत)  हो जाता है और प्रत्येक जुड़ा हुआ घटक <math>S</math> द्वारा उत्पन्न उपसमूह के एक के एक कोसमुच्चय का प्रतिनिधित्व करता है।
+प्रत्येक स्रोत के लिए आवश्यक नहीं है कि <math>S</math> समूह उत्पन्न करें। यदि <math>S</math> <math>G</math> के लिए उत्पादक समुच्चय नहीं है, तो <math>\Gamma</math> वियोजित(ग्राफ़ सिद्धांत) हो जाता है और प्रत्येक संयुक्त घटक <math>S</math> द्वारा उत्पन्न उपसमूह के एक के एक सह समुच्चय का प्रतिनिधित्व करता है।
-यदि  <math>S</math> का एक अवयव <math>s</math> स्वयं का व्युत्क्रम, <math>s = s^{-1}</math> है, तो यह सामान्यतः  एक अप्रत्यक्ष किनारे द्वारा दर्शाया जाता है।
+यदि <math>S</math> का एक अवयव <math>s</math> स्वयं का व्युत्क्रम, <math>s = s^{-1}</math> है, तो यह सामान्यतः एक अप्रत्यक्ष किनारे द्वारा दर्शाया जाता है।
-समुच्चय <math>S</math> को कभी-कभी [[सममित सेट|सममित समुच्चय]]  (यानी <math>S = S^{-1}</math>) माना जाता है और इसमें समूह का पहचान अवयव सम्मिलित नहीं है। इस विषय में, वर्णहीन  केली ग्राफ को एक साधारण अप्रत्यक्ष ग्राफ(असतत गणित) के रूप में दर्शाया जा सकता है।
+समुच्चय <math>S</math> को कभी-कभी [[सममित सेट|सममित समुच्चय]](अर्थात <math>S = S^{-1}</math>) माना जाता है और इसमें समूह का तत्समक अवयव सम्मिलित नहीं है। इस विषय में, वर्णहीन केली ग्राफ को एक साधारण अप्रत्यक्ष ग्राफ(असतत गणित) के रूप में दर्शाया जा सकता है।
-ज्यामितीय समूह सिद्धांत में, समुच्चय <math>S</math> को प्रायः  परिमित माना जाता है जो स्थानीय रूप से परिमित <math>\Gamma</math> से मेल खाता है।
+ज्यामितीय समूह सिद्धांत में, समुच्चय <math>S</math> को प्रायः परिमित माना जाता है जो स्थानीय रूप से परिमित <math>\Gamma</math> से मेल खाता है।
 == उदाहरण ==
-* मान लीजिए कि <math>G=\Z</math> अनंत चक्रीय समूह और समुच्चय <math>S</math> में मानक उत्पादक 1 और इसके व्युत्क्रम (योगात्मक संकेतन में -1) सम्मिलित है; तो केली ग्राफ एक अनंत पथ है।
+* मान लीजिए कि <math>G=\Z</math> अनंत चक्रीय समूह और समुच्चय <math>S</math> में मानक उत्पादक 1 और इसके व्युत्क्रम(योगात्मक संकेतन में -1) सम्मिलित है; तो केली ग्राफ एक अनंत पथ है।
-* इसी प्रकार यदि <math>G=\Z_n</math> क्रम  <math>n</math> का परिमित [[चक्रीय समूह]] है और समुच्चय <math>S</math> में दो अवयव होते हैं,  <math>G</math> का  मानक उत्पादक और इसका व्युत्क्रम, तो केली ग्राफ [[चक्र ग्राफ]] <math>C_n</math>है। अधिक सामान्यतः , परिमित चक्रीय समूहों के केली ग्राफ  यथार्थत परिपत्र ग्राफ होते हैं।
+* इसी प्रकार यदि <math>G=\Z_n</math> क्रम <math>n</math> का परिमित [[चक्रीय समूह]] है और समुच्चय <math>S</math> में दो अवयव होते हैं, <math>G</math> का मानक उत्पादक और इसका व्युत्क्रम, तो केली ग्राफ [[चक्र ग्राफ]] <math>C_n</math> है। अधिक सामान्यतः, परिमित चक्रीय समूहों के केली ग्राफ यथार्थत परिपत्र ग्राफ होते हैं।
-* समूहों के प्रत्यक्ष उत्पाद का केली ग्राफ (उत्पादक समुच्चय के रूप में उत्पादक समुच्चय के  कार्तीय उत्पाद के साथ) संबंधित केली ग्राफ का   कार्तीय उत्पाद है।<ref>{{citation | last = Theron | first = Daniel Peter | mr = 2636729 | page = 46 | publisher = University of Wisconsin, Madison | series = Ph.D. thesis | title = An extension of the concept of graphically regular representations | year = 1988}}.</ref> इस प्रकार  चार अवयवों से युक्त <math>(\pm 1,0),(0,\pm 1)</math> उत्पाद के समुच्चय के साथ एबेलियन समूह   <math>\Z^2</math> का केली ग्राफ समतल <math>\R^2</math>  पर अनंत [[ग्रिड ग्राफ|जाल ग्राफ]] है, जबकि समान उत्पादक के साथ प्रत्यक्ष उत्पाद <math>\Z_n \times \Z_m</math>के लिए केली ग्राफ  एक [[टोरस्र्स]] पर  <math>n\times m</math> परिमित जाल है।
+* समूहों के प्रत्यक्ष उत्पाद का केली ग्राफ(उत्पादक समुच्चय के रूप में उत्पादक समुच्चय के कार्तीय उत्पाद के साथ) संबंधित केली ग्राफ का कार्तीय उत्पाद है।<ref>{{citation | last = Theron | first = Daniel Peter | mr = 2636729 | page = 46 | publisher = University of Wisconsin, Madison | series = Ph.D. thesis | title = An extension of the concept of graphically regular representations | year = 1988}}.</ref> इस प्रकार चार अवयवों से युक्त <math>(\pm 1,0),(0,\pm 1)</math> उत्पाद के समुच्चय के साथ एबेलियन समूह <math>\Z^2</math> का केली ग्राफ समतल <math>\R^2</math> पर अनंत [[ग्रिड ग्राफ|जालक ग्राफ]] है, जबकि समान उत्पादक के साथ प्रत्यक्ष उत्पाद <math>\Z_n \times \Z_m</math>के लिए केली ग्राफ एक [[टोरस्र्स|टोरस्र्]] पर <math>n\times m</math> परिमित जालक है।
 [[Image:Dih 4 Cayley Graph; generators a, b.svg|220px|left|thumb|द्वितल समूह का केली ग्राफ <math>D_4</math> दो उत्पादक ए और बी पर]]
-[[File:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|का केली ग्राफ <math>D_4</math>, दो उत्पादक पर जो दोनों स्व-प्रतिलोम हैं]]दो उत्पादक पर <math>a</math> और <math>b</math> पर  [[डायहेड्रल समूह|द्वितल समूह]]  <math>D_4</math> का केली ग्राफ बाईं ओर दर्शाया गया है। लाल तीर  <math>a</math> के साथ रचना का प्रतिनिधित्व करते हैं। चूँकि <math>b</math>   [[केली टेबल|स्व-व्युत्क्रम(केली तालिका )]] है, नीली रेखाएँ, जो रचना का प्रतिनिधित्व करती हैं <math>b</math> के साथ रचना का प्रतिनिधित्व करती हैं, अप्रत्यक्ष हैं। इसलिए ग्राफ मिश्रित है: इसमें आठ शीर्ष, आठ तीर और चार किनारे हैं। समूह <math>D_4</math> की केली तालिका  [[एक समूह की प्रस्तुति|समूह की प्रस्तुति]]  <math display="block"> \langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle </math>से प्राप्त की जा सकती है।
+[[File:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|<math>D_4</math> का केली ग्राफ, दो उत्पादक पर जो दोनों स्व-व्युत्क्रम हैं]]
-का एक अलग केली ग्राफ <math>D_4</math> दाईं ओर दिखाया गया है। <math>b</math> अभी भी क्षैतिज प्रतिबिंब है और नीली रेखाओं द्वारा दर्शाया गया है, और <math>c</math> एक विकर्ण प्रतिबिंब है और गुलाबी रेखाओं द्वारा दर्शाया गया है। चूंकि दोनों प्रतिबिंब स्व-उलटा हैं, दाईं ओर केली ग्राफ पूरी तरह से अप्रत्यक्ष है। यह ग्राफ प्रस्तुति से मेल खाता है <math display="block"> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle. </math>
+* दो उत्पादक पर <math>a</math> और <math>b</math> पर [[डायहेड्रल समूह|द्वितल समूह]] <math>D_4</math> का केली ग्राफ बाईं ओर दर्शाया गया है। लाल तीर <math>a</math> के साथ रचना का प्रतिनिधित्व करते हैं। चूँकि <math>b</math> [[केली टेबल|स्व-व्युत्क्रम(केली तालिका)]] है, नीली रेखाएँ, जो रचना का प्रतिनिधित्व करती हैं <math>b</math> के साथ रचना का प्रतिनिधित्व करती हैं, अप्रत्यक्ष हैं। इसलिए ग्राफ मिश्रित है: इसमें आठ शीर्ष, आठ तीर और चार किनारे हैं। समूह <math>D_4</math> की केली तालिका [[एक समूह की प्रस्तुति|समूह की प्रस्तुति]]
-* दो उत्पादक पर मुक्त समूह का केली ग्राफ <math>a</math> और <math>b</math> समुच्चय के अनुरूप <math>S = \{a, b, a^{-1}, b^{-1}\}</math> लेख के शीर्ष पर दर्शाया गया है, और <math>e</math> [[पहचान तत्व|पहचान अवयव]] का प्रतिनिधित्व करता है। एक किनारे के साथ दाईं ओर यात्रा करना द्वारा सही गुणन का प्रतिनिधित्व करता है <math>a,</math> किनारे के साथ ऊपर की ओर यात्रा करते समय गुणन से मेल खाती है <math>b.</math> चूंकि मुक्त समूह में समूह की कोई प्रस्तुति नहीं है, केली ग्राफ में कोई [[चक्र (ग्राफ सिद्धांत)]] नहीं है। यह केली ग्राफ एक 4-[[नियमित ग्राफ]] अनंत [[वृक्ष (ग्राफ सिद्धांत)]] है और बनच-टार्स्की विरोधाभास के प्रमाण में एक प्रमुख घटक है।
+<math display="block"> \langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle </math>से प्राप्त की जा सकती है।
-[[Image:HeisenbergCayleyGraph.png|thumb|240px|right|हाइजेनबर्ग समूह के केली ग्राफ का हिस्सा। (वर्ण केवल दृश्य सहायता के लिए है।)]]* [[असतत हाइजेनबर्ग समूह]] का केली ग्राफ  <math display="block">\left\{ \begin{pmatrix}
+<math>D_4</math> का एक भिन्न केली ग्राफ दाईं ओर दिखाया गया है। <math>b</math> अभी भी क्षैतिज प्रतिबिंब है और नीली रेखाओं द्वारा दर्शाया गया है, और <math>c</math> एक विकर्ण प्रतिबिंब है और गुलाबी रेखाओं द्वारा दर्शाया गया है। चूंकि दोनों प्रतिबिंब स्व-व्युत्क्रम हैं, दाईं ओर केली ग्राफ पूर्णता से अप्रत्यक्ष है। यह ग्राफ प्रस्तुति<math display="block"> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle </math>
+से मेल खाता है।
+* लेख के शीर्ष पर दर्शाए गए समुच्चय <math>S = \{a, b, a^{-1}, b^{-1}\}</math> के अनुरूप दो उत्पादक <math>a</math> और <math>b</math> पर मुक्त समूह का केली ग्राफ, और <math>e</math> [[पहचान तत्व|तत्समक अवयव]] का प्रतिनिधित्व करता है। एक किनारे के साथ दाईं ओर प्रगामी <math>a</math> द्वारा सही गुणन का प्रतिनिधित्व करता है जबकि किनारे के साथ ऊपर की ओर प्रगामी <math>b</math> गुणन से मेल खाती है। चूंकि मुक्त समूह का कोई संबंध नहीं है, केली ग्राफ का कोई [[चक्र (ग्राफ सिद्धांत)|चक्र(ग्राफ सिद्धांत)]] नहीं है। यह केली ग्राफ एक 4-[[नियमित ग्राफ]] अनंत [[वृक्ष (ग्राफ सिद्धांत)|वृक्ष(ग्राफ सिद्धांत)]] है और बनच-टार्स्की विरोधाभास के प्रमाण में एक प्रमुख घटक है।
+[[Image:HeisenbergCayleyGraph.png|thumb|240px|right|हाइजेनबर्ग समूह के केली ग्राफ का भाग।(वर्ण मात्र दृश्य सहायता के लिए है।)]]* [[असतत हाइजेनबर्ग समूह]]  <math display="block">\left\{ \begin{pmatrix}
 & x & z\\
 & 1 & y\\
 & 0 & 1\\
-\end{pmatrix},\ x,y,z \in \Z\right\} </math> दाईं ओर दर्शाया गया है। चित्र में प्रयुक्त उत्पादक तीन मैट्रिसेस हैं <math>X, Y, Z</math> प्रविष्टियों के लिए 1, 0, 0 के तीन क्रमपरिवर्तन द्वारा दिया गया <math>x, y, z</math>। वे संबंधों को संतुष्ट करते हैं <math>Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY</math>जिसे तस्वीर से भी समझा जा सकता है। यह एक नाबेलियन समूह है। गैर-कम्यूटेटिव अनंत समूह, और तीन आयामी स्थान होने के बावजूद, केली ग्राफ में चार आयामी [[विकास दर (समूह सिद्धांत)]] है।{{Citation needed|date=September 2020}}
+\end{pmatrix},\ x,y,z \in \Z\right\} </math> के केली ग्राफ को दाईं ओर दर्शाया गया है। चित्र में प्रयुक्त उत्पादक तीन आव्यूह <math>X, Y, Z</math> हैं जो प्रविष्टियों <math>x, y, z</math> के लिए 1, 0, 0 के तीन क्रमपरिवर्तन द्वारा दिए गए हैं। वे संबंधों <math>Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY</math> को संतुष्ट करते हैं जिसे चित्र से भी समझा जा सकता है। यह एक गैर विनिमेय अनंत समूह है,और त्रि-आयामी स्थान होने के अतिरिक्त, केली ग्राफ में चतुर्थ-आयामी [[विकास दर (समूह सिद्धांत)|विकास दर(समूह सिद्धांत)]] है।{{Citation needed|date=September 2020}}
 [[File:Cayley_Q8_quaternion_multiplication_graph.svg|thumb|लिंक ={{filepath:Cayley_Q8_quaternion_multiplication_graph.svg}}s {{red|'''i'''}}, {{green|'''j'''}} और {{blue|'''k'''}}]]
 == विशेषता ==
-समूह <math>G</math> बाएँ गुणन द्वारा स्वयं पर [[समूह क्रिया (गणित)]] (केली की प्रमेय देखें)। की क्रिया के रूप में देखा जा सकता है <math>G</math> इसके केली ग्राफ पर। स्पष्ट रूप से, एक अवयव <math>h\in G</math> एक शीर्ष को मैप करता है <math>g\in V(\Gamma)</math> शिखर तक <math>hg\in V(\Gamma).</math> केली ग्राफ के किनारों का समुच्चय और उनका वर्ण इस क्रिया द्वारा संरक्षित है: किनारा <math>(g,gs)</math> किनारे पर मैप किया गया है <math>(hg,hgs)</math>, दोनों का वर्ण है <math>c_s</math>। किसी समूह की बाईं गुणन क्रिया केवल सकर्मक होती है, विशेष रूप से, केली ग्राफ़ [[शीर्ष-सकर्मक ग्राफ]] | वर्टेक्स-ट्रांसिटिव होते हैं। इसका एक प्रकार का विलोम निम्नलिखित है:
+समूह <math>G</math> बाएँ गुणन द्वारा स्वयं पर [[समूह क्रिया (गणित)|क्रिया(गणित)]] करता है(केली के प्रमेय देखें)। इसे केली ग्राफ पर <math>G</math> की क्रिया के रूप में देखा जा सकता है। स्पष्ट रूप से, एक अवयव <math>h\in G</math> एक शीर्ष <math>g\in V(\Gamma)</math> को शीर्ष <math>hg\in V(\Gamma)</math> पर चित्रित करता है। केली ग्राफ के किनारों का समुच्चय और उनके रंग को इस क्रिया द्वारा संरक्षित किया जाता है: किनारे के <math>(g,gs)</math> को किनारे <math>(hg,hgs)</math> पर चित्रित किया जाता है, दोनों में वर्ण <math>c_s</math> होता है। किसी समूह की बाईं गुणन क्रिया मात्र सकर्मक होती है, विशेष रूप से, केली ग्राफ़ [[शीर्ष-सकर्मक ग्राफ]] होते हैं। इसका एक प्रकार का विलोम निम्नलिखित है:
-{{math theorem | name = Sabidussi's Theorem | math_statement = An (unlabeled and uncolored) directed graph <math>\Gamma</math> is a Cayley graph of a group <math>G</math> if and only if it admits a simply transitive action of <math>G</math> by [[graph automorphism]]s (i.e., preserving the set of directed edges).<ref>{{cite journal|first= Gert |last=Sabidussi|author-link=Gert Sabidussi | journal=[[Proceedings of the American Mathematical Society]] |date=October 1958 |volume=9 |number=5 | pages=800–4 | title=On a class of fixed-point-free graphs |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free }}</ref>}}
+{{math theorem | name = सबिदुस्स की प्रमेय | math_statement = एक (बिना लेबल वाला और बिना वर्ण का) निर्देशित ग्राफ <math>\Gamma</math> एक समूह <math>G</math> का केली ग्राफ है यदि और मात्र यदि यह [[ग्राफ स्वसमाकृतिकता]] (अर्थात, निर्देशित किनारों के समूच्चय को संरक्षित करते हुए) द्वारा <math>G</math> की एक सरल सकर्मक क्रिया को स्वीकार करता है।<ref>{{cite journal|first= Gert |last=Sabidussi|author-link=Gert Sabidussi | journal=[[Proceedings of the American Mathematical Society]] |date=October 1958 |volume=9 |number=5 | pages=800–4 | title=On a class of fixed-point-free graphs |jstor=2033090 |doi=10.1090/s0002-9939-1958-0097068-7|doi-access=free }}</ref>}}
-समूह को पुनर्प्राप्त करने के लिए <math>G</math> और उत्पादक समुच्चय <math>S</math> बिना लेबल वाले निर्देशित ग्राफ़ से <math>\Gamma,</math> एक शीर्ष का चयन करें <math>v_1\in V(\Gamma)</math> और इसे समूह के पहचान अवयव द्वारा लेबल करें। फिर प्रत्येक शीर्ष को लेबल करें  <math>v</math> का <math>\Gamma</math> के अनूठे अवयव द्वारा <math>G</math> वह मानचित्र <math>v_1</math> को <math>v.</math> समुच्चय <math>S</math> के उत्पादक के <math>G</math> कि पैदावार <math>\Gamma</math> केली ग्राफ के रूप में <math>\Gamma(G,S)</math> के बाहरी पड़ोसियों के लेबल का समुच्चय है <math>v_1</math>।
+समूह <math>G</math> और उत्पादक समुच्चय <math>S</math> बिना लेबल वाले निर्देशित ग्राफ़ <math>\Gamma</math> से पुनर्प्राप्त करने के लिए, एक शीर्ष <math>v_1\in V(\Gamma)</math> का चयन करें और इसे समूह के तत्समक अवयव द्वारा लेबल करें। फिर <math>\Gamma</math> के प्रत्येक शीर्ष <math>v</math> को <math>G</math> के अद्वितीय अवयव द्वारा लेबल करें जो <math>v_1</math>से <math>v</math> को चित्रित करता है। <math>G</math> के उत्पादक का समुच्चय <math>S</math> जो केली ग्राफ <math>\Gamma(G,S)</math> के रूप में <math>\Gamma</math> देता है, <math>v_1</math> के बाह्य-निकटवर्ती के लेबल का समुच्चय है।
 == प्राथमिक गुण ==
-* केली ग्राफ <math>\Gamma(G,S)</math> समुच्चय की पसंद पर एक आवश्यक तरीके से निर्भर करता है <math>S</math> उत्पादक की। उदाहरण के लिए, यदि उत्पादक समुच्चय <math>S</math> है <math>k</math> अवयव हैं तो केली ग्राफ के प्रत्येक शीर्ष में है <math>k</math> आने वाला और <math>k</math> निवर्तमान निर्देशित किनारों। एक सममित उत्पादक समुच्चय के विषय में <math>S</math> साथ <math>r</math> अवयवों, केली ग्राफ डिग्री का एक नियमित ग्राफ है <math>r.</math>
+* केली ग्राफ <math>\Gamma(G,S)</math> उत्पादक के समुच्चय <math>S</math> की विकल्प पर एक आवश्यक विधि से निर्भर करता है। उदाहरण के लिए, यदि उत्पादक समुच्चय <math>S</math> में <math>k</math> अवयव हैं तो केली ग्राफ के प्रत्येक शीर्ष में <math>k</math> आगामी और <math>k</math> निर्गामी निर्देशित किनारे हैं। <math>r</math> अवयवों के साथ एक सममित उत्पादक समुच्चय <math>S</math> के विषय में, केली ग्राफ परिमाण <math>r</math> का एक नियमित ग्राफ है।
-* केली ग्राफ में साइकिल (ग्राफ सिद्धांत) (या क्लोज्ड वॉक) के अवयवों के बीच एक समूह की प्रस्तुति को दर्शाता है <math>S.</math> एक समूह के केली परिसर के अधिक विस्तृत निर्माण में, संबंधों के अनुरूप बंद पथ [[बहुभुज]]ों द्वारा भरे जाते हैं। इसका मतलब यह है कि दी गई प्रस्तुति के केली ग्राफ के निर्माण की समस्या <math>\mathcal{P}</math> के लिए [[समूहों के लिए शब्द समस्या]] को हल करने के बराबर है <math>\mathcal{P}</math>।<ref name = CGT/>* यदि  <math>f: G'\to G</math> एक [[विशेषण]] [[समूह समरूपता]] है और उत्पादक समुच्चय के अवयवों की छवियां हैं <math>S'</math> के लिए <math>G'</math> अलग हैं, तो यह ग्राफ के आवरण को प्रेरित करता है <math display="block"> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),</math> कहाँ <math>S = f(S').</math> विशेष रूप से, यदि एक समूह <math>G</math> है <math>k</math> उत्पादक, सभी ऑर्डर 2 से अलग हैं, और समुच्चय <math>S</math> इन उत्पादकों के साथ उनके व्युत्क्रम होते हैं, फिर केली ग्राफ <math>\Gamma(G,S)</math> डिग्री के अनंत नियमित वृक्ष (ग्राफ सिद्धांत) द्वारा कवर किया गया है <math>2k</math> उत्पादक के एक ही समुच्चय पर मुक्त समूह के अनुरूप।
+* केली ग्राफ में चक्र(ग्राफ सिद्धांत)(या संवृत चाल) <math>S</math> के अवयवों के बीच संबंधों को दर्शाता है। एक समूह के केली परिसर के अधिक विस्तृत निर्माण में, संबंधों के अनुरूप संवृत पथ [[बहुभुज|बहुभुजों]] द्वारा "भरे" जाते हैं। इसका तात्पर्य यह है कि दी गई प्रस्तुति <math>\mathcal{P}</math> के केली ग्राफ निर्माण की समस्या <math>\mathcal{P}</math> [[समूहों के लिए शब्द समस्या]] को हल करने के बराबर है।<ref name = CGT/>
-* किसी भी परिमित केली ग्राफ के लिए, जिसे अप्रत्यक्ष माना जाता है, कनेक्टिविटी (ग्राफ सिद्धांत) ग्राफ के [[डिग्री (ग्राफ सिद्धांत)]] के कम से कम 2/3 के बराबर है। यदि उत्पादक समुच्चय न्यूनतम है (किसी भी अवयव को हटाना और यदि मौजूद है, तो उत्पादक समुच्चय से इसका व्युत्क्रम एक समुच्चय छोड़ देता है जो उत्पन्न नहीं कर रहा है), वर्टेक्स कनेक्टिविटी डिग्री के बराबर है। कनेक्टिविटी (ग्राफ सिद्धांत) सभी मामलों में डिग्री के बराबर है।<ref>See Theorem 3.7 of {{cite book | chapter=27. Automorphism groups, isomorphism, reconstruction|title=Handbook of Combinatorics|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link= Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor2-link= Martin Grötschel |editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|first=László|last=Babai|author-link=László Babai| publisher=Elsevier|volume=1 |isbn=9780444823465 |url=https://books.google.com/books?id=5Y9NCwlx63IC |year=1995|chapter-url=http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf}}</ref>
+*यदि <math>f: G'\to G</math> एक [[विशेषण]] [[समूह समरूपता]] है और <math>G'</math> के लिए उत्पादक समुच्चय <math>S'</math> के अवयवों के प्रतिरूप भिन्न हैं, तो यह ग्राफ <math display="block"> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),</math> के आवरण को प्रेरित करता है जहाँ <math>S = f(S')</math>। विशेष रूप से, यदि एक समूह <math>G</math> में <math>k</math> उत्पादक हैं, जो सभी क्रम 2 से भिन्न हैं, और समुच्चय <math>S</math> इन उत्पादकों को उनके व्युत्क्रमों के साथ सम्मिलित किया गया है, तो केली ग्राफ <math>\Gamma(G,S)</math> को <math>2k</math> परिमाण के अनंत नियमित वृक्ष(ग्राफ सिद्धांत) द्वारा आच्छादन किया गया है जो उत्पादक के एक ही समुच्चय पर मुक्त समूह के अनुरूप है।
-* यदि  <math>\rho_{\text{reg}}(g)(x) = gx</math> के साथ वाम-नियमित प्रतिनिधित्व है <math>|G|\times |G|</math> मैट्रिक्स फॉर्म निरूपित <math>[\rho_{\text{reg}}(g)]</math>, का आसन्न मैट्रिक्स <math>\Gamma(G,S)</math> है <math display="inline">A = \sum_{s\in S} [\rho_{\text{reg}}(g)]</math>।
+* किसी भी परिमित केली ग्राफ के लिए, जिसे अप्रत्यक्ष माना जाता है, संयोजकता(ग्राफ सिद्धांत) ग्राफ के [[डिग्री (ग्राफ सिद्धांत)|परिमाण(ग्राफ सिद्धांत)]] के कम से कम 2/3 के बराबर है। यदि उत्पादक समुच्चय न्यूनतम है(किसी भी अवयव को हटाना और यदि स्थित है, तो उत्पादक समुच्चय से इसका व्युत्क्रम एक समुच्चय छोड़ देता है जो उत्पन्न नहीं कर रहा है), शीर्ष संयोजकता परिमाण के बराबर है। संयोजकता(ग्राफ सिद्धांत) सभी विषयों में परिमाण के बराबर है।<ref>See Theorem 3.7 of {{cite book | chapter=27. Automorphism groups, isomorphism, reconstruction|title=Handbook of Combinatorics|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link= Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor2-link= Martin Grötschel |editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|first=László|last=Babai|author-link=László Babai| publisher=Elsevier|volume=1 |isbn=9780444823465 |url=https://books.google.com/books?id=5Y9NCwlx63IC |year=1995|chapter-url=http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf}}</ref>
-* प्रत्येक समूह [[गुणक वर्ण]] <math>\chi</math> समूह का <math>G</math> के आसन्न मैट्रिक्स के एक [[eigenvector]] को प्रेरित करता है <math>\Gamma(G,S)</math>। कब <math>G</math> एबेलियन है, संबंधित [[eigenvalue]] है  <math display="block">\lambda_\chi=\sum_{s\in S}\chi(s),</math> जो रूप धारण कर लेता है <math display="block">\sum_{s\in S} e^{2\pi ijs/|G|}</math> पूर्णांकों के लिए <math>j = 0,1,\dots,|G|-1.</math> विशेष रूप से, तुच्छ चरित्र (जो प्रत्येक अवयव को 1 पर भेज रहा है) का संबंधित ईजेनवेल्यू की डिग्री है <math>\Gamma(G,S)</math>, अर्थात् का क्रम <math>S</math>। यदि  <math>G</math> एक एबेलियन समूह है, बिल्कुल हैं <math>|G|</math> वर्ण, सभी eigenvalues का निर्धारण। ईजेनवेक्टरों के संबंधित ऑर्थोनॉर्मल आधार द्वारा दिया गया है <math>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}.</math> यह ध्यान रखना दिलचस्प है कि यह ईजेनबेसिस उत्पादक समुच्चय से स्वतंत्र है <math>S</math>। {{pb}} अधिक सामान्यतः  सममित उत्पादक समुच्चय के लिए, लें <math>\rho_1,\dots,\rho_k</math> के अलघुकरणीय अभ्यावेदन का एक पूरा समुच्चय <math>G,</math> और जाने <math display="inline">\rho_i(S) = \sum_{s\in S} \rho_i(s)</math> आइगेनवैल्यू समुच्चय के साथ <math>\Lambda_i(S)</math>। फिर के eigenvalues का समुच्चय <math>\Gamma(G,S)</math> बिल्कुल सही है <math display="inline">\bigcup_i \Lambda_i(S),</math> जहां eigenvalue <math>\lambda</math> बहुलता से प्रकट होता है <math>\dim(\rho_i)</math> की प्रत्येक घटना के लिए <math>\lambda</math> के आइगेनवैल्यू के रूप में <math>\rho_i(S).</math>
+* यदि <math>\rho_{\text{reg}}(g)(x) = gx</math> वाम-नियमित प्रतिनिधित्व है जिसमें <math>|G|\times |G|</math> आव्यूह रूप को <math>[\rho_{\text{reg}}(g)]</math> दर्शाया गया है, तो <math>\Gamma(G,S)</math> का आसन्न आव्यूह <math display="inline">A = \sum_{s\in S} [\rho_{\text{reg}}(g)]</math> है।
+* समूह <math>G</math> का प्रत्येक समूह [[गुणक वर्ण]] <math>\chi</math>, <math>\Gamma(G,S)</math> के आसन्न आव्यूह के एक [[eigenvector|आइगेनसदिश]] को प्रेरित करता है । जब <math>G</math> एबेलियन होता है, तो संबद्ध [[eigenvalue|आइगेनमान]] <math display="block">\lambda_\chi=\sum_{s\in S}\chi(s),</math> होता है, जो पूर्णांकों <math>j = 0,1,\dots,|G|-1</math> के लिए<math display="block">\sum_{s\in S} e^{2\pi ijs/|G|}</math>का रूप ले लेता है। विशेष रूप से,सामान्य वर्ण(जो प्रत्येक अवयव को 1 पर भेज रहा है) का संबद्ध आइगेनमान <math>\Gamma(G,S)</math> का परिमाण है, अर्थात् <math>S</math> का क्रम। यदि <math>G</math> एक एबेलियन समूह है, तो यथार्थतः <math>|G|</math> वर्ण हैं, जो सभी आइगेनमानों का निर्धारण करते हैं। आइगेनसदिशों का संगत प्रसामान्य लांबिक विश्लेषण आधार <math>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}</math> द्वारा दिया गया है। यह ध्यान रखना रोचक है कि यह आइगेनआधार उत्पादक समुच्चय <math>S</math> से स्वतंत्र है। अधिक सामान्यतः सममित उत्पादक समुच्चय के लिए, <math>\rho_1,\dots,\rho_k</math> को <math>G</math> के असमानेय निरूपण का एक पूरा समुच्चय लें, और आइगेनमान समुच्चय <math>\Lambda_i(S)</math> के साथ <math display="inline">\rho_i(S) = \sum_{s\in S} \rho_i(s)</math> दें। तब <math>\Gamma(G,S)</math> के आइगेनमानों का समुच्चय ठीक <math display="inline">\bigcup_i \Lambda_i(S)</math> है, जहाँ आइगेनमान <math>\lambda</math> <math>\rho_i(S)</math> के आइगेनमान के रूप में <math>\lambda</math> की प्रत्येक घटना के लिए बहुलता <math>\dim(\rho_i)</math> के साथ प्रकट होता है।
-== स्क्रीमर कोसमुच्चय ग्राफ ==
+== स्च्रिएर सह समुच्चय ग्राफ ==
-{{main article|Schreier coset graph}}
+{{main article|स्च्रिएर सह समुच्चय ग्राफ}}
-यदि एक, इसके बजाय, एक निश्चित उपसमूह के सही सहसमुच्चय होने के लिए कोने लेता है <math>H,</math> एक संबंधित निर्माण, [[श्रेयर कॉस्टेट ग्राफ]] प्राप्त करता है, जो [[कोसेट गणना|कोसमुच्चय गणना]] या टोड-कॉक्समुच्चयर प्रक्रिया के आधार पर है।
+यदि कोई, इसके अतिरिक्त, एक निश्चित उपसमूह <math>H</math> के सही सहसमुच्चय होने के लिए निश्चित लेता है एक संबंधित निर्माण, [[श्रेयर कॉस्टेट ग्राफ|स्च्रिएर सह समुच्चय ग्राफ]] प्राप्त करता है, जो [[कोसेट गणना|सह समुच्चय गणना]] या टोड-कॉक्समुच्चयर प्रक्रिया के आधार पर होता है।
 == समूह सिद्धांत से संबंध ==
-समूह की संरचना के बारे में ज्ञान ग्राफ के आसन्न मैट्रिक्स का अध्ययन करके और विशेष रूप से [[वर्णक्रमीय ग्राफ सिद्धांत]] के प्रमेयों को लागू करके प्राप्त किया जा सकता है। इसके विपरीत, सममित उत्पादक समुच्चय के लिए, वर्णक्रमीय और प्रतिनिधित्व सिद्धांत <math>\Gamma(G,S)</math> सीधे एक साथ बंधे हैं: लो <math>\rho_1,\dots,\rho_k</math> के अलघुकरणीय अभ्यावेदन का एक पूरा समुच्चय <math>G,</math> और जाने <math display="inline">\rho_i(S) = \sum_{s \in S} \rho_i(s)</math> आइगेनवैल्यू के साथ <math>\Lambda_i(S)</math>। फिर के eigenvalues का समुच्चय <math>\Gamma(G,S)</math> बिल्कुल सही है <math display="inline">\bigcup_i \Lambda_i(S),</math> जहां eigenvalue <math>\lambda</math> बहुलता से प्रकट होता है <math>\dim(\rho_i)</math> की प्रत्येक घटना के लिए <math>\lambda</math> के आइगेनवैल्यू के रूप में <math>\rho_i(S).</math>
+समूह की संरचना के विषय में ज्ञान ग्राफ के आसन्न आव्यूह का अध्ययन करके और विशेष रूप से [[वर्णक्रमीय ग्राफ सिद्धांत]] के प्रमेयों को लागू करके प्राप्त किया जा सकता है। इसके विपरीत, सममित उत्पादक समुच्चय के लिए, <math>\Gamma(G,S)</math> वर्णक्रमीय और प्रतिनिधित्व सिद्धांत सीधे एक साथ बंधे होते हैं: <math>\rho_1,\dots,\rho_k</math> को <math>G</math> के असमानेय प्रस्तुतियों का एक पूरा समुच्चय लें, और <math display="inline">\rho_i(S) = \sum_{s \in S} \rho_i(s)</math> को आइगेनमान <math>\Lambda_i(S)</math> के साथ दें। तब <math>\Gamma(G,S)</math> के आइगेनमानों का समुच्चय ठीक <math display="inline">\bigcup_i \Lambda_i(S)</math> होता है, जहाँ आइगेनमान <math>\lambda</math> <math>\rho_i(S)</math> के आइगेनमान के रूप में <math>\lambda</math> की प्रत्येक घटना के लिए बहुलता <math>\dim(\rho_i)</math> के साथ प्रकट होता है।
-किसी समूह का [[जीनस (गणित)]] उस समूह के किसी भी केली ग्राफ के लिए न्यूनतम जीनस है।<ref>{{cite journal | last=White |first=Arthur T. |title=On the genus of a group |journal=[[Transactions of the American Mathematical Society]] |volume=173 |year=1972 |pages=203–214 |mr=0317980 |doi=10.1090/S0002-9947-1972-0317980-2|doi-access=free }}</ref>
+किसी समूह का [[जीनस (गणित)|जीनस(गणित)]] उस समूह के किसी भी केली ग्राफ के लिए न्यूनतम जीनस है।<ref>{{cite journal | last=White |first=Arthur T. |title=On the genus of a group |journal=[[Transactions of the American Mathematical Society]] |volume=173 |year=1972 |pages=203–214 |mr=0317980 |doi=10.1090/S0002-9947-1972-0317980-2|doi-access=free }}</ref>
 === ज्यामितीय समूह सिद्धांत ===
-अनंत समूहों के लिए, केली ग्राफ की मोटे संरचना ज्यामितीय समूह सिद्धांत के लिए मौलिक है। एक अंतिम रूप से उत्पन्न समूह के लिए, यह उत्पादक के परिमित समुच्चय की पसंद से स्वतंत्र है, इसलिए समूह की एक आंतरिक संपत्ति है। यह केवल अनंत समूहों के लिए दिलचस्प है: प्रत्येक परिमित समूह मोटे तौर पर एक बिंदु (या तुच्छ समूह) के बराबर होता है, क्योंकि कोई भी पूरे समूह को उत्पादक के परिमित समुच्चय के रूप में चुन सकता है।
+अनंत समूहों के लिए, केली ग्राफ की स्थूल संरचना ज्यामितीय समूह सिद्धांत के लिए मौलिक है। अंतिम रूप से उत्पन्न समूह के लिए, यह उत्पादक के परिमित समुच्चय के विकल्प से स्वतंत्र है, इसलिए समूह का एक आंतरिक गुण है। यह मात्र अनंत समूहों के लिए रोचक है: प्रत्येक परिमित समूह स्थूल रूप में एक बिंदु(या सामान्य समूह) के बराबर होता है, क्योंकि कोई भी पूर्ण समूह को उत्पादक के परिमित समुच्चय के रूप में चुन सकता है।
-औपचारिक रूप से, उत्पादक के दिए गए विकल्प के लिए, एक [[शब्द मीट्रिक]] (केली ग्राफ पर प्राकृतिक दूरी) होता है, जो एक [[मीट्रिक स्थान]] निर्धारित करता है। इस स्थान का मोटा तुल्यता वर्ग समूह का एक अपरिवर्तनीय है।
+औपचारिक रूप से, उत्पादक के दिए गए विकल्प के लिए, एक [[शब्द मीट्रिक|शब्द मापीय]](केली ग्राफ पर प्राकृतिक दूरी) होता है, जो एक [[मीट्रिक स्थान|मापीय स्थान]] निर्धारित करता है। इस स्थान का स्थूल तुल्यता वर्ग समूह का एक अपरिवर्तनीय है।
 == विस्तार गुण ==
-कब <math>S = S^{-1}</math>, केली ग्राफ <math>\Gamma(G,S)</math> है <math>|S|</math>-नियमित, इसलिए ग्राफ के [[विस्तारक ग्राफ]] का विश्लेषण करने के लिए वर्णक्रमीय तकनीकों का उपयोग किया जा सकता है। विशेष रूप से एबेलियन समूहों के लिए, केली ग्राफ के ईगेनवेल्यू अधिक आसानी से गणना योग्य हैं और इनके द्वारा दिए गए हैं <math display="inline">\lambda_\chi = \sum_{s\in S} \chi(s)</math> शीर्ष eigenvalue के बराबर <math>|S|</math>, इसलिए हम वर्णक्रमीय अंतर का उपयोग करके किनारे के विस्तार अनुपात को सीमित करने के लिए स्पेक्ट्रल ग्राफ सिद्धांत#चीजर असमानता|चीजर की असमानता का उपयोग कर सकते हैं।
+जब <math>S = S^{-1}</math>, केली ग्राफ <math>\Gamma(G,S)</math> <math>|S|</math>-नियमित है, इसलिए ग्राफ के [[विस्तारक ग्राफ]] का विश्लेषण करने के लिए वर्णक्रमीय तकनीकों का उपयोग किया जा सकता है। विशेष रूप से एबेलियन समूहों के लिए, केली ग्राफ के आइगेनमान अधिक आसानी से संगणनीय हैं और <math display="inline">\lambda_\chi = \sum_{s\in S} \chi(s)</math> द्वारा <math>|S|</math> के बराबर शीर्ष आइगेनमान के साथ दिए गए हैं, इसलिए हम वर्णक्रमीय अंतर का उपयोग करके किनारे के विस्तार अनुपात को सीमित करने के लिए चीजर की असमानता का उपयोग कर सकते हैं।
-कज़्दान संपत्ति (टी) के रूप में, इस तरह के विस्तारित केली ग्राफ़ के निर्माण के लिए प्रतिनिधित्व सिद्धांत का उपयोग किया जा सकता है। निम्नलिखित कथन धारण करता है:<ref>Proposition 1.12 in {{cite journal|last=Lubotzky|first=Alexander | authorlink=Alexander Lubotzky |title=Expander graphs in pure and applied mathematics | journal=[[Bulletin of the American Mathematical Society]] |year=2012 |volume=49 |pages=113–162  |arxiv=1105.2389| doi=10.1090/S0273-0979-2011-01359-3 |doi-access=free}}</ref>
+कज़्दान गुण(टी) के रूप में, इस प्रकार के विस्तारित केली ग्राफ़ के निर्माण के लिए प्रतिनिधित्व सिद्धांत का उपयोग किया जा सकता है। निम्नलिखित कथन धारण करता है:<ref>Proposition 1.12 in {{cite journal|last=Lubotzky|first=Alexander | authorlink=Alexander Lubotzky |title=Expander graphs in pure and applied mathematics | journal=[[Bulletin of the American Mathematical Society]] |year=2012 |volume=49 |pages=113–162  |arxiv=1105.2389| doi=10.1090/S0273-0979-2011-01359-3 |doi-access=free}}</ref>
-{{block indent | em = 1.6 | text = ''If a discrete group <math>G</math> has Kazhdan's property (T), and <math>S</math> is a finite, symmetric generating set of <math>G</math>, then there exists a constant <math>c > 0</math> depending only on <math>G, S</math> such that for any finite quotient <math>Q</math> of <math>G</math> the Cayley graph of <math>Q</math> with respect to the image of <math>S</math> is a <math>c</math>-expander. ''}}
+{{block indent | em = 1.6 | text = ''यदि एक असतत समूह <math>G</math> के समीप काज़दान गुण (T) है, और <math>S</math>,
-उदाहरण के लिए समूह <math>G = \mathrm{SL}_3(\Z)</math> संपत्ति (टी) है और [[प्राथमिक मैट्रिक्स]] द्वारा उत्पन्न होती है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देती है।
+ <math>G</math> का एक परिमित, सममित उत्पादक समूच्चय  है, तो मात्र <math>G, S</math> पर निर्भर करते हुए एक निरंतर   <math>c > 0</math> स्थित है, जैसे कि <math>G</math> के किसी भी परिमित भागफल <math>Q</math> केली ग्राफ के लिए <math>S</math> की प्रतिरूप के संबंध में <math>Q</math> का एक <math>c</math>-विस्तारक है।''}}
+उदाहरण के लिए समूह <math>G = \mathrm{SL}_3(\Z)</math> के गुण(T) है और [[प्राथमिक मैट्रिक्स|प्राथमिक आव्यूह]] द्वारा उत्पन्न होता है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देता है।
 == अभिन्न वर्गीकरण ==
-एक अभिन्न ग्राफ वह होता है जिसके आइगेनवैल्यू सभी पूर्णांक होते हैं। जबकि इंटीग्रल ग्राफ़ का पूर्ण वर्गीकरण एक खुली समस्या है, कुछ समूहों के केली ग्राफ़ हमेशा इंटीग्रल होते हैं।
+अभिन्न ग्राफ वह होता है जिसके आइगेनमान सभी पूर्णांक होते हैं। जबकि अभिन्न ग्राफ़ का पूर्ण वर्गीकरण एक विवृत समस्या है, कुछ समूहों के केली ग्राफ़ सदैव अभिन्न होते हैं। केली ग्राफ के वर्णक्रम के पिछले गुणों का वर्णन का उपयोग करते हुए, ध्यान दें कि <math>\Gamma(G,S)</math> अभिन्न है यदि <math>\rho(S)</math> के आइगेनमानों <math>G</math> के प्रत्येक प्रतिनिधित्व <math>\rho</math> के लिए अभिन्न हैं।
-केली ग्राफ के स्पेक्ट्रम के पिछले लक्षण वर्णन का उपयोग करते हुए, ध्यान दें <math>\Gamma(G,S)</math> अभिन्न है यदि  के eigenvalues <math>\rho(S)</math> प्रत्येक प्रतिनिधित्व के लिए अभिन्न हैं <math>\rho</math> का <math>G</math>।
 === केली अभिन्न सरल समूह ===
-एक समूह <math>G</math> केली इंटीग्रल सिंपल (CIS) है यदि  कनेक्टेड केली ग्राफ <math>\Gamma(G,S)</math> सममित उत्पादक समुच्चय होने पर बिल्कुल अभिन्न है <math>S</math> के एक उपसमूह का पूरक है <math>G</math>। अहमदी, बेल और मोहर के परिणाम से पता चलता है कि सभी सीआईएस समूह आइसोमॉर्फिक हैं <math>\mathbb{Z}/p\mathbb{Z}, \mathbb{Z}/p^2\mathbb{Z}</math>, या <math>\mathbb{Z}_2 \times \mathbb{Z}_2</math> प्राइम्स के लिए <math>p</math>।<ref name="CIS">{{cite journal|last1=Ahmady|first1=Azhvan |last2=Bell|first2=Jason|last3=Mohar|first3=Bojan|authorlink3=Bojan Mohar|title=Integral Cayley graphs and groups|journal=[[SIAM Journal on Discrete Mathematics]]|volume=28|issue=2|pages=685–701|year=2014|arxiv=1307.6155 |doi=10.1137/130925487 |s2cid=207067134}}</ref> यह महत्वपूर्ण है कि <math>S</math>  यथार्थत पूरे समूह को उत्पन्न करता है <math>G</math> केली ग्राफ को जोड़ने के लिए। (यदि  <math>S</math> उत्पन्न नहीं करता <math>G</math>, केली ग्राफ अभी भी अभिन्न हो सकता है, लेकिन इसका पूरक है <math>S</math> जरूरी नहीं कि एक उपसमूह हो।)
+एक समूह <math>G</math> केली अभिन्न सरल(CIS) है यदि संयुक्त केली ग्राफ <math>\Gamma(G,S)</math> अभिन्न है जब सममित उत्पादक समुच्चय <math>S</math>, <math>G</math> के एक उपसमूह का पूरक है। अहमदी, बेल और मोहर के परिणाम से ज्ञात होता है कि सभी सीआईएस समूह अभाज्य <math>p</math> के लिए <math>\mathbb{Z}/p\mathbb{Z}, \mathbb{Z}/p^2\mathbb{Z}</math>, या <math>\mathbb{Z}_2 \times \mathbb{Z}_2</math> समरूपी हैं ।<ref name="CIS">{{cite journal|last1=Ahmady|first1=Azhvan |last2=Bell|first2=Jason|last3=Mohar|first3=Bojan|authorlink3=Bojan Mohar|title=Integral Cayley graphs and groups|journal=[[SIAM Journal on Discrete Mathematics]]|volume=28|issue=2|pages=685–701|year=2014|arxiv=1307.6155 |doi=10.1137/130925487 |s2cid=207067134}}</ref> यह महत्वपूर्ण है कि केली ग्राफ को जोड़ने के लिए <math>S</math> यथार्थत पूर्ण समूह <math>G</math> को उत्पन्न करता है।(यदि <math>S</math> <math>G</math> उत्पन्न नहीं करता है, तो केली ग्राफ अभी भी अभिन्न हो सकता है, परन्तु <math>S</math> का पूरक अनिवार्य रूप से एक उपसमूह नहीं है।)
-के उदाहरण में <math>G=\mathbb{Z}/5\mathbb{Z}</math>, सममित उत्पादक समुच्चय (ग्राफ़ समरूपता तक) हैं
+<math>G=\mathbb{Z}/5\mathbb{Z}</math> के उदाहरण में, सममित उत्पादक समुच्चय(ग्राफ़ समरूपता तक) हैं
-*<math>S = \{1,4\}</math>: <math>\Gamma(G,S)</math> एक है <math>5</math>- आइगेनवैल्यू के साथ साइकिल <math>2, \tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}</math>
+*<math>S = \{1,4\}</math>: <math>\Gamma(G,S)</math> एक <math>5</math>-चक्र है जिसका आइगेनमान <math>2, \tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}</math> है
-*<math>S = \{1,2,3,4\}</math>: <math>\Gamma(G,S)</math> है <math>K_5</math> आइगेनवैल्यू के साथ <math>4, -1,-1,-1,-1</math>
+*<math>S = \{1,2,3,4\}</math>: <math>\Gamma(G,S)</math> <math>K_5</math> है जिसका आइगेनमान <math>4, -1,-1,-1,-1</math> है
-का एकमात्र उपसमूह <math>\mathbb{Z}/5\mathbb{Z}</math> संपूर्ण समूह और तुच्छ समूह हैं, और केवल सममित उत्पादक समुच्चय हैं <math>S</math> जो एक अभिन्न ग्राफ का उत्पादन करता है वह तुच्छ समूह का पूरक है। इसलिए <math>\mathbb{Z}/5\mathbb{Z}</math> एक सीआईएस समूह होना चाहिए।
+<math>\mathbb{Z}/5\mathbb{Z}</math> का एकमात्र उपसमूह संपूर्ण समूह और सामान्य समूह हैं, और एकमात्र सममित उत्पादक समुच्चय <math>S</math> हैं जो एक अभिन्न ग्राफ का उत्पादन करता है वह सामान्य समूह का पूरक है। इसलिए <math>\mathbb{Z}/5\mathbb{Z}</math> एक सीआईएस समूह होना चाहिए।
-पूर्ण CIS वर्गीकरण का प्रमाण इस तथ्य का उपयोग करता है कि CIS समूह का प्रत्येक उपसमूह और होमोमोर्फिक छवि भी CIS समूह है।<ref name="CIS" />
+पूर्ण सीआईएस वर्गीकरण का प्रमाण इस तथ्य का उपयोग करता है कि सीआईएस समूह का प्रत्येक उपसमूह और समरूपी प्रतिरूप भी सीआईएस समूह है।<ref name="CIS" />
 === केली अभिन्न समूह ===
-केली इंटीग्रल ग्रुप की एक थोड़ी अलग धारणा है <math>G</math>, जिसमें प्रत्येक सममित उपसमुच्चय <math>S</math> एक अभिन्न ग्राफ बनाता है <math>\Gamma(G,S)</math>। ध्यान दें कि <math>S</math> अब पूरे समूह को उत्पन्न नहीं करना है।
+केली अभिन्न समूह <math>G</math> की एक किंचित् भिन्न धारणा है, जिसमें प्रत्येक सममित उपसमुच्चय <math>S</math> एक अभिन्न ग्राफ <math>\Gamma(G,S)</math> बनाता है। ध्यान दें कि <math>S</math> अब पूर्ण समूह को उत्पन्न नहीं करना है।
+केली अभिन्न समूहों की पूरी सूची <math>\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</math> द्वारा दी गई है, और क्रम <math>12</math> के द्विचक्रीय समूह, जहाँ <math>m,n\in \mathbb{Z}_{\ge 0}</math> और <math>Q_8</math> चतुष्कोणीय समूह है।<ref name="CIS"/> प्रमाण केली अभिन्न समूहों के दो महत्वपूर्ण गुणों पर निर्भर करता है:
+* केली अभिन्न समूह के उपसमूह और समरूपी प्रतिरूप भी केली अभिन्न समूह हैं।
+* एक समूह केली अभिन्न है यदि समूह का प्रत्येक संयुक्त केली ग्राफ भी अभिन्न है।
-केली अभिन्न समूहों की पूरी सूची किसके द्वारा दी गई है <math>\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</math>, और ऑर्डर का डायसाइक्लिक समूह <math>12</math>, कहाँ <math>m,n\in \mathbb{Z}_{\ge 0}</math> और <math>Q_8</math> चतुष्कोणीय समूह है।<ref name="CIS"/>प्रमाण केली अभिन्न समूहों के दो महत्वपूर्ण गुणों पर निर्भर करता है:
+=== सामान्य और ऑयतर उत्पादक समुच्चय ===
-* केली इंटीग्रल ग्रुप के सबग्रुप और होमोमोर्फिक इमेज भी केली इंटीग्रल ग्रुप हैं।
-* एक समूह केली इंटीग्रल है यदि  समूह का प्रत्येक जुड़ा केली ग्राफ भी इंटीग्रल है।
-=== सामान्य और ऑयलेरियन उत्पादक समुच्चय ===
+एक सामान्य समूह <math>G</math> दिया गया है, एक उपसमुच्चय <math>S \subseteq G</math> सामान्य है यदि <math>S</math> <math>G</math> के अवयवों(एक सामान्य उपसमूह की धारणा को सामान्य बनाने) के [[संयुग्मन (समूह सिद्धांत)|संयुग्मन(समूह सिद्धांत)]] के अंतर्गत संवृत है, और <math>S</math> ऑयतर है यदि प्रत्येक <math>s \in S</math> के लिए, चक्रीय समूह उत्पन्न करने वाले अवयवों का समुच्चय <math>\langle s \rangle</math> भी <math>S</math> में निहित है। गुओ, लिटकिना, माजुरोव और रेवेन द्वारा 2019 का परिणाम सिद्ध करता है कि केली ग्राफ <math>\Gamma(G,S)</math> किसी भी ऑयतर प्रसामान्य उपसमुच्चय <math>S \subseteq G</math> के लिए अभिन्न है, जो विशुद्ध रूप से प्रतिनिधित्व सैद्धांतिक तकनीकों का उपयोग करता है।<ref>{{cite journal| last1=Guo|first1=W.|last2=Lytkina|first2=D.V.|last3=Mazurov|first3=V.D.|last4=Revin|first4=D.O.|title=Integral Cayley graphs|journal=Algebra and Logic | year=2019|volume=58 |issue=4 |pages=297–305 |doi=10.1007/s10469-019-09550-2|url=https://link.springer.com/content/pdf/10.1007/s10469-019-09550-2.pdf}}</ref>
-एक सामान्य समूह दिया <math>G</math>, उपसमुच्चय <math>S \subseteq G</math> सामान्य है यदि  <math>S</math> के अवयवों द्वारा [[संयुग्मन (समूह सिद्धांत)]] के तहत बंद है <math>G</math> (एक सामान्य उपसमूह की धारणा को सामान्य बनाना), और <math>S</math> यदि प्रत्येक के लिए ऑयलरीय है <math>s \in S</math>, चक्रीय समूह उत्पन्न करने वाले अवयवों का समूह <math>\langle s \rangle</math> में भी निहित है <math>S</math>।
+इस परिणाम का प्रमाण अपेक्षाकृत कम है: <math>S</math> को एक ऑयतर प्रसामान्य उपसमुच्चय दिया गया है, <math>x_1,\dots, x_t\in G</math> युग्‍मानूसार असंयुग्मी का चयन करें ताकि <math>S</math> संयुग्मी वर्गों <math>\operatorname{Cl}(x_i)</math> का संयोजन हो। फिर एक केली ग्राफ के वर्णक्रम के गुणों का वर्णन का उपयोग करके, <math>\Gamma(G,S)</math> के आइगेनमान दिखा सकते हैं <math display="inline">\left\{\lambda_\chi = \sum_{i=1}^t \frac{\chi(x_i) \left|\operatorname{Cl}(x_i)\right|}{\chi(1)}\right\}</math> <math>G</math> असमानेय वर्ण <math>\chi</math> पर लिया गया है। इस समुच्चय में प्रत्येक आइगेनमान <math>\lambda_\chi</math> का एक अवयव होना चाहिए <math>\zeta</math> के लिए <math>\mathbb{Q}(\zeta)</math> एक मौलिक <math>m^{th}</math> एकात्मकता की घात(जहाँ <math>m</math> को प्रत्येक <math>x_i</math> की कोटि से विभाज्य होना चाहिए)। क्योंकि आइगेनमान बीजगणितीय पूर्णांक हैं, यह दर्शाने के लिए कि वे अभिन्न हैं, यह दर्शाना पर्याप्त है कि वे परिमेय हैं, और यह दर्शाने के लिए पर्याप्त है कि <math>\mathbb{Q}(\zeta)</math> के किसी भी स्वसमाकृतिकता <math>\sigma</math> के अंतर्गत <math>\lambda_\chi</math> निश्चित है। कुछ <math>k</math> अपेक्षाकृत अभाज्य होना चाहिए <math>m</math> ऐसा है कि सभी <math>i</math> के लिए <math>\sigma(\chi(x_i)) = \chi(x_i^k)</math>, और क्योंकि <math>S</math> ऑयतर और सामान्य दोनों है, <math>\sigma(\chi(x_i)) = \chi(x_j)</math> कुछ <math>j</math> के लिए। <math>x\mapsto x^k</math> भेजना संयुग्मन वर्गों को अलग करता है, इसलिए <math>\operatorname{Cl}(x_i)</math> और <math>\operatorname{Cl}(x_j)</math> का आकार समान है और <math>\sigma</math> मात्र <math>\lambda_\chi</math> के योग में शर्तों की अनुमति देता है। इसलिए <math>\lambda_\chi</math> <math>\mathbb{Q}(\zeta)</math> के सभी स्वसमाकृतिकता के लिए निश्चित है, इसलिए <math>\lambda_\chi</math> परिमेय है और इस प्रकार अभिन्न है।
-गुओ, लिटकिना, माजुरोव और रेविन द्वारा 2019 का परिणाम साबित करता है कि केली ग्राफ <math>\Gamma(G,S)</math> किसी भी ऑयलरीय प्रसामान्य उपसमुच्चय के लिए अभिन्न है <math>S \subseteq G</math>, विशुद्ध रूप से प्रतिनिधित्व सैद्धांतिक तकनीकों का उपयोग करते हुए।<ref>{{cite journal| last1=Guo|first1=W.|last2=Lytkina|first2=D.V.|last3=Mazurov|first3=V.D.|last4=Revin|first4=D.O.|title=Integral Cayley graphs|journal=Algebra and Logic | year=2019|volume=58 |issue=4 |pages=297–305 |doi=10.1007/s10469-019-09550-2|url=https://link.springer.com/content/pdf/10.1007/s10469-019-09550-2.pdf}}</ref>
-इस परिणाम का प्रमाण अपेक्षाकृत कम है: दिया गया <math>S</math> एक ऑयलरीय प्रसामान्य उपसमुच्चय, चयन करें <math>x_1,\dots, x_t\in G</math> जोड़ीदार असंयुग्मी ताकि <math>S</math> संयुग्मी वर्गों का संघ है <math>\operatorname{Cl}(x_i)</math>। फिर एक केली ग्राफ के स्पेक्ट्रम के लक्षण वर्णन का उपयोग करके, कोई आइगेनवेल्यू दिखा सकता है <math>\Gamma(G,S)</math> द्वारा दिए गए हैं <math display="inline">\left\{\lambda_\chi = \sum_{i=1}^t \frac{\chi(x_i) \left|\operatorname{Cl}(x_i)\right|}{\chi(1)}\right\}</math> अप्रासंगिक पात्रों पर कब्जा कर लिया <math>\chi</math> का <math>G</math>। प्रत्येक आइगेनवैल्यू <math>\lambda_\chi</math> इस समुच्चय में का एक अवयव होना चाहिए <math>\mathbb{Q}(\zeta)</math> के लिए <math>\zeta</math> एक आदिम <math>m^{th}</math> एकता की जड़ (जहाँ <math>m</math> प्रत्येक के आदेश से विभाज्य होना चाहिए <math>x_i</math>)। क्योंकि आइगेनमान बीजगणितीय पूर्णांक हैं, यह दर्शाने के लिए कि वे अभिन्न हैं, यह दर्शाना पर्याप्त है कि वे परिमेय हैं, और यह दर्शाने के लिए पर्याप्त है <math>\lambda_\chi</math> किसी भी ऑटोमोर्फिज्म के तहत तय किया गया है <math>\sigma</math> का <math>\mathbb{Q}(\zeta)</math>। कुछ होना चाहिए <math>k</math> अपेक्षाकृत प्रधान <math>m</math> ऐसा है कि <math>\sigma(\chi(x_i)) = \chi(x_i^k)</math> सभी के लिए <math>i</math>, और क्योंकि <math>S</math> ऑयलरीय और सामान्य दोनों है, <math>\sigma(\chi(x_i)) = \chi(x_j)</math> कुछ के लिए <math>j</math>। भेजना <math>x\mapsto x^k</math> bijects संयुग्मी वर्ग, इसलिए <math>\operatorname{Cl}(x_i)</math> और <math>\operatorname{Cl}(x_j)</math> एक ही आकार और है <math>\sigma</math> केवल के योग में शर्तों की अनुमति देता है <math>\lambda_\chi</math>। इसलिए <math>\lambda_\chi</math> के सभी ऑटोमोर्फिज्म के लिए तय है <math>\mathbb{Q}(\zeta)</math>, इसलिए <math>\lambda_\chi</math> तर्कसंगत है और इस प्रकार अभिन्न है।
-नतीजतन, यदि  <math>G=A_n</math> वैकल्पिक समूह है और <math>S</math> द्वारा दिए गए क्रमपरिवर्तन का एक समुच्चय है <math>\{ (12i)^{\pm 1} \}</math>, फिर केली ग्राफ <math>\Gamma(A_n,S)</math> अभिन्न है। (इससे [[कौरोव्का नोटबुक]] की पहले से खुली हुई समस्या हल हो गई।) इसके अलावा जब <math>G = S_n</math> सममित समूह है और <math>S</math> या तो सभी ट्रांसपोज़िशन का समुच्चय है या किसी विशेष अवयव, केली ग्राफ़ को सम्मिलित  करने वाले ट्रांसपोज़िशन का समुच्चय है <math>\Gamma(G,S)</math> अभिन्न भी है।
+परिणामस्वरूप, यदि <math>G=A_n</math> एक प्रत्यावर्ती समूह है और <math>S</math>, <math>\{ (12i)^{\pm 1} \}</math> द्वारा दिए गए क्रमपरिवर्तनों का एक समुच्चय है, फिर केली ग्राफ <math>\Gamma(A_n,S)</math> अभिन्न है।(इससे [[कौरोव्का नोटबुक|कौरोव्का स्मरण पुस्तक]] की पूर्व से विवृत समस्या हल हो गई।) इसके अतिरिक्त जब <math>G = S_n</math> सममित समूह होता है और <math>S</math> या तो सभी परिवर्तनों का समुच्चय होता है या किसी विशेष अवयव से जुड़े परिवर्तनों का समुच्चय होता है, केली ग्राफ़ <math>\Gamma(G,S)</math> भी अभिन्न है।
 == इतिहास ==
-में आर्थर केली द्वारा परिमित समूहों के लिए केली ग्राफ पर पहली बार विचार किया गया था।<ref name=Cayley78/>[[मैक्स डेहन]] ने 1909-10 के समूह सिद्धांत पर अपने अप्रकाशित व्याख्यान में ग्रुपेनबिल्ड (समूह आरेख) नाम के तहत केली ग्राफ को फिर से प्रस्तुत किया, जिसने आज के ज्यामितीय समूह सिद्धांत को जन्म दिया। उनका सबसे महत्वपूर्ण अनुप्रयोग जीनस ≥ 2 के साथ भूतल (टोपोलॉजी) के [[मौलिक समूह]] के लिए [[शब्द समस्या (गणित)]] का समाधान था, जो सतह के अनुबंध पर एक बिंदु पर बंद घटता तय करने की सामयिक समस्या के बराबर है।<ref>{{cite book |last=Dehn |first=Max |author-link=Max Dehn| title=Papers on Group Theory and Topology |publisher=Springer-Verlag |year=2012 |orig-year=1987 |isbn=978-1461291077 }} Translated from the German and with introductions and an appendix by [[John Stillwell]], and with an appendix by [[Otto Schreier]].</ref>
+में आर्थर केली द्वारा परिमित समूहों के लिए केली ग्राफ पर पहली बार विचार किया गया था।<ref name=Cayley78/> [[मैक्स डेहन]] ने 1909-10 के समूह सिद्धांत पर अपने अप्रकाशित व्याख्यान में ग्रुपेनबिल्ड(समूह आरेख) नाम के अंतर्गत केली ग्राफ को फिर से प्रस्तुत किया, जिसने आज के ज्यामितीय समूह सिद्धांत को जन्म दिया। उनका सबसे महत्वपूर्ण अनुप्रयोग जीनस ≥ 2 के साथ भूतल(टोपोलॉजी) के [[मौलिक समूह]] के लिए [[शब्द समस्या (गणित)|शब्द समस्या(गणित)]] का हल था, जो सतह के अनुबंध पर एक बिंदु पर संवृत घटता निश्चित करने की सामयिक समस्या के बराबर है।<ref>{{cite book |last=Dehn |first=Max |author-link=Max Dehn| title=Papers on Group Theory and Topology |publisher=Springer-Verlag |year=2012 |orig-year=1987 |isbn=978-1461291077 }} Translated from the German and with introductions and an appendix by [[John Stillwell]], and with an appendix by [[Otto Schreier]].</ref>
-== बेठे जाली ==
+== बेथे जालक ==
-{{Main article|Bethe lattice}}
+{{Main article|बेथे जालक}}
-[[बेथे जाली]] या अनंत केली वृक्ष मुक्त समूह का केली ग्राफ है <math>n</math> उत्पादक। एक समूह की प्रस्तुति <math>G</math> द्वारा <math>n</math> उत्पादक मुक्त समूह से एक विशेषण मानचित्र से मेल खाता है <math>n</math> समूह के लिए उत्पादक <math>G,</math> और केली ग्राफ के स्तर पर अनंत केली पेड़ से केली ग्राफ तक एक मानचित्र पर। इसे ([[बीजगणितीय टोपोलॉजी]] में) केली ग्राफ के [[सार्वभौमिक आवरण]] के रूप में भी व्याख्या किया जा सकता है, जो सामान्य रूप से जुड़ा नहीं है।
+[[बेथे जाली|बेथे जालक]] या अनंत केली वृक्ष <math>n</math> उत्पादक मुक्त समूह का केली ग्राफ है। <math>n</math> उत्पादक द्वारा समूह <math>G</math> की प्रस्तुति <math>n</math> उत्पादक पर मुक्त समूह से समूह <math>G</math> तक और केली ग्राफ के स्तर पर असीमित केली वृक्ष से केली ग्राफ तक एक प्रतिचित्र के लिए एक प्रक्षेपण प्रतिचित्र से मेल खाती है।। इसे([[बीजगणितीय टोपोलॉजी]] में) केली ग्राफ के [[सार्वभौमिक आवरण]] के रूप में भी व्याख्या किया जा सकता है, जो सामान्य रूप से संयुक्त नहीं है।
 == यह भी देखें ==
-* वर्टेक्स-सकर्मक ग्राफ
+* शीर्ष-सकर्मक ग्राफ
 * एक समूह का समुच्चय बनाना
 * लोवाज़ अनुमान
-* क्यूब से जुड़े चक्र
+* क्यूब से संयुक्त चक्र
 * [[बीजगणितीय ग्राफ सिद्धांत]]
-* [[साइकिल ग्राफ (बीजगणित)]]
+* [[साइकिल ग्राफ (बीजगणित)|चक्र ग्राफ(बीजगणित)]]
 == टिप्पणियाँ ==
@@ Line 131: / Line 140: @@
 * {{mathworld | urlname = CayleyGraph  | title = Cayley graph }}
-{{DEFAULTSORT:Cayley Graph}}[[Category: समूह सिद्धांत]] [[Category: क्रमपरिवर्तन समूह]] [[Category: ग्राफ परिवार]] [[Category: एप्लिकेशन-विशिष्ट रेखांकन]] [[Category: ज्यामितीय समूह सिद्धांत]] [[Category: केली रेखांकन | केली रेखांकन ]]
+{{DEFAULTSORT:Cayley Graph}}
-[[Category: Machine Translated Page]]
+[[Category:All articles with unsourced statements|Cayley Graph]]
-[[Category:Created On 13/02/2023]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Cayley Graph]]
+[[Category:Articles with unsourced statements from September 2020|Cayley Graph]]
+[[Category:Created On 13/02/2023|Cayley Graph]]
+[[Category:Lua-based templates|Cayley Graph]]
+[[Category:Machine Translated Page|Cayley Graph]]
+[[Category:Pages with script errors|Cayley Graph]]
+[[Category:Short description with empty Wikidata description|Cayley Graph]]
+[[Category:Templates Vigyan Ready|Cayley Graph]]
+[[Category:Templates that add a tracking category|Cayley Graph]]
+[[Category:Templates that generate short descriptions|Cayley Graph]]
+[[Category:Templates using TemplateData|Cayley Graph]]
+[[Category:एप्लिकेशन-विशिष्ट रेखांकन|Cayley Graph]]
+[[Category:केली रेखांकन| केली रेखांकन ]]
+[[Category:क्रमपरिवर्तन समूह|Cayley Graph]]
+[[Category:ग्राफ परिवार|Cayley Graph]]
+[[Category:ज्यामितीय समूह सिद्धांत|Cayley Graph]]
+[[Category:समूह सिद्धांत|Cayley Graph]]

Anonymous

Search

केली ग्राफ: Difference between revisions

Namespaces

More