सशक्त नियमित आलेख

क्रम 13 का पीला आलेख, मापदंडों के साथ एक दृढ़ता से नियमित आलेख srg(13,6,2,3).

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

आलेख सिद्धांत में, एक सशक्त नियमित आलेख (एसआरजी) को निम्नानुसार परिभाषित किया गया है। मान लीजिये G = (V, E) v शीर्ष और डिग्री (आलेख सिद्धांत) k के साथ एक नियमित आलेख बनें। G को दृढ़ता से नियमित कहा जाता है यदि पूर्णांक λ और μ इस प्रकार है कि:

• प्रत्येक दो आसन्न शीर्ष λ उभयनिष्ठ प्रतिवैस में है।
• प्रत्येक दो गैर-आसन्न शीर्षों μ उभयनिष्ठ प्रतिवैस में होता है।

एक srg(v, k, λ, μ) का पूरक भी दृढ़ता से नियमित है। एक srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ) है।

जब भी μ गैर-शून्य होता है तो एक दृढ़ता से नियमित आलेख व्यास 2 के साथ एक दूरी-नियमित आलेख होता है। जब भी यह स्थानीय रूप से रैखिक आलेख λ = 1 होता है।

व्युत्पत्ति

साहित्य में एक दृढ़ता से नियमित आलेख को srg(v, k, λ, μ) दर्शाया जाता है। परंपरा के अनुसार, जो आलेख तुच्छ रूप से परिभाषा को संतुष्ट करते हैं उन्हें विस्तृत अध्ययन और दृढ़ता से नियमित आलेख की सूची से बाहर रखा जाता है। इनमें एक या अधिक समान आकार के पूर्ण आलेख का असंयुक्त संघ सम्मिलित है, और उनके पूरक आलेख, समान आकार के स्वतंत्र सम्मुच्चयों के साथ पूर्ण बहुपक्षीय आलेख है।

एंड्रयू ब्रेवर और हेंड्रिक वैन माल्डेघम (संदर्भ देखें) वर्णक्रमीय आलेख सिद्धांत के आधार पर एक दृढ़ता से नियमित आलेख की एक वैकल्पिक लेकिन पूरी तरह से समकक्ष परिभाषा का उपयोग करते हैं: एक दृढ़ता से नियमित आलेख एक परिमित नियमित आलेख है जिसमें बिल्कुल तीन आइगेनवैल्यू होते हैं, जिनमें से केवल एक बराबर होता है। यह स्वचालित रूप से पूरी तरह से जुड़े हुए आलेख (जिनमें केवल दो अलग-अलग eigenvalues ​​​​हैं, तीन नहीं) और डिस्कनेक्ट किए गए आलेख (जिनकी डिग्री k की बहुलता विभिन्न जुड़े हुए घटकों की संख्या के बराबर है, को बाहर कर देती है, जो इसलिए होगा) एक से अधिक)। ब्रौवर सहित अधिकांश साहित्य में बड़े स्वदेशी मान को r (बहुलता f के साथ) और छोटे को s (बहुलता g के साथ) के रूप में संदर्भित किया गया है।

इतिहास

राज चंद्र बोस|आर.सी. द्वारा सशक्त रूप से नियमित आलेख पेश किए गए। 1963 में बोस. उन्होंने 1950 के दशक में वर्णक्रमीय आलेख सिद्धांत के तत्कालीन नए क्षेत्र में पहले के काम को आगे बढ़ाया।

उदाहरण

