Граф Брауэра — Хемерса

Граф Брауэра — Хемерса имеет несколько связанных алгебраических построений. Одно из самых простых построений — как обобщённый граф Пэли порядка 4. Его можно определить путём выбора каждой вершины из конечного поля ${\displaystyle GF(81)}$, а в качества рёбер берутся каждые два элемента, отличающиеся на четвёртую степень[1][2].

Граф Брауэра — Хемерса является единственным сильно регулярным графом с параметрами (81, 20, 1, 6). Это озаначает, что он имеет 81 вершину, 20 рёбер на вершину, 1 треугольник на ребро и путь, соединяющий каждые две несмежные вершины имеет длину 6[3]. Как сильно регулярный граф с третьим параметром 1, граф Брауэра — Хемерса обладает свойством, что любое ребро принадлежит единственному треугольнику. То есть он локально линеен. Поиск больших плотных графов с этим свойством является одной из формулировок проблемы Ружи — Семереди[4].

Будучи строго регулярным, граф дистанционно-транзитивен[5].

Хотя Брауэр писал, что построения этого графа является «фольклорным» и цитировал раннюю статью 1964 года по латинским квадратам Дейла М. Меснера[1], граф назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые в 1992 году опубликовали доказательство, что он единственный строго регулярный граф с такими параметрами[3].

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

Граф следует отличать от графа судоку, другого 20-регулярного графа с 81 вершиной. Граф судоку получается из головоломки Судоку, если разместить вершину в каждой ячейке судоку и соединить рёбрами вершины, которые находятся в той же строке, в том же столбце или ${\displaystyle 3\times 3}$ блоке головоломки. Граф имеет много клик с 9 вершинами и требует 9 цветов для любой раскраски. Раскраска в 9 цветов этого графа описывает решение головоломки судоку[7][8]. В качестве контраста, в графе Брауэра — Хемерса наибольшими кликами являются треугольники и для раскраски нужно лишь 7 цветов[5].