Граф Геймса

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

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

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

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

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

Эта страница в последний раз была отредактирована 15 апреля 2019 в 18:17.