• लंबाई 5 का चक्र आलेख ़ एक srg(5, 2, 0, 1) है।
• पीटरसन आलेख एक srg(10, 3, 0, 1) है।
• क्लेब्स आलेख एक srg(16, 5, 0, 2) है।
• श्रीखंडे आलेख एक srg(16, 6, 2, 2) है जो दूरी-संक्रमणीय आलेख नहीं है।
• n × n वर्ग रूक का आलेख, यानी, एक संतुलित पूर्ण द्विदलीय आलेख K का रेखा आलेख_n,n, एक एसआरजी(एन) है², 2n − 2, n − 2, 2). के लिए पैरामीटर n = 4 श्रीखंडे आलेख से मेल खाता है, लेकिन दोनों आलेख समरूपी नहीं हैं।
• पूर्ण आलेख K का रेखा आलेख_nएक ${\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)}$.
• चांग रेखांकन srg(28, 12, 6, 4) हैं, K के लाइन आलेख के समान₈, लेकिन ये चार आलेख समरूपी नहीं हैं।
• एक सामान्यीकृत चतुर्भुज GQ(2, 4) का रेखा आलेख एक srg(27, 10, 1, 5) है। वास्तव में क्रम (s, t) का प्रत्येक सामान्यीकृत चतुर्भुज इस तरह से एक दृढ़ता से नियमित आलेख देता है: बुद्धि के लिए, एक srg((s + 1)(st + 1), s(t + 1), s - 1, t +1).
• श्लाफली आलेख एक srg(27, 16, 10, 8) है।
• हॉफमैन-सिंगलटन आलेख एक srg(50, 7, 0, 1) है।
• सिम्स अस्पष्ट आलेख एक (56, 10, 0, 2) है।
• M22 आलेख उर्फ ​​मेस्नर आलेख एक srg(77, 16, 0, 4) है।
• ब्रौवर-हैमर्स आलेख एक srg(81, 20, 1, 6) है।
• हिगमैन-सिम्स आलेख एक srg(100, 22, 0, 6) है।
• स्थानीय मैकलॉघलिन आलेख एक srg(162, 56, 10, 24) है।
• कैमरून आलेख एक srg(231, 30, 9, 3) है।
• बर्लेकैंप-वैन लिंट-सीडेल आलेख एक एसआरजी(243, 22, 1, 2) है।

स्थानीय मैकलॉघलिन आलेख एक srg(275, 112, 30, 56) है।

• क्रम q का पैली आलेख एक srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4) है। सबसे छोटा पैली आलेख, के साथ q = 5, 5-चक्र (ऊपर) है।
• स्व-पूरक आलेख|स्व-पूरक सममित आलेख|चाप-संक्रमणीय आलेख दृढ़ता से नियमित हैं।

एक दृढ़ता से नियमित आलेख को आदिम कहा जाता है यदि आलेख और उसके पूरक दोनों जुड़े हुए हैं। उपरोक्त सभी आलेख अन्यथा आदिम हैं μ = 0 या λ = k.

कॉनवे की 99-आलेख समस्या एक एसआरजी (99, 14, 1, 2) के निर्माण के लिए कहती है। यह अज्ञात है कि क्या इन मापदंडों वाला कोई आलेख मौजूद है, और जॉन हॉर्टन कॉनवे ने इस समस्या के समाधान के लिए $1000 के पुरस्कार की पेशकश की।

त्रिकोण-मुक्त आलेख

λ=0 वाले दृढ़तापूर्वक नियमित आलेख त्रिकोण-मुक्त आलेख हैं। 3 से कम शीर्षों पर पूर्ण आलेख और सभी पूर्ण द्विदलीय आलेख के अलावा, पहले सूचीबद्ध सात (पेंटागन, पीटरसन, क्लेबश, हॉफमैन-सिंगलटन, गेविर्ट्ज़, मेस्नर-एम22, और हिगमैन-सिम्स) ही एकमात्र ज्ञात हैं।

जियोडेटिक आलेख

