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

Граф Брауэра — Хемерса имеет несколько связанных алгебраических построений. Одно из самых простых построений — как обобщённый граф Пэли порядка 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].