Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Геймса це найбільший із відомих локально лінійних сильно регулярних графів Його параметри як сильно регулярного гра

Граф Геймса

Граф Геймса

Граф Геймса — це найбільший із відомих локально лінійних сильно регулярних графів. Його параметри як сильно регулярного графа рівні (729,112,1,20). Це означає, що граф має 729 вершин та 40824 ребер (112 ребер на вершину). Кожне ребро належить єдиному трикутнику (це локально лінійний граф) і кожна несуміжна пара вершин має рівно 20 спільних сусідів. Граф названо ім'ям Річарда А. Геймса, який у неопублікованому листуванні запропонував його побудову і написав про пов'язані побудови .

Побудова

Побудова цього графа використовує єдину (з точністю до симетрії) 56-точкову [en] (англ. cap set, підмножина точок, ніякі три з яких не лежать на одній прямій) image, п'ятивимірної проєктивної геометрії над триелементним полем. Шестивимірну проєктивну геометрію, image, можна розбити на шестивимірний афінний простір image та копію image (точки на нескінченності з урахуванням афінного простору). Граф Геймса має як вершини 729 точок афінного простору image. Кожна пряма в афінному просторі проходить через три з цих точок і четверту нескінченно віддалену точку. Граф містить трикутник для будь-якої прямої з трьох афінних точок, яка проходить через точку множини-ковпака.

Властивості

Деякі з властивостей графа випливають безпосередньо з побудови. Граф має image вершин, оскільки кількість точок у афінному просторі дорівнює розміру базового поля в степені розмірності. Для кожної афінної точки існує 56 прямих через точки множини-ковпака, 56 трикутників, що містять відповідну вершину, та image сусідів вершини. І не може бути ніяких трикутників, відмінних від отриманих при побудові, оскільки будь-який інший трикутник отримувався би з трьох різних прямих, що перетинаються в спільній площині image, а три точки множини-ковпака трьох прямих лежали б на перетині цієї площини з image, що дає пряму. Однак це порушило би властивість множини-ковпака, що ніякі три точки не лежать на одній прямій, так що ніякого додаткового трикутника існувати не може. Властивість сильної регулярності графів, що всі несуміжні пари вершин мають однакову кількість спільних сусідів, залежить від властивостей 5-вимірної множини-ковпака.

Пов'язані графи

Разом із туровим графом image і графом Брауера — Хемерса, граф Геймса є одним з трьох можливих сильно регулярних графів, параметри якого мають вигляд image.

Ті ж властивості, які дають сильно регулярний граф із множини-ковпака, можна використати з 11-точковою множиною-ковпаком у image, яка дає найменший регулярний граф із параметрами (243,22,1,2). Це граф граф Берлекемпа — ван Лінта — Зейделя.