प्रत्येक दृढ़तापूर्वक नियमित आलेख के साथ $\mu =1$ एक भूगणितीय आलेख ़ है, एक ऐसा आलेख जिसमें प्रत्येक दो शीर्षों पर एक अद्वितीय लघुतम पथ समस्या होती है। एकमात्र ज्ञात दृढ़ता से नियमित आलेख के साथ $\mu =1$ वे कहाँ हैं $\lambda$ 0 है, इसलिए त्रिकोण-मुक्त भी है। इन्हें मूर आलेख कहा जाता है और ये #हॉफमैन-सिंगलटन प्रमेय हैं। मापदंडों के अन्य संयोजन जैसे (400, 21, 2, 1) को अभी तक खारिज नहीं किया गया है। उन संपत्तियों पर चल रहे शोध के बावजूद, जिनके साथ एक दृढ़ता से नियमित आलेख है $\mu =1$ होगा, यह ज्ञात नहीं है कि क्या और भी अस्तित्व में हैं या उनकी संख्या सीमित है या नहीं।केवल प्रारंभिक परिणाम ही ज्ञात है, वह $\lambda$ ऐसे आलेख के लिए 1 नहीं हो सकता.

दृढ़ता से नियमित आलेख के बीजगणितीय गुण

पैरामीटरों के बीच बुनियादी संबंध

srg(v, k, λ, μ) में चार पैरामीटर स्वतंत्र नहीं हैं। उन्हें निम्नलिखित संबंध का पालन करना होगा:

$(v-k-1)\mu =k(k-\lambda -1)$

उपरोक्त संबंध निम्नलिखित गणना तर्क के माध्यम से प्राप्त किया गया है:

1. आलेख के शीर्षों को तीन स्तरों में स्थित होने की कल्पना करें। स्तर 0 में किसी भी शीर्ष को मूल के रूप में चुनें। फिर इसके k प्रतिवैस स्तर 1 में हैं, और अन्य सभी शीर्ष स्तर 2 में हैं।
2. लेवल 1 में शीर्ष सीधे जड़ से जुड़े होते हैं, इसलिए उनमें जड़ के साथ अन्य प्रतिवैस समान होने चाहिए, और ये सामान्य प्रतिवैस भी स्तर 1 में होने चाहिए। चूंकि प्रत्येक शीर्ष की डिग्री k है, इसलिए वहां हैं $k-\lambda -1$ स्तर 2 में शीर्षों से जुड़ने के लिए प्रत्येक स्तर 1 नोड के किनारे शेष हैं। इसलिए, वहाँ हैं $k(k-\lambda -1)$ लेवल 1 और लेवल 2 के बीच का किनारा।
3. स्तर 2 में शीर्ष सीधे जड़ से जुड़े नहीं हैं, इसलिए उनके मूल के साथ μ सामान्य प्रतिवैस होने चाहिए, और ये सभी सामान्य प्रतिवैस स्तर 1 में होने चाहिए। $(v-k-1)$ स्तर 2 में शीर्ष, और प्रत्येक स्तर 1 में μ शीर्षों से जुड़ा है। इसलिए स्तर 1 और स्तर 2 के बीच किनारों की संख्या है $(v-k-1)\mu$.
4. लेवल 1 और लेवल 2 के बीच किनारों के लिए दो अभिव्यक्तियों को बराबर करने पर, संबंध इस प्रकार है।

आसन्नता मैट्रिक्स समीकरण

आइए मैं पहचान मैट्रिक्स को निरूपित करता हूं और जे को ऑर्डर वी के दोनों मैट्रिक्स को निरूपित करने देता हूं। दृढ़ता से नियमित आलेख का आसन्न लोगों का मैट्रिक्स समीकरणों को संतुष्ट करता है।

पहला:

$AJ=JA=kJ,$

जो नियमितता की आवश्यकता का पुनर्कथन है। इससे पता चलता है कि k सभी eigenvector के साथ आसन्न मैट्रिक्स का एक eigenvalue है।

दूसरा:

$A^{2}=kI+\lambda {A}+\mu (J-I-A)$

