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

Граф Брауэра — Хемерса
Вершин	81
Рёбер	810
Диаметр	2
Обхват	3
Автоморфизмы	233280
Хроматическое число	7
Свойства	сильно регулярный дистанционно-транзитивный граф Рамануджана локально линейный
Медиафайлы на Викискладе

Граф Брауэра — Хемерса — 20-регулярный неориентированный граф с 81 вершиной и 810 рёбрами. Это сильно регулярный, дистанционно-транзитивный граф и граф Рамануджана. Хотя его построение является математическим фольклором, он был назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые доказали его единственность в качестве строго регулярного графа.

Построение

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

Свойства

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

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

История

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

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

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

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