График игр

В теории графов граф Игр является крупнейшим известным локально линейным сильно регулярным графом . Его параметры как сильно регулярного графа равны (729,112,1,20). Это означает, что он имеет 729 вершин и 40824 ребра (112 на вершину). Каждое ребро находится в уникальном треугольнике (это локально линейный граф ), и каждая несмежная пара вершин имеет ровно 20 общих соседей. Он назван в честь Ричарда А. Геймса, который предложил его конструкцию в неопубликованном сообщении ^[1] и писал о связанных конструкциях. ^[2]

Строительство

Построение этого графа включает в себя 56-точечный набор колпачков в . Это подмножество точек без трех на одной линии в пятимерной проективной геометрии над трехэлементным полем, и является уникальным с точностью до симметрии. ^[3] Шестимерная проективная геометрия, , может быть разделена на шестимерное аффинное пространство и копию , которая образует множество точек на бесконечности относительно аффинного пространства. Граф игр имеет в качестве своих вершин 729 точек аффинного пространства . Каждая линия в аффинном пространстве проходит через три из этих точек и через четвертую точку на бесконечности. Граф содержит треугольник для каждой линии из трех аффинных точек, которая проходит через точку набора колпачков. ^[1] ${\displaystyle PG(5,3)}$ ${\displaystyle PG(6,3)}$ ${\displaystyle AG(6,3)}$ ${\displaystyle PG(5,3)}$ ${\displaystyle AG(6,3)}$

Характеристики

Несколько свойств графа немедленно вытекают из этой конструкции. Он имеет вершины, поскольку число точек в аффинном пространстве равно размеру базового поля в степени размерности. Для каждой аффинной точки существует 56 прямых, проходящих через точки множества шапок, 56 треугольников, содержащих соответствующую вершину, и соседей вершины. И не может быть никаких треугольников, кроме тех, которые возникают из конструкции, поскольку любой другой треугольник должен был бы происходить из трех различных прямых, встречающихся в общей плоскости , и три точки множества шапок трех линий все лежали бы на пересечении этой плоскости с , что является прямой. Но это нарушило бы определяющее свойство множества шапок, что оно не имеет трех точек на прямой, поэтому такой дополнительный треугольник не может существовать. Оставшееся свойство строго регулярных графов, что все несмежные пары точек имеют одинаковое количество общих соседей, зависит от конкретных свойств 5-мерного множества шапок. ${\displaystyle 729=3^{6}}$ ${\displaystyle 112=56\times 2}$ ${\displaystyle PG(6,3)}$ ${\displaystyle PG(5,3)}$

Связанные графики

Вместе с графом Рукса и графом Брауэра–Хемерса граф Геймса является одним из трех возможных сильно регулярных графов, параметры которых имеют вид . ^[4] ${\displaystyle 3\times 3}$ ${\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}$

Те же свойства, которые создают строго регулярный граф из набора крышек, можно использовать и с 11-точечным набором крышек в , создавая меньший строго регулярный граф с параметрами (243,22,1,2). ^[5] Этот граф является графом Берлекэмпа–Ван Линта–Зейделя . ^[6] ${\displaystyle PG(4,3)}$

Ссылки

1. van Lint, JH ; Brouwer, AE (1984), "Строго регулярные графы и частичные геометрии" (PDF) , в Jackson, David M. ; Vanstone, Scott A. (ред.), Enumeration and Design: Papers from the conference on combinatorics performed at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982 , London: Academic Press, pp. 85–122, MR  0782310. См. в частности стр. 114–115.
2. Игры, Ричард А. (1983), «Проблема упаковки проективных геометрий над GF(3) с размерностью больше пяти», Журнал комбинаторной теории , Серия A, 35 (2): 126–144, doi : 10.1016/0097-3165(83)90002-X , MR  0712100. См., в частности, Таблицу VII, стр. 139, запись для и . ${\displaystyle r=5}$ ${\displaystyle d=3}$
3. Хилл, Рэймонд (1978), «Caps and codes», Discrete Mathematics , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR  0523299
4. Бондаренко, Андрей В.; Радченко, Данил В. (2013), «О семействе сильно регулярных графов с », Журнал комбинаторной теории , Серия B, 103 (4): 521–531, arXiv : 1201.0383 , doi : 10.1016/j.jctb.2013.05.005, MR  3071380 ${\displaystyle \lambda =1}$
5. Кэмерон, Питер Дж. (1975), «Частичные четырехугольники», The Quarterly Journal of Mathematics , Вторая серия, 26 : 61–73, doi : 10.1093/qmath/26.1.61, MR  0366702
6. Берлекамп, Э. Р .; ван Линт, Дж. Х .; Зайдель, Дж. Дж. (1973), «Строго регулярный граф, полученный из совершенного троичного кода Голея», Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Амстердам: Северная Голландия: 25–30, doi : 10.1016/B978-0-7204-2262-7.50008-9, ISBN 9780720422627, МР  0364015