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

Revision as of 14:33, 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$ परिमित जाल है।

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

लिंक =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,$ और जाने ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ आइगेनवैल्यू समुच्चय के साथ $\Lambda _{i}(S)$ । फिर के आइगेनमानों का समुच्चय $\Gamma (G,S)$ बिल्कुल सही है ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ जहां आइगेनमान $\lambda$ बहुलता से प्रकट होता है $\dim(\rho _{i})$ की प्रत्येक घटना के लिए $\lambda$ के आइगेनवैल्यू के रूप में $\rho _{i}(S).$

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

यदि एक, इसके बजाय, एक निश्चित उपसमूह के सही सहसमुच्चय होने के लिए कोने लेता है $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$ बहुलता से प्रकट होता है $\dim(\rho _{i})$ की प्रत्येक घटना के लिए $\lambda$ के आइगेनवैल्यू के रूप में $\rho _{i}(S).$ किसी समूह का जीनस (गणित) उस समूह के किसी भी केली ग्राफ के लिए न्यूनतम जीनस है।^[6]

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

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

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

विस्तार गुण

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

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

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

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

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

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

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

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

पूर्ण CIS वर्गीकरण का प्रमाण इस तथ्य का उपयोग करता है कि CIS समूह का प्रत्येक उपसमूह और होमोमोर्फिक छवि भी CIS समूह है।^[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 29: / Line 29: @@
-<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>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>
 से मेल खाता है।
@@ 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>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>। {{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>। फिर के आइगेनमानों का समुच्चय <math>\Gamma(G,S)</math> बिल्कुल सही है <math display="inline">\bigcup_i \Lambda_i(S),</math> जहां आइगेनमान <math>\lambda</math> बहुलता से प्रकट होता है <math>\dim(\rho_i)</math> की प्रत्येक घटना के लिए <math>\lambda</math> के आइगेनवैल्यू के रूप में <math>\rho_i(S).</math>
@@ Line 61: / Line 62: @@
 == समूह सिद्धांत से संबंध ==
-समूह की संरचना के बारे में ज्ञान ग्राफ के आसन्न मैट्रिक्स का अध्ययन करके और विशेष रूप से [[वर्णक्रमीय ग्राफ सिद्धांत]] के प्रमेयों को लागू करके प्राप्त किया जा सकता है। इसके विपरीत, सममित उत्पादक समुच्चय के लिए, वर्णक्रमीय और प्रतिनिधित्व सिद्धांत <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>\dim(\rho_i)</math> की प्रत्येक घटना के लिए <math>\lambda</math> के आइगेनवैल्यू के रूप में <math>\rho_i(S).</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>
@@ Line 72: / Line 73: @@
 == विस्तार गुण ==
-कब <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>
 {{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. ''}}
-उदाहरण के लिए समूह <math>G = \mathrm{SL}_3(\Z)</math> संपत्ति (टी) है और [[प्राथमिक मैट्रिक्स]] द्वारा उत्पन्न होती है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देती है।
+उदाहरण के लिए समूह <math>G = \mathrm{SL}_3(\Z)</math> संपत्ति (टी) है और [[प्राथमिक मैट्रिक्स|प्राथमिक आव्यूह]] द्वारा उत्पन्न होती है और यह विस्तारक ग्राफ के अपेक्षाकृत स्पष्ट उदाहरण देती है।
 == अभिन्न वर्गीकरण ==
 एक अभिन्न ग्राफ वह होता है जिसके आइगेनवैल्यू सभी पूर्णांक होते हैं। जबकि इंटीग्रल ग्राफ़ का पूर्ण वर्गीकरण एक खुली समस्या है, कुछ समूहों के केली ग्राफ़ हमेशा इंटीग्रल होते हैं।
-केली ग्राफ के स्पेक्ट्रम के पिछले लक्षण वर्णन का उपयोग करते हुए, ध्यान दें <math>\Gamma(G,S)</math> अभिन्न है यदि  के eigenvalues <math>\rho(S)</math> प्रत्येक प्रतिनिधित्व के लिए अभिन्न हैं <math>\rho</math> का <math>G</math>।
+केली ग्राफ के स्पेक्ट्रम के पिछले लक्षण वर्णन का उपयोग करते हुए, ध्यान दें <math>\Gamma(G,S)</math> अभिन्न है यदि  के आइगेनमानों <math>\rho(S)</math> प्रत्येक प्रतिनिधित्व के लिए अभिन्न हैं <math>\rho</math> का <math>G</math>।
 === केली अभिन्न सरल समूह ===
@@ Line 98: / Line 99: @@
 === केली अभिन्न समूह ===
-केली इंटीग्रल ग्रुप की एक थोड़ी अलग धारणा है <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"/>प्रमाण केली अभिन्न समूहों के दो महत्वपूर्ण गुणों पर निर्भर करता है:
 * केली इंटीग्रल ग्रुप के सबग्रुप और होमोमोर्फिक इमेज भी केली इंटीग्रल ग्रुप हैं।
 * एक समूह केली इंटीग्रल है यदि  समूह का प्रत्येक जुड़ा केली ग्राफ भी इंटीग्रल है।
@@ Line 108: / Line 109: @@
 एक सामान्य समूह दिया <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>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>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> अभिन्न भी है।
@@ Line 121: / Line 122: @@
 == यह भी देखें ==
-* वर्टेक्स-सकर्मक ग्राफ
+* शीर्ष-सकर्मक ग्राफ
 * एक समूह का समुच्चय बनाना
 * लोवाज़ अनुमान

Anonymous

Search

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

Namespaces

More