Граф Брауера — Хемерса — 20-регулярний неорієнтований граф з 81 вершиною та 810 ребрами. Це сильно регулярний, дистанційно-транзитивний граф та граф Рамануджана. Хоча його побудова є математичним фольклором, граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які довели його єдиність як строго регулярного графа.
Побудова Граф Брауера — Хемерса має кілька пов'язаних алгебричних побудов. Одна з найпростіших побудов — як узагальненого графа Пелі порядку 4. Його можна визначити вибором кожної вершини зі скінченного поля , а як ребра беруться кожні два елементи, що відрізняються на четвертий степінь.
Властивості Граф Брауера — Хемерса є єдиним регулярним графом з параметрами (81, 20, 1, 6). Це означає, що він має 81 вершину, 20 ребер на вершину, 1 трикутник на ребро і шлях, що з'єднує кожні дві несуміжні вершини, має довжину 6. Як регулярний граф із третім параметром 1, граф Брауера — Хемерса має властивість, що будь-яке ребро належить єдиному трикутнику. Тобто він локально лінійний. Пошук великих щільних графів із цією властивістю є одним із формулювань проблеми Ружі — Семереді.
Як строго регулярний, граф є дистанційно-транзитивним.
Історія Хоча Брауер писав, що побудова цього графа є «фольклором» і цитував ранню статтю 1964 року про латинські квадрати Дейла М. Меснера, граф названо іменами Андреаса Брауера та Вілема Х. Хемерса, які 1992 року опублікували доведення, того, що це єдиний строго регулярний граф із такими параметрами.
Пов'язані графи Граф Брауера — Хемерса є першим у нескінченному сімействі графів Рамануджана, визначених як узагальнення графів Пелі над полем характеристики 3. Разом із туровим графом і графом Геймса він є одним із трьох можливих сильно регулярних графів, параметри яких мають вигляд .
Граф слід відрізняти від графа судоку, іншого 20-регулярного графа з 81 вершиною. Граф судоку виходить із головоломки судоку, якщо розмістити вершину в кожній комірці судоку і з'єднати ребрами вершини, розташовані в тому ж рядку, в тому ж стовпці або блоці головоломки. Граф має багато клік із 9 вершинами і вимагає 9 кольорів для будь-якого розфарбування. Розфарбування в 9 кольорів цього графа визначає розв'язок головоломки судоку. Як контраст, у графі Брауера — Хемерса найбільшими кліками є трикутники і для розфарбування потрібно лише 7 кольорів.
Примітки