हिगमैन-सिम्स ग्राफ
| 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 किनारे हैं। यह अद्वितीय दृढ़ता से नियमित ग्राफ srg (100,22,0,6) है, जहां कोई भी पड़ोसी जोड़ी एक सामान्य पड़ोसी को साझा नहीं करती है और प्रत्येक गैर-पड़ोसी जोड़ी के कोने छह आम पड़ोसियों को साझा करते हैं।[2] इसका निर्माण सर्वप्रथम द्वारा किया गया था Mesner (1956) और 1968 में डोनाल्ड जी. हिगमैन और चार्ल्स सी. सिम्स द्वारा हिगमैन-सिम्स समूह को परिभाषित करने के तरीके के रूप में फिर से खोजा गया, हिगमैन-सिम्स ग्राफ के ऑटोमोर्फिज्म के समूह में एक उपसमूह दो के सूचकांक का एक उपसमूह।[3]
निर्माण
M22 ग्राफ से
M22 ग्राफ लें, एक दृढ़ता से नियमित ग्राफ srg(77,16,0,4) और इसे S(3,6,22) के बिंदुओं के अनुरूप 22 नए शीर्षों के साथ बढ़ाएं, प्रत्येक ब्लॉक को इसके बिंदुओं से जोड़ा जा रहा है, और एक अतिरिक्त शीर्ष C 22 बिंदुओं से जुड़ा है।
हॉफमैन-सिंगलटन ग्राफ से
हॉफमैन-सिंगलटन ग्राफ में आकार 15 के 100 स्वतंत्र सेट (ग्राफ सिद्धांत) हैं। 100 संबंधित शीर्षों के साथ एक नया ग्राफ़ बनाएँ, और उन शीर्षों को कनेक्ट करें जिनके संबंधित स्वतंत्र सेटों में बिल्कुल 0 या 8 तत्व समान हैं। परिणामी हिगमैन-सिम्स ग्राफ को 352 तरीकों से हॉफमैन-सिंगलटन ग्राफ की दो प्रतियों में विभाजित किया जा सकता है।
एक घन से
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 डिज़ाइनों में से प्रत्येक के लिए और प्रत्येक डिज़ाइन की प्रत्येक पंक्ति के लिए एक शीर्ष बनाएँ (कुल 70 ऐसी पंक्तियाँ हैं, प्रत्येक पंक्ति 8 का 4-सेट है और 6 डिज़ाइनों में दिखाई देती है)। प्रत्येक डिज़ाइन को उसकी 14 पंक्तियों से जोड़ें। अलग-अलग डिज़ाइनों को एक दूसरे से कनेक्ट करें (प्रत्येक डिज़ाइन 8 अन्य के साथ अलग है)। पंक्तियों को एक दूसरे से कनेक्ट करें यदि उनके पास सामान्य रूप से एक तत्व है (4x4 = 16 ऐसे पड़ोसी हैं)। परिणामी ग्राफ हिगमैन-सिम्स ग्राफ है। पंक्तियाँ 16 अन्य पंक्तियों से जुड़ी हैं और 6 डिज़ाइन == डिग्री 22 से जुड़ी हैं। डिज़ाइन 14 पंक्तियों से जुड़ी हैं और 8 असंयुक्त डिज़ाइन == डिग्री 22 हैं। इस प्रकार सभी 100 कोने में डिग्री 22 है।
बीजगणितीय गुण
हिगमैन-सिम्स ग्राफ का ऑटोमोर्फिज्म समूह क्रम का एक समूह है 88,704,000 ऑर्डर के हिगमैन-सिम्स समूह के अर्ध-प्रत्यक्ष उत्पाद के लिए आइसोमोर्फिक 44,352,000 ऑर्डर 2 के चक्रीय समूह के साथ।[4] इसमें ऑटोमोर्फिज़्म हैं जो किसी भी किनारे को किसी अन्य किनारे पर ले जाते हैं, जिससे हिगमैन-सिम्स ग्राफ एक बढ़त-संक्रमणीय ग्राफ बन जाता है।[5] हिगमन-सिम्स ग्राफ़ का विशिष्ट बहुपद है (x − 22)(x − 2)77(x + 8)22</उप>। इसलिए, हिगमैन-सिम्स ग्राफ एक अभिन्न ग्राफ है: इसके स्पेक्ट्रल ग्राफ सिद्धांत में पूरी तरह से पूर्णांक होते हैं। यह इस विशिष्ट बहुपद के साथ एकमात्र ग्राफ भी है, जो इसे इसके स्पेक्ट्रम द्वारा निर्धारित ग्राफ बनाता है।
जोंक की जाली के अंदर
हिगमैन-सिम्स ग्राफ स्वाभाविक रूप से हिगमैन-सिम्स समूह # ए हिगमैन-सिम्स ग्राफ जोंक जाली के अंदर: यदि X, Y और Z जोंक जाली में तीन बिंदु हैं जैसे कि दूरी XY, XZ और YZ हैं क्रमशः, तो ठीक 100 लीच जाली बिंदु T हैं जैसे कि सभी दूरियाँ XT, YT और ZT 2 के बराबर हैं, और यदि हम दो ऐसे बिंदुओं T और T' को जोड़ते हैं, जब उनके बीच की दूरी है , परिणामी ग्राफ हिगमैन-सिम्स ग्राफ के लिए आइसोमोर्फिक है। इसके अलावा, जोंक जाली के सभी ऑटोमोर्फिम्स का सेट (अर्थात, यूक्लिडियन सर्वांगसमताएं इसे फिक्सिंग करती हैं) जो एक्स, वाई और जेड में से प्रत्येक को ठीक करती हैं, हिगमैन-सिम्स समूह है (यदि हम एक्स और वाई का आदान-प्रदान करने की अनुमति देते हैं, तो सभी का क्रम 2 विस्तार ग्राफ ऑटोमोर्फिज्म प्राप्त होता है)। इससे पता चलता है कि हिगमैन-सिम्स समूह कॉनवे समूह कंपनी के अंदर होता है2 (इसके ऑर्डर 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
