हिगमैन-सिम्स ग्राफ: Difference between revisions
(Created page with "{{infobox graph | name = Higman–Sims graph | image = 220px | image_caption = Drawing based on Paul R. Hafner's construction.<ref>{{Cite jo...") |
No edit summary |
||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 23: | Line 23: | ||
}} | }} | ||
[[Image:Higman Sims Graph Parts.svg|220px|right|thumb|हाफनर के निर्माण के अलग हुए | [[Image:Higman Sims Graph Parts.svg|220px|right|thumb|हाफनर के निर्माण के अलग हुए भाग।]]गणितीय [[ग्राफ सिद्धांत|आलेख सिद्धांत]] में, हिगमैन-सिम्स आलेख एक 22-[[नियमित ग्राफ|नियमित आलेख]] [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष आलेख]] है जिसमें 100 कोने और 1100 किनारे हैं। यह अद्वितीय [[दृढ़ता से नियमित ग्राफ|दृढ़ता से नियमित आलेख]] एसआरजी (100,22,0,6) है, जहां कोई भी निकटवर्ती युग्म सामान्य निकटवर्ती को साझा नहीं करती है और प्रत्येक गैर-निकटवर्ती युग्म के कोने छह सामान्य निकटवर्तियों को साझा करते हैं।<ref>{{MathWorld|urlname=Higman-SimsGraph|title=Higman–Sims Graph}}</ref> इसका निर्माण सर्वप्रथम {{harvtxt|मेस्नेर|1956}} द्वारा किया गया था और 1968 में डोनाल्ड जी. हिगमैन और चार्ल्स सी. सिम्स द्वारा हिगमैन-सिम्स समूह को परिभाषित करने की विधि के रूप में फिर से खोजा गया, हिगमैन-सिम्स आलेख के स्वसमाकृतिकता के समूह में उपसमूह दो के सूचकांक का एक उपसमूह है।<ref>{{Cite journal | ||
| last1 = Higman | first1 = Donald G. | | last1 = Higman | first1 = Donald G. | ||
| last2 = Sims | first2 = Charles C. | author2-link = Charles Sims (mathematician) | | last2 = Sims | first2 = Charles C. | author2-link = Charles Sims (mathematician) | ||
| Line 36: | Line 36: | ||
== निर्माण == | == निर्माण == | ||
===[[M22 ग्राफ]] से=== | ===[[M22 ग्राफ|एम22 आलेख]] से=== | ||
एम22 आलेख लें, दृढ़ता से नियमित आलेख एसआरजी (77,16,0,4) और इसे S (3,6,22) के बिंदुओं के अनुरूप 22 नवीन शीर्षों के साथ बढ़ाएं, प्रत्येक कक्ष को इसके बिंदुओं से जोड़ा जा रहा है, और अतिरिक्त शीर्ष सी 22 बिंदुओं से जुड़ा है। | |||
=== हॉफमैन-सिंगलटन | === हॉफमैन-सिंगलटन आलेख से === | ||
हॉफमैन-सिंगलटन | हॉफमैन-सिंगलटन आलेख में आकार 15 के 100 [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र समूह (आलेख सिद्धांत]]) हैं। 100 संबंधित शीर्षों के साथ नवीन आलेख़ बनाएँ, और उन शीर्षों को संबद्ध करें जिनके संबंधित स्वतंत्र समूहों में पूर्णतः 0 या 8 अवयव समान हैं। परिणामी हिगमैन-सिम्स आलेख को 352 विधियों से हॉफमैन-सिंगलटन आलेख की दो प्रतियों में विभाजित किया जा सकता है। | ||
परिणामी हिगमैन-सिम्स | |||
=== एक घन से === | === एक घन से === | ||
000, 001, 010, ..., 111 लेबल वाले शीर्षों वाला घन लें। सभी 70 संभव 4-शीर्षों के | 000, 001, 010, ..., 111 लेबल वाले शीर्षों वाला घन लें। सभी 70 संभव 4-शीर्षों के समूह लें, और मात्र उन्हीं को बनाए रखें जिनके [[XOR|एक्सओआर]] का मूल्यांकन 000 है; 14 ऐसे 4-समूह हैं, जो 6 शीर्षों + 6 विकर्ण-आयतों + 2 समता टेट्राहेड्रा के अनुरूप हैं। यह 8 बिंदुओं पर 3- (8,4,1) [[ब्लॉक डिजाइन|कक्ष डिजाइन]] है, कक्ष आकार 4 के 14 कक्षों के साथ, प्रत्येक बिंदु 7 कक्षों में दिखाई देते है, बिंदुओं की प्रत्येक युग्म 3 बार दिखाई देती है, बिंदुओं का प्रत्येक तिगुना एक बार होता है। मूल 8 शीर्षों को 8 में से किसी एक में बदलें! = 40320 विधि, और प्रतिलिपि को त्यागें। शीर्षों को फिर से लेबल करने के 30 अलग-अलग विधि हैं (अर्थात, 30 अलग-अलग डिज़ाइन जो बिंदुओं के क्रमपरिवर्तन द्वारा एक दूसरे के लिए सभी समरूपी हैं)। ऐसा इसलिए है क्योंकि 1344 [[ automorphism |स्वसमाकृतिकता]] हैं, और 40320/1344 = 30 हैं। | ||
30 डिज़ाइनों में से प्रत्येक के लिए और प्रत्येक डिज़ाइन की प्रत्येक पंक्ति के लिए | 30 डिज़ाइनों में से प्रत्येक के लिए और प्रत्येक डिज़ाइन की प्रत्येक पंक्ति के लिए शीर्ष बनाएँ (कुल 70 ऐसी पंक्तियाँ हैं, प्रत्येक पंक्ति 8 का 4-समूह है और 6 डिज़ाइनों में दिखाई देती है)। प्रत्येक डिज़ाइन को उसकी 14 पंक्तियों से जोड़ें। अलग-अलग डिज़ाइनों को एक दूसरे से संबद्ध करें (प्रत्येक डिज़ाइन 8 अन्य के साथ अलग है)। पंक्तियों को एक दूसरे से संबद्ध करें यदि उनके निकट सामान्य रूप से एक अवयव है (4x4 = 16 ऐसे निकटवर्ती हैं)। परिणामी आलेख हिगमैन-सिम्स आलेख है। पंक्तियाँ 16 अन्य पंक्तियों से जुड़ी हैं और 6 डिज़ाइन == डिग्री 22 से जुड़ी हैं। डिज़ाइन 14 पंक्तियों से जुड़ी हैं और 8 असंयुक्त डिज़ाइन == डिग्री 22 हैं। इस प्रकार सभी 100 कोने में डिग्री 22 है। | ||
== बीजगणितीय गुण == | == बीजगणितीय गुण == | ||
हिगमैन-सिम्स | हिगमैन-सिम्स आलेख का [[ऑटोमोर्फिज्म समूह|स्वसमाकृतिकता समूह]] क्रम {{formatnum:88704000}} समरूपी का एक समूह है, जो क्रम 2 के [[चक्रीय समूह]] के साथ क्रम {{formatnum:44352000}} के हिगमैन-सिम्स समूह के [[अर्ध-प्रत्यक्ष उत्पाद]] के लिए है।<ref>{{cite web | ||
| url = http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html | | url = http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html | ||
| title = Higman–Sims graph | | title = Higman–Sims graph | ||
| author-link = Andries E. Brouwer | | author-link = Andries E. Brouwer | ||
| author = Brouwer, Andries E.}}</ref> इसमें | | author = Brouwer, Andries E.}}</ref> इसमें स्वसमाकृतिकता हैं जो किसी भी किनारे को किसी अन्य किनारे पर ले जाते हैं, जिससे हिगमैन-सिम्स आलेख बढ़त-संक्रमणीय आलेख बन जाते है।<ref>Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397–407, 1993.</ref> | ||
== | हिगमन-सिम्स आलेख़ का विशिष्ट बहुपद (x − 22) (x − 2) <sup>77</sup> (x + 8) <sup>22</sup> है | ||
[[Image:Higman-Sims-19.svg|220px|right|thumb| | |||
इसलिए, हिगमैन-सिम्स आलेख [[अभिन्न ग्राफ|अभिन्न आलेख]] है: इसके [[स्पेक्ट्रल ग्राफ सिद्धांत|वर्णक्रम आलेख सिद्धांत]] में पूर्ण रूप से पूर्णांक होते हैं। यह इस विशिष्ट बहुपद के साथ एकमात्र आलेख भी है, जो इसे इसके वर्णक्रम द्वारा निर्धारित आलेख बनाते है। | |||
== लीच की जालक के भीतर == | |||
[[Image:Higman-Sims-19.svg|220px|right|thumb|लीच जालक के भीतर हिगमैन-सिम्स आलेख का प्रक्षेपण।]]हिगमैन-सिम्स आलेख स्वाभाविक रूप से [[जोंक जाली|लीच जालक]] के भीतर होते है: यदि X, Y और Z लीच जालक में तीन बिंदु हैं जैसे कि दूरी XY, XZ और YZ क्रमशः <math>2, \sqrt{6}, \sqrt{6}</math> हैं, तो वस्तुतः 100 लीच जालक बिंदु T हैं जैसे कि सभी दूरियाँ XT, YT और ZT 2 के बराबर हैं, और यदि हम दो ऐसे बिंदुओं T और T' को जोड़ते हैं, जब उनके बीच की दूरी <math> \sqrt{6} </math> , परिणामी आलेख हिगमैन-सिम्स आलेख के लिए समरूपी है। इसके अतिरिक्त , लीच जालक के सभी स्वसमाकृतिकता का समूह (अर्थात, यूक्लिडियन सर्वांगसमताएं इसे स्थायीकर करती हैं) जो x, y और z में से प्रत्येक को ठीक करती हैं, हिगमैन-सिम्स समूह है (यदि हम x और y का आदान-प्रदान करने की अनुमति देते हैं, तो सभी का क्रम 2 विस्तार आलेख स्वसमाकृतिकता प्राप्त होता है)। इससे पता चलता है कि हिगमैन-सिम्स समूह [[कॉनवे समूह]] Co<sub>2</sub> (इसके क्रम 2 विस्तार के साथ) और Co<sub>3</sub> के भीतर होता है, और इसके परिणामस्वरूप Co<sub>1</sub> भी होते है।<ref>{{Cite book | last1=Conway | first1=John H. | authorlink1=John Horton Conway | last2=Sloane | first2=Neil J. A. | authorlink2=Neil Sloane | title=क्षेत्र पैकिंग, जाली और समूह| edition=3rd | series=Grundlehren der mathematischen Wissenschaften | isbn=1-4419-3134-1 | publisher=[[Springer-Verlag]] }} chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups"), pp. 292–293.</ref> | |||
| Line 65: | Line 67: | ||
*{{Citation | last1=Mesner | first1=Dale Marsh | title=An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types | publisher=Department of Statistics, Michigan State University | series=Doctoral Thesis |mr=2612633 | year=1956}} | *{{Citation | last1=Mesner | first1=Dale Marsh | title=An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types | publisher=Department of Statistics, Michigan State University | series=Doctoral Thesis |mr=2612633 | year=1956}} | ||
{{DEFAULTSORT:Higman-Sims graph}} | {{DEFAULTSORT:Higman-Sims graph}} | ||
[[Category: | [[Category:CS1 errors]] | ||
[[Category:Created On 08/05/2023]] | [[Category:Created On 08/05/2023|Higman-Sims graph]] | ||
[[Category:Machine Translated Page|Higman-Sims graph]] | |||
[[Category:Pages with script errors|Higman-Sims graph]] | |||
[[Category:Templates Vigyan Ready|Higman-Sims graph]] | |||
[[Category:नियमित रेखांकन|Higman-Sims graph]] | |||
[[Category:मजबूत नियमित रेखांकन|Higman-Sims graph]] | |||
[[Category:व्यक्तिगत रेखांकन|Higman-Sims graph]] | |||
[[Category:समूह सिद्धांत|Higman-Sims graph]] | |||
Latest revision as of 17:21, 17 May 2023
| Higman–Sims graph | |
|---|---|
 Drawing based on Paul R. Hafner's construction.[1] | |
| Named after | Donald G. Higman Charles C. Sims |
| Vertices | 100 |
| Edges | 1100 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 4 |
| Automorphisms | 88,704,000 (HS:2) |
| Properties | Strongly regular Edge-transitive Hamiltonian Eulerian |
| Table of graphs and parameters | |
गणितीय आलेख सिद्धांत में, हिगमैन-सिम्स आलेख एक 22-नियमित आलेख अप्रत्यक्ष आलेख है जिसमें 100 कोने और 1100 किनारे हैं। यह अद्वितीय दृढ़ता से नियमित आलेख एसआरजी (100,22,0,6) है, जहां कोई भी निकटवर्ती युग्म सामान्य निकटवर्ती को साझा नहीं करती है और प्रत्येक गैर-निकटवर्ती युग्म के कोने छह सामान्य निकटवर्तियों को साझा करते हैं।[2] इसका निर्माण सर्वप्रथम मेस्नेर (1956) द्वारा किया गया था और 1968 में डोनाल्ड जी. हिगमैन और चार्ल्स सी. सिम्स द्वारा हिगमैन-सिम्स समूह को परिभाषित करने की विधि के रूप में फिर से खोजा गया, हिगमैन-सिम्स आलेख के स्वसमाकृतिकता के समूह में उपसमूह दो के सूचकांक का एक उपसमूह है।[3]
निर्माण
एम22 आलेख से
एम22 आलेख लें, दृढ़ता से नियमित आलेख एसआरजी (77,16,0,4) और इसे S (3,6,22) के बिंदुओं के अनुरूप 22 नवीन शीर्षों के साथ बढ़ाएं, प्रत्येक कक्ष को इसके बिंदुओं से जोड़ा जा रहा है, और अतिरिक्त शीर्ष सी 22 बिंदुओं से जुड़ा है।
हॉफमैन-सिंगलटन आलेख से
हॉफमैन-सिंगलटन आलेख में आकार 15 के 100 स्वतंत्र समूह (आलेख सिद्धांत) हैं। 100 संबंधित शीर्षों के साथ नवीन आलेख़ बनाएँ, और उन शीर्षों को संबद्ध करें जिनके संबंधित स्वतंत्र समूहों में पूर्णतः 0 या 8 अवयव समान हैं। परिणामी हिगमैन-सिम्स आलेख को 352 विधियों से हॉफमैन-सिंगलटन आलेख की दो प्रतियों में विभाजित किया जा सकता है।
एक घन से
000, 001, 010, ..., 111 लेबल वाले शीर्षों वाला घन लें। सभी 70 संभव 4-शीर्षों के समूह लें, और मात्र उन्हीं को बनाए रखें जिनके एक्सओआर का मूल्यांकन 000 है; 14 ऐसे 4-समूह हैं, जो 6 शीर्षों + 6 विकर्ण-आयतों + 2 समता टेट्राहेड्रा के अनुरूप हैं। यह 8 बिंदुओं पर 3- (8,4,1) कक्ष डिजाइन है, कक्ष आकार 4 के 14 कक्षों के साथ, प्रत्येक बिंदु 7 कक्षों में दिखाई देते है, बिंदुओं की प्रत्येक युग्म 3 बार दिखाई देती है, बिंदुओं का प्रत्येक तिगुना एक बार होता है। मूल 8 शीर्षों को 8 में से किसी एक में बदलें! = 40320 विधि, और प्रतिलिपि को त्यागें। शीर्षों को फिर से लेबल करने के 30 अलग-अलग विधि हैं (अर्थात, 30 अलग-अलग डिज़ाइन जो बिंदुओं के क्रमपरिवर्तन द्वारा एक दूसरे के लिए सभी समरूपी हैं)। ऐसा इसलिए है क्योंकि 1344 स्वसमाकृतिकता हैं, और 40320/1344 = 30 हैं।
30 डिज़ाइनों में से प्रत्येक के लिए और प्रत्येक डिज़ाइन की प्रत्येक पंक्ति के लिए शीर्ष बनाएँ (कुल 70 ऐसी पंक्तियाँ हैं, प्रत्येक पंक्ति 8 का 4-समूह है और 6 डिज़ाइनों में दिखाई देती है)। प्रत्येक डिज़ाइन को उसकी 14 पंक्तियों से जोड़ें। अलग-अलग डिज़ाइनों को एक दूसरे से संबद्ध करें (प्रत्येक डिज़ाइन 8 अन्य के साथ अलग है)। पंक्तियों को एक दूसरे से संबद्ध करें यदि उनके निकट सामान्य रूप से एक अवयव है (4x4 = 16 ऐसे निकटवर्ती हैं)। परिणामी आलेख हिगमैन-सिम्स आलेख है। पंक्तियाँ 16 अन्य पंक्तियों से जुड़ी हैं और 6 डिज़ाइन == डिग्री 22 से जुड़ी हैं। डिज़ाइन 14 पंक्तियों से जुड़ी हैं और 8 असंयुक्त डिज़ाइन == डिग्री 22 हैं। इस प्रकार सभी 100 कोने में डिग्री 22 है।
बीजगणितीय गुण
हिगमैन-सिम्स आलेख का स्वसमाकृतिकता समूह क्रम 88,704,000 समरूपी का एक समूह है, जो क्रम 2 के चक्रीय समूह के साथ क्रम 44,352,000 के हिगमैन-सिम्स समूह के अर्ध-प्रत्यक्ष उत्पाद के लिए है।[4] इसमें स्वसमाकृतिकता हैं जो किसी भी किनारे को किसी अन्य किनारे पर ले जाते हैं, जिससे हिगमैन-सिम्स आलेख बढ़त-संक्रमणीय आलेख बन जाते है।[5]
हिगमन-सिम्स आलेख़ का विशिष्ट बहुपद (x − 22) (x − 2) 77 (x + 8) 22 है
इसलिए, हिगमैन-सिम्स आलेख अभिन्न आलेख है: इसके वर्णक्रम आलेख सिद्धांत में पूर्ण रूप से पूर्णांक होते हैं। यह इस विशिष्ट बहुपद के साथ एकमात्र आलेख भी है, जो इसे इसके वर्णक्रम द्वारा निर्धारित आलेख बनाते है।
लीच की जालक के भीतर
हिगमैन-सिम्स आलेख स्वाभाविक रूप से लीच जालक के भीतर होते है: यदि X, Y और Z लीच जालक में तीन बिंदु हैं जैसे कि दूरी XY, XZ और YZ क्रमशः हैं, तो वस्तुतः 100 लीच जालक बिंदु T हैं जैसे कि सभी दूरियाँ XT, YT और ZT 2 के बराबर हैं, और यदि हम दो ऐसे बिंदुओं T और T' को जोड़ते हैं, जब उनके बीच की दूरी , परिणामी आलेख हिगमैन-सिम्स आलेख के लिए समरूपी है। इसके अतिरिक्त , लीच जालक के सभी स्वसमाकृतिकता का समूह (अर्थात, यूक्लिडियन सर्वांगसमताएं इसे स्थायीकर करती हैं) जो x, y और z में से प्रत्येक को ठीक करती हैं, हिगमैन-सिम्स समूह है (यदि हम x और y का आदान-प्रदान करने की अनुमति देते हैं, तो सभी का क्रम 2 विस्तार आलेख स्वसमाकृतिकता प्राप्त होता है)। इससे पता चलता है कि हिगमैन-सिम्स समूह कॉनवे समूह Co2 (इसके क्रम 2 विस्तार के साथ) और Co3 के भीतर होता है, और इसके परिणामस्वरूप Co1 भी होते है।[6]
संदर्भ
- ↑ Hafner, P. R. (2004). "On the Graphs of Hoffman–Singleton and Higman–Sims" (PDF). the Electronic Journal of Combinatorics. 11 (1): R77(1–32). doi:10.37236/1830.
{{cite journal}}: External link in|journal= - ↑ Weisstein, Eric W. "Higman–Sims Graph". MathWorld.
- ↑ Higman, Donald G.; Sims, Charles C. (1968). "A simple group of order 44,352,000" (PDF). Mathematische Zeitschrift. 105 (2): 110–113. doi:10.1007/BF01110435. hdl:2027.42/46258..
- ↑ Brouwer, Andries E. "Higman–Sims graph".
- ↑ Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397–407, 1993.
- ↑ Conway, John H.; Sloane, Neil J. A. क्षेत्र पैकिंग, जाली और समूह. Grundlehren der mathematischen Wissenschaften (3rd ed.). Springer-Verlag. ISBN 1-4419-3134-1. chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups"), pp. 292–293.
- Mesner, Dale Marsh (1956), An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types, Doctoral Thesis, Department of Statistics, Michigan State University, MR 2612633
