Граф Геймса

Граф Геймса — це найбільший із відомих локально лінійних сильно регулярних графів. Його параметри як сильно регулярного графа рівні (729,112,1,20). Це означає, що граф має 729 вершин та 40824 ребер (112 ребер на вершину). Кожне ребро належить єдиному трикутнику (це локально лінійний граф) і кожна несуміжна пара вершин має рівно 20 спільних сусідів. Граф названо ім'ям Річарда А. Геймса, який у неопублікованому листуванні запропонував його побудовуШаблон:R і написав про пов'язані побудовиШаблон:R .

Побудова

Побудова цього графа використовує єдину (з точністю до симетрії) 56-точкову Шаблон:Не перекладено (Шаблон:Lang-en, підмножина точок, ніякі три з яких не лежать на одній прямій) $PG(5,3)$, п'ятивимірної проєктивної геометрії над триелементним полемШаблон:R. Шестивимірну проєктивну геометрію, $PG(6,3)$, можна розбити на шестивимірний афінний простір $AG(6,3)$ та копію $PG(5,3)$ (точки на нескінченності з урахуванням афінного простору). Граф Геймса має як вершини 729 точок афінного простору $AG(6,3)$. Кожна пряма в афінному просторі проходить через три з цих точок і четверту нескінченно віддалену точку. Граф містить трикутник для будь-якої прямої з трьох афінних точок, яка проходить через точку множини-ковпакаШаблон:R.

Властивості

Деякі з властивостей графа випливають безпосередньо з побудови. Граф має $729=3^6$ вершин, оскільки кількість точок у афінному просторі дорівнює розміру базового поля в степені розмірності. Для кожної афінної точки існує 56 прямих через точки множини-ковпака, 56 трикутників, що містять відповідну вершину, та $112=56\times 2$ сусідів вершини. І не може бути ніяких трикутників, відмінних від отриманих при побудові, оскільки будь-який інший трикутник отримувався би з трьох різних прямих, що перетинаються в спільній площині $PG(6,3)$, а три точки множини-ковпака трьох прямих лежали б на перетині цієї площини з $PG(5,3)$, що дає пряму. Однак це порушило би властивість множини-ковпака, що ніякі три точки не лежать на одній прямій, так що ніякого додаткового трикутника існувати не може. Властивість сильної регулярності графів, що всі несуміжні пари вершин мають однакову кількість спільних сусідів, залежить від властивостей 5-вимірної множини-ковпака.

Пов'язані графи

Разом із туровим графом $3\times 3$ і графом Брауера — Хемерса, граф Геймса є одним з трьох можливих сильно регулярних графів, параметри якого мають вигляд $((n^2+3n-1{)}^2,n^2(n+3),1,n(n+1))$Шаблон:R.

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