Примітки

  1. van Lint J. H., Brouwer A. E. Strongly regular graphs and partial geometries // Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982 / David M. Jackson, Scott A. Vanstone. — London : Academic Press, 1984. — С. 85–122.. Див., зокрема, стор. 114—115.
  2. Richard A. Games. The packing problem for projective geometries over GF(3) with dimension greater than five // . — 1983. — Т. 35, вип. 2. — С. 126–144. — DOI:10.1016/0097-3165(83)90002-X.. Див., зокрема, таблицю VII, стор. 139, рядки image і image.
  3. Raymond Hill. Caps and codes // . — 1978. — Т. 22, вип. 2. — С. 111–137. — DOI:10.1016/0012-365X(78)90120-6.
  4. Bondarenko Andriy V., Radchenko Danylo V. On a family of strongly regular graphs with image // . — 2013. — Т. 103, вип. 4. — С. 521–531. — DOI:10.1016/j.jctb.2013.05.005.
  5. Peter J. Cameron. Partial quadrangles // The Quarterly Journal of Mathematics. — 1975. — Т. 26. — С. 61–73. — DOI:10.1093/qmath/26.1.61.
  6. Berlekamp E. R., van Lint J. H., Seidel J. J. A strongly regular graph derived from the perfect ternary Golay code // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). — Amsterdam : North-Holland, 1973. — С. 25–30. — DOI:10.1016/B978-0-7204-2262-7.50008-9.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graf Gejmsa ce najbilshij iz vidomih lokalno linijnih silno regulyarnih grafiv Jogo parametri yak silno regulyarnogo grafa rivni 729 112 1 20 Ce oznachaye sho graf maye 729 vershin ta 40824 reber 112 reber na vershinu Kozhne rebro nalezhit yedinomu trikutniku ce lokalno linijnij graf i kozhna nesumizhna para vershin maye rivno 20 spilnih susidiv Graf nazvano im yam Richarda A Gejmsa yakij u neopublikovanomu listuvanni zaproponuvav jogo pobudovu i napisav pro pov yazani pobudovi PobudovaPobudova cogo grafa vikoristovuye yedinu z tochnistyu do simetriyi 56 tochkovu en angl cap set pidmnozhina tochok niyaki tri z yakih ne lezhat na odnij pryamij PG 5 3 displaystyle PG 5 3 p yativimirnoyi proyektivnoyi geometriyi nad trielementnim polem Shestivimirnu proyektivnu geometriyu PG 6 3 displaystyle PG 6 3 mozhna rozbiti na shestivimirnij afinnij prostir AG 6 3 displaystyle AG 6 3 ta kopiyu PG 5 3 displaystyle PG 5 3 tochki na neskinchennosti z urahuvannyam afinnogo prostoru Graf Gejmsa maye yak vershini 729 tochok afinnogo prostoru AG 6 3 displaystyle AG 6 3 Kozhna pryama v afinnomu prostori prohodit cherez tri z cih tochok i chetvertu neskinchenno viddalenu tochku Graf mistit trikutnik dlya bud yakoyi pryamoyi z troh afinnih tochok yaka prohodit cherez tochku mnozhini kovpaka VlastivostiDeyaki z vlastivostej grafa viplivayut bezposeredno z pobudovi Graf maye 729 36 displaystyle 729 3 6 vershin oskilki kilkist tochok u afinnomu prostori dorivnyuye rozmiru bazovogo polya v stepeni rozmirnosti Dlya kozhnoyi afinnoyi tochki isnuye 56 pryamih cherez tochki mnozhini kovpaka 56 trikutnikiv sho mistyat vidpovidnu vershinu ta 112 56 2 displaystyle 112 56 times 2 susidiv vershini I ne mozhe buti niyakih trikutnikiv vidminnih vid otrimanih pri pobudovi oskilki bud yakij inshij trikutnik otrimuvavsya bi z troh riznih pryamih sho peretinayutsya v spilnij ploshini PG 6 3 displaystyle PG 6 3 a tri tochki mnozhini kovpaka troh pryamih lezhali b na peretini ciyeyi ploshini z PG 5 3 displaystyle PG 5 3 sho daye pryamu Odnak ce porushilo bi vlastivist mnozhini kovpaka sho niyaki tri tochki ne lezhat na odnij pryamij tak sho niyakogo dodatkovogo trikutnika isnuvati ne mozhe Vlastivist silnoyi regulyarnosti grafiv sho vsi nesumizhni pari vershin mayut odnakovu kilkist spilnih susidiv zalezhit vid vlastivostej 5 vimirnoyi mnozhini kovpaka Pov yazani grafiRazom iz turovim grafom 3 3 displaystyle 3 times 3 i grafom Brauera Hemersa graf Gejmsa ye odnim z troh mozhlivih silno regulyarnih grafiv parametri yakogo mayut viglyad n2 3n 1 2 n2 n 3 1 n n 1 displaystyle bigl n 2 3n 1 2 n 2 n 3 1 n n 1 bigr Ti zh vlastivosti yaki dayut silno regulyarnij graf iz mnozhini kovpaka mozhna vikoristati z 11 tochkovoyu mnozhinoyu kovpakom u PG 4 3 displaystyle PG 4 3 yaka daye najmenshij regulyarnij graf iz parametrami 243 22 1 2 Ce graf graf Berlekempa van Linta Zejdelya Primitkivan Lint J H Brouwer A E Strongly regular graphs and partial geometries Enumeration and Design Papers from the conference on combinatorics held at the University of Waterloo Waterloo Ont June 14 July 2 1982 David M Jackson Scott A Vanstone London Academic Press 1984 S 85 122 Div zokrema stor 114 115 Richard A Games The packing problem for projective geometries over GF 3 with dimension greater than five 1983 T 35 vip 2 S 126 144 DOI 10 1016 0097 3165 83 90002 X Div zokrema tablicyu VII stor 139 ryadki r 5 displaystyle r 5 i d 3 displaystyle d 3 Raymond Hill Caps and codes 1978 T 22 vip 2 S 111 137 DOI 10 1016 0012 365X 78 90120 6 Bondarenko Andriy V Radchenko Danylo V On a family of strongly regular graphs with l 1 displaystyle lambda 1 2013 T 103 vip 4 S 521 531 DOI 10 1016 j jctb 2013 05 005 Peter J Cameron Partial quadrangles The Quarterly Journal of Mathematics 1975 T 26 S 61 73 DOI 10 1093 qmath 26 1 61 Berlekamp E R van Lint J H Seidel J J A strongly regular graph derived from the perfect ternary Golay code A survey of combinatorial theory Proc Internat Sympos Colorado State Univ Fort Collins Colo 1971 Amsterdam North Holland 1973 S 25 30 DOI 10 1016 B978 0 7204 2262 7 50008 9

Дата публікації:
Топ