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

Revision as of 17:15, 15 February 2023

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

गणित में, केली ग्राफ, जिसे केली वर्ण ग्राफ, केली आरेख, समूह आरेख या वर्ण समूह के रूप में भी जाना जाता है^[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$ परिमित जाल है।

Error creating thumbnail:

द्वितल समूह का केली ग्राफ

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]}

File:Cayley Q8 quaternion multiplication graph.svg

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

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

इतिहास

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

बेठे जाली

बेथे जाली या अनंत केली वृक्ष मुक्त समूह का केली ग्राफ है $n$ उत्पादक। एक समूह की प्रस्तुति $G$ द्वारा $n$ उत्पादक मुक्त समूह से एक विशेषण मानचित्र से मेल खाता है $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 9: / Line 9: @@
 * प्रत्येक <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> है, तो यह सामान्यतः  एक अप्रत्यक्ष किनारे द्वारा दर्शाया जाता है।
@@ Line 50: / Line 50: @@
 * केली ग्राफ <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>S</math> के अवयवों के बीच संबंधों को दर्शाता है। एक समूह के केली परिसर के अधिक विस्तृत निर्माण में, संबंधों के अनुरूप संवृत पथ [[बहुभुज|बहुभुजों]]  द्वारा "भरे" जाते हैं। इसका तात्पर्य यह है कि दी गई प्रस्तुति <math>\mathcal{P}</math> के केली ग्राफ निर्माण की समस्या  <math>\mathcal{P}</math>  [[समूहों के लिए शब्द समस्या]] को हल करने के बराबर है।<ref name = CGT/>
 *यदि  <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> परिमाण के अनंत नियमित वृक्ष (ग्राफ सिद्धांत) द्वारा आच्छादन किया गया है जो उत्पादक के एक ही समुच्चय पर मुक्त समूह के अनुरूप है।
 * किसी भी परिमित केली ग्राफ के लिए, जिसे अप्रत्यक्ष माना जाता है, संयोजकता(ग्राफ सिद्धांत) ग्राफ के [[डिग्री (ग्राफ सिद्धांत)|परिमाण (ग्राफ सिद्धांत)]] के कम से कम 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>
@@ Line 82: / Line 82: @@
 {{block indent | em = 1.6 | text = ''यदि एक असतत समूह <math>G</math> के समीप काज़दान गुण (T) है, और <math>S</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> गुण (टी) है और [[प्राथमिक मैट्रिक्स|प्राथमिक आव्यूह]] द्वारा उत्पन्न होती है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देती है।
+उदाहरण के लिए समूह <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> अभिन्न है यदि  के आइगेनमानों <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>।
+एक सामान्य समूह <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>
-गुओ, लिटकिना, माजुरोव और रेविन द्वारा 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>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> अभिन्न भी है।
 == इतिहास ==
-में आर्थर केली द्वारा परिमित समूहों के लिए केली ग्राफ पर पहली बार विचार किया गया था।<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}}
-[[बेथे जाली]] या अनंत केली वृक्ष मुक्त समूह का केली ग्राफ है <math>n</math> उत्पादक। एक समूह की प्रस्तुति <math>G</math> द्वारा <math>n</math> उत्पादक मुक्त समूह से एक विशेषण मानचित्र से मेल खाता है <math>n</math> समूह के लिए उत्पादक <math>G,</math> और केली ग्राफ के स्तर पर अनंत केली पेड़ से केली ग्राफ तक एक मानचित्र पर। इसे ([[बीजगणितीय टोपोलॉजी]] में) केली ग्राफ के [[सार्वभौमिक आवरण]] के रूप में भी व्याख्या किया जा सकता है, जो सामान्य रूप से जुड़ा नहीं है।
+[[बेथे जाली]] या अनंत केली वृक्ष मुक्त समूह का केली ग्राफ है <math>n</math> उत्पादक। एक समूह की प्रस्तुति <math>G</math> द्वारा <math>n</math> उत्पादक मुक्त समूह से एक विशेषण मानचित्र से मेल खाता है <math>n</math> समूह के लिए उत्पादक <math>G,</math> और केली ग्राफ के स्तर पर अनंत केली पेड़ से केली ग्राफ तक एक मानचित्र पर। इसे ([[बीजगणितीय टोपोलॉजी]] में) केली ग्राफ के [[सार्वभौमिक आवरण]] के रूप में भी व्याख्या किया जा सकता है, जो सामान्य रूप से संयुक्त  नहीं है।
 == यह भी देखें ==

Anonymous

Search

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

Namespaces

More