जो सशक्त नियमितता को व्यक्त करता है। बायीं ओर का ij-वां तत्व i से j तक दो-चरणीय पथों की संख्या देता है। दायीं ओर का पहला पद i से वापस i तक दो-चरणीय पथों की संख्या देता है, अर्थात् k किनारे बाहर और वापस अंदर। दूसरा पद दो-चरणीय पथों की संख्या देता है जब i और j सीधे जुड़े होते हैं। जब i और j जुड़े नहीं होते हैं तो तीसरा पद संगत मान देता है। चूंकि तीन मामले परस्पर अनन्य और सामूहिक रूप से संपूर्ण हैं, इसलिए सरल योगात्मक समानता इस प्रकार है।

इसके विपरीत, एक आलेख जिसका आसन्न मैट्रिक्स उपरोक्त दोनों शर्तों को पूरा करता है और जो पूर्ण या शून्य आलेख नहीं है, एक दृढ़ता से नियमित आलेख है।

आइजेनवैल्यू और आलेख स्पेक्ट्रम

चूँकि आसन्न मैट्रिक्स A सममित है, यह उस ऑर्थोगोनल आधार का अनुसरण करता है। हमने पहले ही ऊपर एक आइजनवेक्टर देखा है जो आइगेनवैल्यू k के अनुरूप सभी से बना है। इसलिए अन्य eigenvectors x को सभी को संतुष्ट करना होगा $Jx=0$ जहां J पहले की तरह ऑल-वन्स मैट्रिक्स है। पहले से स्थापित समीकरण लें:

$A^{2}=kI+\lambda {A}+\mu (J-I-A)$

और उपरोक्त समीकरण को eigenvector x से गुणा करें:

$A^{2}x=kIx+\lambda {A}x+\mu (J-I-A)x$

संगत eigenvalue p को कॉल करें (भ्रमित न हों)। $\lambda$ आलेख पैरामीटर) और स्थानापन्न $Ax=px$, $Jx=0$ और $Ix=x$:

$p^{2}x=kx+\lambda px-\mu x-\mu px$

x को हटाएँ और द्विघात प्राप्त करने के लिए पुनर्व्यवस्थित करें:

$p^{2}+(\mu -\lambda )p-(k-\mu )=0$

