हिगमैन-सिम्स ग्राफ

From Vigyanwiki
Revision as of 17:21, 17 May 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Higman–Sims graph
Higman Sims Graph.svg
Drawing based on Paul R. Hafner's construction.[1]
Named afterDonald G. Higman
Charles C. Sims
Vertices100
Edges1100
Radius2
Diameter2
Girth4
Automorphisms88,704,000 (HS:2)
PropertiesStrongly 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]


संदर्भ

  1. 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= (help).
  2. Weisstein, Eric W. "Higman–Sims Graph". MathWorld.
  3. 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..
  4. Brouwer, Andries E. "Higman–Sims graph".
  5. 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.
  6. 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