Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық графтар теориясында Хигман-Симс графы — 100 төбесі және 1100 қабырғасы бар 22-реттік бағытталмаған граф. Бұл бірегей берік реттелген граф srg(100,22,0,6), онда ешбір көршілес төбелер жұбы ортақ көршіге ие емес, ал көршілес емес төбелер жұбы алты ортақ көршіге ие. Ол алғаш рет Дональд Г. Хигман және Чарльз С. Симс 1968 жылы Хоффман-Синглтон графының автоморфизмдер тобындағы екілік индекске ие кіші топ — Хигман-Симс тобын анықтау үшін құрастырылып, қайтадан ашылды.
In mathematical graph theory, the Higman–Sims graph is a 22 regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Hoffman–Singleton graph.
M22 графигінен
M22 графигін, күшті тұрақты srg(77,16,0,4) графигін алыңыз және оны S(3,6,22) нүктелеріне сәйкес келетін 22 жаңа төбемен толықтырыңыз, әр блок өзінің нүктелеріне қосылсын, сондай-ақ 22 нүктеге жалғанған қосымша C төбесі де болсын.
Take the M22 graph, a strongly regular graph srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex C connected to the 22 points.
Хоффман-Синглтон графигінен
Хоффман-Синглтон графигінде 15 өлшемді 100 тәуелсіз жиынтық бар. 100 сәйкес келетін төбесі бар жаңа графикті құрыңыз, және сәйкес келетін тәуелсіз жиынтықтарының дәл 0 немесе 8 элементі ортақ болатын төбелерді қосыңыз. Нәтижесінде алынған Хигман-Симс графигін Хоффман-Синглтон графигінің екі көшірмесіне 352 тәсілмен бөлуге болады.
There are 100 independent sets of size 15 in the Hoffman–Singleton graph. Create a new graph with 100 corresponding vertices, and connect vertices whose corresponding independent sets have exactly 0 or 8 elements in common. The resulting Higman–Sims graph can be partitioned into two copies of the Hoffman–Singleton graph in 352 ways.
Кекседен
000, 001, 010, 111 деп белгіленген төбелері бар куб алыңыз. Барлық 70 мүмкін 4 төбелік жиынды қарастырыңыз және XOR-і 000-ға тең болатын жиындарды ғана сақтап қалыңыз; мұндай 4 жиынның 14-і бар, олар 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 дәрежеге ие.
Take a cube with vertices labeled 000, 001, 010, , 111. Take all 70 possible 4 sets of vertices, and retain only the ones whose XOR evaluates to 000; there are 14 such 4 sets, corresponding to the 6 faces + 6 diagonal rectangles + 2 parity tetrahedra. This is a 3 (8,4,1) block design on 8 points, with 14 blocks of block size 4, each point appearing in 7 blocks, each pair of points appearing 3 times, each triplet of points occurring exactly once. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices (i. e., 30 different designs that are all isomorphic to each other by permutation of the points). This is because there are 1344 automorphisms, and 40320/1344 = 30. Create a vertex for each of the 30 designs, and for each row of every design (there are 70 such rows in total, each row being a 4 set of 8 and appearing in 6 designs). Connect each design to its 14 rows. Connect disjoint designs to each other (each design is disjoint with 8 others). Connect rows to each other if they have exactly one element in common (there are 4x4 = 16 such neighbors). The resulting graph is the Higman–Sims graph. Rows are connected to 16 other rows and to 6 designs == degree 22. Designs are connected to 14 rows and 8 disjoint designs == degree 22. Thus all 100 vertices have degree 22 each.
Алгебралық қасиеттер
Хигман-Симс графигінің автоморфизм тобы – Хигман-Симс тобының 2-реттік циклдік топпен жартылай тура көбейтіндісіне изоморфты топ. Ол кез келген қабырғаны кез келген басқа қабырғаға жіберуге мүмкіндік беретін автоморфизмдерге ие, бұл Хигман-Симс графигін қабырғалық транзитивті график етеді. Сыртқы элементтер графикте жұп емес орналасуларды тудырады. Жоғарыда айтылғандай, Хигман-Симс графигін Хоффман-Синглтон графиктерінің жұбына бөлудің 352 тәсілі бар; бұл бөлімдер іс жүзінде әрқайсысы 176 өлшемді 2 орбита түрінде келеді, ал Хигман-Симс тобының сыртқы элементтері осы орбиталарды ауыстырады. Хигман-Симс графигінің сипаттамалық полиномы (x – 22)(x – 2)⁷⁷(x + 8)²². Демек, Хигман-Симс графигі интегралды график болып табылады: оның спектрі толығымен бүтін сандардан тұрады. Бұл сонымен қатар осы сипаттамалық полиномға ие жалғыз график, оны спектрімен анықталатын график етеді.
The automorphism group of the Higman–Sims graph is a group of order isomorphic to the semidirect product of the Higman–Sims group of order with the cyclic group of order 2. It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an edge transitive graph. The outer elements induce odd permutations on the graph. As mentioned above, there are 352 ways to partition the Higman–Sims graph into a pair of Hoffman–Singleton graphs; these partitions actually come in 2 orbits of size 176 each, and the outer elements of the Higman–Sims group swap these orbits. The characteristic polynomial of the Higman–Sims graph is (x − 22)(x − 2)77(x + 8)22. Therefore, the Higman–Sims graph is an integral graph: its spectrum consists entirely of integers. It is also the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Сырғанақ тордың ішінде
Хигман-Симс графигі Лич торында табиғи түрде кездеседі: егер X, Y және Z Лич торындағы үш нүкте болса және XY, XZ және YZ арақашықтықтары сәйкесінше болса, онда дәл 100 Лич торының нүктелері T бар, мұнда барлық арақашықтықтар XT, YT және ZT 2-ге тең. Егер біз осы екі нүктені T және T' деп қосып, олардың арақашықтығы болса, нәтижедегі граф Хигман-Симс графигімен изоморфты болады. Сонымен қатар, X, Y және Z-дің әрқайсысын бекітетін Лич торының барлық автоморфизмдерінің жиынтығы (яғни, оны бекітетін Евклидтік конгруэнциялар) Хигман-Симс тобын құрайды (егер X және Y-ті алмастыруға рұқсат етілсе, барлық граф автоморфизмдерінің 2-реттік кеңейтілуі алынады). Бұл Хигман-Симс тобының Конуэй топтарының ішінде Co2 (оның 2-реттік кеңейтімімен) және Co3-те, сондай-ақ Co1-де кездесетінін көрсетеді.
The Higman–Sims graph naturally occurs inside the Leech lattice: if X, Y and Z are three points in the Leech lattice such that the distances XY, XZ and YZ are respectively, then there are exactly 100 Leech lattice points T such that all the distances XT, YT and ZT are equal to 2, and if we connect two such points T and T′ when the distance between them is , the resulting graph is isomorphic to the Higman–Sims graph. Furthermore, the set of all automorphisms of the Leech lattice (that is, Euclidean congruences fixing it) which fix each of X, Y and Z is the Higman–Sims group (if we allow exchanging X and Y, the order 2 extension of all graph automorphisms is obtained). This shows that the Higman–Sims group occurs inside the Conway groups Co2 (with its order 2 extension) and Co3, and consequently also Co1.