График игр

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

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

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

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

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

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

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

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

Ссылки

↑ Перейти обратно: Перейти обратно: ^а ^б ван Линт, Дж. Х .; Брауэр, А.Е. (1984), «Строго регулярные графы и частичная геометрия» (PDF) , в Джексоне, Дэвид М .; Ванстон, Скотт А. (ред.), Перечисление и проектирование: материалы конференции по комбинаторике, состоявшейся в Университете Ватерлоо, Ватерлоо, Онтарио, 14 июня – 2 июля 1982 г. , Лондон: Academic Press, стр. 85–122. , МР 0782310 . См., в частности, стр. 114–115.
^ Геймс, Ричард А. (1983), «Проблема упаковки проективных геометрий над GF (3) с размерностью больше пяти», Журнал комбинаторной теории , серия A, 35 (2): 126–144, doi : 10.1016/0097 -3165(83)90002-Х , МР 0712100 . См., в частности, Таблицу VII, с. 139, вход для $r=5$ и $d=3$ .
^ Хилл, Рэймонд (1978), «Шапики и коды», Дискретная математика , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR 0523299
^ Бондаренко Андрей В.; Радченко Даниил В. (2013), "Об одном семействе сильно регулярных графов с $\lambda =1$ ", Журнал комбинаторной теории , серия B, 103 (4): 521–531, arXiv : 1201.0383 , doi : 10.1016/j.jctb.2013.05.005 , MR 3071380
^ Кэмерон, Питер Дж. (1975), «Частичные четырехугольники», Ежеквартальный журнал математики , вторая серия, 26 : 61–73, doi : 10.1093/qmath/26.1.61 , MR 0366702
^ Берлекамп, ER ; ван Линт, Дж. Х .; Зайдель, Дж. Дж. (1973), «Сильно регулярный граф, полученный из идеального троичного кода Голея» , Обзор комбинаторной теории (Proc. Internat. Sympos., Университет штата Колорадо, Форт-Коллинз, Колорадо, 1971) , Амстердам: Северная Голландия: 25–30, номер doi : 10.1016/B978-0-7204-2262-7.50008-9 , ISBN. 9780720422627 , МР 0364015

[vlb-1] Перейти обратно: Перейти обратно: ^а ^б ван Линт, Дж. Х .; Брауэр, А.Е. (1984), «Строго регулярные графы и частичная геометрия» (PDF) , в Джексоне, Дэвид М .; Ванстон, Скотт А. (ред.), Перечисление и проектирование: материалы конференции по комбинаторике, состоявшейся в Университете Ватерлоо, Ватерлоо, Онтарио, 14 июня – 2 июля 1982 г. , Лондон: Academic Press, стр. 85–122. , МР 0782310 . См., в частности, стр. 114–115.

[g-2] Геймс, Ричард А. (1983), «Проблема упаковки проективных геометрий над GF (3) с размерностью больше пяти», Журнал комбинаторной теории , серия A, 35 (2): 126–144, doi : 10.1016/0097 -3165(83)90002-Х , МР 0712100 . См., в частности, Таблицу VII, с. 139, вход для $r=5$ и $d=3$ .

[h-3] Хилл, Рэймонд (1978), «Шапики и коды», Дискретная математика , 22 (2): 111–137, doi : 10.1016/0012-365X(78)90120-6 , MR 0523299

[br-4] Бондаренко Андрей В.; Радченко Даниил В. (2013), "Об одном семействе сильно регулярных графов с $\lambda =1$ ", Журнал комбинаторной теории , серия B, 103 (4): 521–531, arXiv : 1201.0383 , doi : 10.1016/j.jctb.2013.05.005 , MR 3071380

[c-5] Кэмерон, Питер Дж. (1975), «Частичные четырехугольники», Ежеквартальный журнал математики , вторая серия, 26 : 61–73, doi : 10.1093/qmath/26.1.61 , MR 0366702

[bvls-6] Берлекамп, ER ; ван Линт, Дж. Х .; Зайдель, Дж. Дж. (1973), «Сильно регулярный граф, полученный из идеального троичного кода Голея» , Обзор комбинаторной теории (Proc. Internat. Sympos., Университет штата Колорадо, Форт-Коллинз, Колорадо, 1971) , Амстердам: Северная Голландия: 25–30, номер doi : 10.1016/B978-0-7204-2262-7.50008-9 , ISBN. 9780720422627 , МР 0364015

[1]

[2]

[3]

[4]

[5]

[6]