Граф Геймса

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

Построение

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

Свойства

Некоторые из свойств графа следуют немедленно из построения. Граф имеет $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 )}$.

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