इससे दो अतिरिक्त eigenvalues ​​मिलते हैं ${\frac {1}{2}}\left[(\lambda -\mu )\pm {\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$. इस प्रकार एक दृढ़ता से नियमित मैट्रिक्स के लिए बिल्कुल तीन eigenvalues ​​​​हैं।

इसके विपरीत, केवल तीन eigenvalues ​​​​के साथ जुड़ा हुआ नियमित आलेख दृढ़ता से नियमित होता है। अधिकांश दृढ़तापूर्वक नियमित आलेख साहित्य में शब्दावली का पालन करते हुए, बड़े eigenvalue को बहुलता f के साथ r कहा जाता है और छोटे को बहुलता g के साथ s कहा जाता है।

चूँकि सभी eigenvalues ​​​​का योग ट्रेस (रैखिक बीजगणित) है, जो इस मामले में शून्य है, संबंधित गुणन f और g की गणना की जा सकती है:

• Eigenvalue k में बहुलता (गणित) 1 है।
• आइजेनवैल्यू $r={\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$ बहुलता है $f={\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$.
• आइजेनवैल्यू $s={\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\,\right]$ बहुलता है $g={\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$.

चूँकि बहुलताएँ पूर्णांक होनी चाहिए, उनकी अभिव्यक्तियाँ v, k, μ, और λ के मानों पर और बाधाएँ प्रदान करती हैं।

जिसके लिए सशक्त रूप से नियमित आलेख $2k+(v-1)(\lambda -\mu )\neq 0$ असमान बहुलता वाले पूर्णांक eigenvalues ​​​​हैं।

जिसके लिए सशक्त रूप से नियमित आलेख $2k+(v-1)(\lambda -\mu )=0$ सममित सम्मेलन मैट्रिक्स के साथ उनके संबंध के कारण सम्मेलन आलेख कहा जाता है। उनके पैरामीटर कम हो जाते हैं

$\operatorname {srg} \left(v,{\frac {1}{2}}(v-1),{\frac {1}{4}}(v-5),{\frac {1}{4}}(v-1)\right).$

उनके स्वदेशी मूल्य हैं $r={\frac {-1+{\sqrt {v}}}{2}}$ और $s={\frac {-1-{\sqrt {v}}}{2}}$, दोनों की बहुलता बराबर है ${\frac {v-1}{2}}$. इसके अलावा, इस मामले में, v को ब्रुक-राइसर-चौला प्रमेय से संबंधित दो वर्गों के योग के बराबर होना चाहिए।

eigenvalues ​​​​और उनकी बहुलता के आगे गुण हैं:

• $(A-rI)\times (A-sI)=\mu .J$, इसलिए $(k-r).(k-s)=\mu v$
• $\lambda -\mu =r+s$
• $k-\mu =-r\times s$
• $k\geq r$
• एक दिया गया srg(v, k, λ, μ) eigenvalues ​​r और s के साथ, यह पूरक है srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ) के eigenvalues ​​-1-s और -1-r हैं।
• बहुलता के लिए वैकल्पिक समीकरण हैं $f={\frac {(s+1)k(k-s)}{\mu (s-r)}}$ और $g={\frac {(r+1)k(k-r)}{\mu (r-s)}}$
• फ़्रेम भागफल स्थिति: $vk(v-k-1)=fg(r-s)^{2}$. एक परिणाम के रूप में, $v=(r-s)^{2}$ अगर और केवल अगर ${f,g}={k,v-k-1}$ किसी क्रम में.
• केरिन स्थितियाँ: $(v-k-1)^{2}(k^{2}+r^{3})\geq (r+1)^{3}k^{2}$ और $(v-k-1)^{2}(k^{2}+s^{3})\geq (s+1)^{3}k^{2}$
• पूर्ण बाध्य: $v\leq {\frac {f(f+3)}{2}}$ और $v\leq {\frac {g(g+3)}{2}}$.
• पंजा बँधा हुआ: यदि $r+1>{\frac {s(s+1)(\mu +1)}{2}}$, तब $\mu =s^{2}$ या $\mu =s(s+1)$.

यदि मापदंडों के किसी भी सेट के लिए उपरोक्त शर्तों का उल्लंघन किया जाता है, तो उन मापदंडों के लिए कोई दृढ़ता से नियमित आलेख मौजूद नहीं है। ब्रौवर ने अस्तित्व या गैर-अस्तित्व की ऐसी सूचियां संकलित की हैं यहां गैर-अस्तित्व के कारणों के साथ, यदि कोई हो।

हॉफमैन-सिंगलटन प्रमेय

जैसा कि ऊपर उल्लेख किया गया है, eigenvalues ​​​​की बहुलताएँ द्वारा दी गई हैं

$M_{\pm }={\frac {1}{2}}\left[(v-1)\pm {\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$

जो पूर्णांक होना चाहिए.

1960 में, एलन जे. हॉफमैन और रॉबर्ट सिंगलटन ने मूर आलेख पर लागू होने पर उन अभिव्यक्तियों की जांच की, जिनमें λ = 0 और μ = 1 है। ऐसे आलेख त्रिकोण से मुक्त हैं (अन्यथा λ शून्य से अधिक होगा) और चतुर्भुज (अन्यथा μ 1 से अधिक होगा) , इसलिए उनकी परिधि (सबसे छोटी चक्र लंबाई) 5 है। समीकरण में λ और μ के मानों को प्रतिस्थापित करना $(v-k-1)\mu =k(k-\lambda -1)$, यह देखा जा सकता है $v=k^{2}+1$, और eigenvalue बहुलताएँ कम हो जाती हैं

$M_{\pm }={\frac {1}{2}}\left[k^{2}\pm {\frac {2k-k^{2}}{\sqrt {4k-3}}}\right]$

गुणनखंडों के पूर्णांक होने के लिए, मात्रा ${\frac {2k-k^{2}}{\sqrt {4k-3}}}$ तर्कसंगत होना चाहिए, इसलिए या तो अंश $2k-k^{2}$ शून्य या हर है ${\sqrt {4k-3}}$ एक पूर्णांक है.

यदि अंश $2k-k^{2}$ शून्य है, संभावनाएँ हैं:

• k = 0 और v = 1 एक शीर्ष और बिना किनारों वाला एक तुच्छ आलेख उत्पन्न करता है, और
• k = 2 और v = 5 से 5-शीर्ष चक्र आलेख प्राप्त होता है $C_{5}$, उभयनिष्ठतौर पर एक नियमित पंचकोण के रूप में खींचा जाता है।

यदि हर ${\sqrt {4k-3}}$ तो, एक पूर्णांक t है $4k-3$ एक पूर्ण वर्ग है $t^{2}$, इसलिए $k={\frac {t^{2}+3}{4}}$. प्रतिस्थापन:

${\begin{aligned}M_{\pm }&={\frac {1}{2}}\left[\left({\frac {t^{2}+3}{4}}\right)^{2}\pm {\frac {{\frac {t^{2}+3}{2}}-\left({\frac {t^{2}+3}{4}}\right)^{2}}{t}}\right]\\32M_{\pm }&=(t^{2}+3)^{2}\pm {\frac {8(t^{2}+3)-(t^{2}+3)^{2}}{t}}\\&=t^{4}+6t^{2}+9\pm {\frac {-t^{4}+2t^{2}+15}{t}}\\&=t^{4}+6t^{2}+9\pm \left(-t^{3}+2t+{\frac {15}{t}}\right)\end{aligned}}$

चूँकि दोनों पक्ष पूर्णांक हैं, ${\frac {15}{t}}$ एक पूर्णांक होना चाहिए, इसलिए t, अर्थात् 15 का एक गुणनखंड है $t\in \{\pm 1,\pm 3,\pm 5,\pm 15\}$, इसलिए $k\in \{1,3,7,57\}$. के बदले में:

• k = 1 और v = 2 एक किनारे से जुड़े दो शीर्षों का एक तुच्छ आलेख प्राप्त करता है,
• k = 3 और v = 10 पीटरसन आलेख प्राप्त करता है,
• k = 7 और v = 50 हॉफमैन-सिंगलटन आलेख प्राप्त करता है, जिसे हॉफमैन और सिंगलटन ने इस विश्लेषण के दौरान खोजा था, और
• k = 57 और v = 3250 एक प्रसिद्ध आलेख की भविष्यवाणी करता है जिसे 1960 के बाद से न तो खोजा गया है, न ही इसके अस्तित्व को अस्वीकृत किया गया है।

हॉफमैन-सिंगलटन प्रमेय में कहा गया है कि ऊपर सूचीबद्ध आलेख को छोड़कर कोई भी नियमित रूप से नियमित परिधि-5 मूर आलेख नहीं हैं।

यह भी देखें

• आंशिक ज्यामिति
• सीडेल आसन्नता मैट्रिक्स
• दो-आलेख

संदर्भ

• Andries Brouwer and Hendrik van Maldeghem (2022), Strongly Regular Graphs. Cambridge: Cambridge University Press. ISBN 1316512037. ISBN 978-1316512036
• A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
• Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1

बाहरी संबंध

• Eric W. Weisstein, Mathworld article with numerous examples.
• Gordon Royle, List of larger graphs and families.
• Andries E. Brouwer, Parameters of Strongly Regular Graphs.
• Brendan McKay, Some collections of graphs.
• Ted Spence, Strongly regular graphs on at most 64 vertices.