Задача Конвея про 99-вершинний граф
Зада́ча Ко́нвея про 99-верши́нний граф — нерозв'язана задача, в якій запитується, чи існує неорієнтований граф з 99 вершинами, у якому кожні дві суміжні вершини мають рівно одного спільного сусіда і в якому дві несуміжні вершини мають рівно два спільних сусіди. Еквівалентно, будь-яке ребро має бути частиною єдиного трикутника, а будь-яка пара несуміжних вершин має бути на діагоналі єдиного 4-циклу. Джон Гортон Конвей оголосив про приз у 1000 доларів тому, хто розв'яже цю задачуШаблон:R.
Властивості
Якщо такий граф існує, він буде локально лінійним сильно регулярним графом з параметрами (99,14,1,2). Перший, третій і четвертий параметри кодують твердження задачі — граф повинен мати 99 вершин, кожна пара суміжних вершин повинна мати 1 спільного сусіда, а будь-які несуміжні вершини повинні мати 2 спільних сусіди. Другий параметр означає, що граф є регулярним графом із 14 ребрами на вершинуШаблон:R.
Якщо цей граф існує, він не має будь-яких симетрій порядку 11, звідки випливає, що його симетрії не можуть перевести будь-яку вершину в іншу вершинуШаблон:R. Відомі й інші обмеження на можливі групи симетрійШаблон:R.
Історія
Можливість існування графа з такими параметрами припускав вже 1969 року Шаблон:НпШаблон:R, а як відкриту задачу існування серед інших поставив КонвейШаблон:R. Конвей сам працював над цією задачою від 1975Шаблон:R, але 2014 року оголосив приз тому, хто розв'яже задачу, як частину набору задач, представлених на конференції DIMACS з найважливіших проблем ідентифікації цілочисельних послідовностей. Цей набір задач також включає гіпотезу про трекл, найменшу відстань множин Данцера і питання, хто виграє після ходу 16 у грі в Шаблон:Не перекладеноШаблон:R.
Пов'язані графи
Загальніше, існує тільки п'ять можливих комбінацій параметрів, для яких сильно регулярний граф може існувати зі властивістю, що кожне ребро належить єдиному трикутнику, а кожне неребро (відсутнє ребро двох несуміжних вершин) утворює діагональ єдиного чотирикутника. Відомо лише, що графи існують із двома з п'яти цих комбінацій. Цими двома графами є граф Пелі з дев'ятьма вершинами (граф 3-3 дуопризми) з параметрами (9,4,1,2) та граф Берлекемпа — ван Лінта — Зейделя з параметрами (243,22,1,2). Задача про 99-вершинний граф запитує про найменшу із цих п'яти комбінацій параметрів, для яких існування графа невідомеШаблон:R.