Граф Геймса
Граф Геймса — це найбільший із відомих локально лінійних сильно регулярних графів. Його параметри як сильно регулярного графа рівні (729,112,1,20). Це означає, що граф має 729 вершин та 40824 ребер (112 ребер на вершину). Кожне ребро належить єдиному трикутнику (це локально лінійний граф) і кожна несуміжна пара вершин має рівно 20 спільних сусідів. Граф названо ім'ям Річарда А. Геймса, який у неопублікованому листуванні запропонував його побудову[1] і написав про пов'язані побудови[2] .
Побудова цього графа використовує єдину (з точністю до симетрії) 56-точкову множину-ковпак[en] (англ. cap set, підмножина точок, ніякі три з яких не лежать на одній прямій) , п'ятивимірної проєктивної геометрії над триелементним полем[3]. Шестивимірну проєктивну геометрію, , можна розбити на шестивимірний афінний простір та копію (точки на нескінченності з урахуванням афінного простору). Граф Геймса має як вершини 729 точок афінного простору . Кожна пряма в афінному просторі проходить через три з цих точок і четверту нескінченно віддалену точку. Граф містить трикутник для будь-якої прямої з трьох афінних точок, яка проходить через точку множини-ковпака[1].
Деякі з властивостей графа випливають безпосередньо з побудови. Граф має вершин, оскільки кількість точок у афінному просторі дорівнює розміру базового поля в степені розмірності. Для кожної афінної точки існує 56 прямих через точки множини-ковпака, 56 трикутників, що містять відповідну вершину, та сусідів вершини. І не може бути ніяких трикутників, відмінних від отриманих при побудові, оскільки будь-який інший трикутник отримувався би з трьох різних прямих, що перетинаються в спільній площині , а три точки множини-ковпака трьох прямих лежали б на перетині цієї площини з , що дає пряму. Однак це порушило би властивість множини-ковпака, що ніякі три точки не лежать на одній прямій, так що ніякого додаткового трикутника існувати не може. Властивість сильної регулярності графів, що всі несуміжні пари вершин мають однакову кількість спільних сусідів, залежить від властивостей 5-вимірної множини-ковпака.
Разом із туровим графом і графом Брауера — Хемерса, граф Геймса є одним з трьох можливих сильно регулярних графів, параметри якого мають вигляд [4].
Ті ж властивості, які дають сильно регулярний граф із множини-ковпака, можна використати з 11-точковою множиною-ковпаком у , яка дає найменший регулярний граф із параметрами (243,22,1,2)[5]. Це граф граф Берлекемпа — ван Лінта — Зейделя[6].
- ↑ а б 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.
- ↑ Richard A. Games. The packing problem for projective geometries over GF(3) with dimension greater than five // Journal of Combinatorial Theory. — 1983. — Т. 35, вип. 2. — С. 126–144. — DOI:10.1016/0097-3165(83)90002-X.. Див., зокрема, таблицю VII, стор. 139, рядки і .
- ↑ Raymond Hill. Caps and codes // Discrete Mathematics. — 1978. — Т. 22, вип. 2. — С. 111–137. — DOI:10.1016/0012-365X(78)90120-6.
- ↑ Bondarenko Andriy V., Radchenko Danylo V. On a family of strongly regular graphs with // Journal of Combinatorial Theory. — 2013. — Т. 103, вип. 4. — С. 521–531. — DOI:10.1016/j.jctb.2013.05.005.
- ↑ Peter J. Cameron. Partial quadrangles // The Quarterly Journal of Mathematics. — 1975. — Т. 26. — С. 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. — С. 25–30. — DOI:10.1016/B978-0-7204-2262-7.50008-9.
