Задача Конвея про 99-вершинний граф

Нерозв'язана проблема математики:
Чи існує сильно регулярний граф з параметрами (99,14,1,2)?
(більше нерозв'язаних проблем математики)
Граф із 9 вершинами, у якому кожне ребро належить єдиному трикутнику, а будь-яке не-ребро є діагоналлю в єдиному чотирикутнику. Задача про 99-вершинний граф ставить питання існування графа з 99 вершинами з такими самими властивостями.

Зада́ча Ко́нвея про 99-верши́нний граф — нерозв'язана задача, в якій запитується, чи існує неорієнтований граф з 99 вершинами, у якому кожні дві суміжні вершини мають рівно одного спільного сусіда і в якому дві несуміжні вершини мають рівно два спільних сусіди. Еквівалентно, будь-яке ребро має бути частиною єдиного трикутника, а будь-яка пара несуміжних вершин має бути на діагоналі єдиного 4-циклу. Джон Гортон Конвей оголосив про приз у 1000 доларів тому, хто розв'яже цю задачу[1].

Властивості

Якщо такий граф існує, він буде локально лінійним сильно регулярним графом з параметрами (99,14,1,2). Перший, третій і четвертий параметри кодують твердження задачі — граф повинен мати 99 вершин, кожна пара суміжних вершин повинна мати 1 спільного сусіда, а будь-які несуміжні вершини повинні мати 2 спільних сусіди. Другий параметр означає, що граф є регулярним графом із 14 ребрами на вершину[2].

Якщо цей граф існує, він не має будь-яких симетрій порядку 11, звідки випливає, що його симетрії не можуть перевести будь-яку вершину в іншу вершину[3]. Відомі й інші обмеження на можливі групи симетрій[4].

Історія

Можливість існування графа з такими параметрами припускав вже 1969 року Норман Л. Біггз[en][5], а як відкриту задачу існування серед інших поставив Конвей[3][6][7][8]. Конвей сам працював над цією задачою від 1975[6], але 2014 року оголосив приз тому, хто розв'яже задачу, як частину набору задач, представлених на конференції DIMACS з найважливіших проблем ідентифікації цілочисельних послідовностей. Цей набір задач також включає гіпотезу про трекл, найменшу відстань множин Данцера і питання, хто виграє після ходу 16 у грі в «чеканку»[en][1].

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

Загальніше, існує тільки п'ять можливих комбінацій параметрів, для яких сильно регулярний граф може існувати зі властивістю, що кожне ребро належить єдиному трикутнику, а кожне неребро (відсутнє ребро двох несуміжних вершин) утворює діагональ єдиного чотирикутника. Відомо лише, що графи існують із двома з п'яти цих комбінацій. Цими двома графами є граф Пелі з дев'ятьма вершинами (граф 3-3 дуопризми) з параметрами (9,4,1,2) та граф Берлекемпа — ван Лінта — Зейделя з параметрами (243,22,1,2). Задача про 99-вершинний граф запитує про найменшу із цих п'яти комбінацій параметрів, для яких існування графа невідоме[4].

Примітки

  1. ↑ а б John H. Conway. Five $1,000 Problems (Update 2017). — On-Line Encyclopedia of Integer Sequences.
  2. ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Not Conway's 99-graph problem. — 2017. — arXiv:1707.08047.
  3. ↑ а б Wilbrink H. A. On the (99,14,1,2) strongly regular graph // Papers dedicated to J. J. Seidel / de Doelder P. J., de Graaf J., van Lint J. H.. — Eindhoven University of Technology. — Т. 84-WSK-03. — С. 342–355. — (EUT Report).
  4. ↑ а б Makhnev A. A., Minakova I. M.,. On automorphisms of strongly regular graphs with parameters ,  // Discrete Mathematics and Applications. — 2004. — Т. 14, вип. 2 (січень). — DOI:10.1515/156939204872374.
  5. ↑ Norman L. Biggs. Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969. — London and New York : Cambridge University Press, 1971. — Т. 6. — С. 111. — (London Mathematical Society Lecture Note Series).
  6. ↑ а б Richard K. Guy. Problems // Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974 / Kelly L. M.. — Berlin, New York : Springer-Verlag, 1975. — Т. 490. — С. 233–244. — (Lecture Notes in Mathematics). — DOI:10.1007/BFb0081147.. See problem 7 (J. J. Seidel), pp. 237—238.
  7. ↑ Brouwer A. E., Neumaier A. A remark on partial linear spaces of girth 5 with an application to strongly regular graphs // Combinatorica. — 1988. — Т. 8, вип. 1. — С. 57–61. — DOI:10.1007/BF02122552.
  8. ↑ Peter J. Cameron. Combinatorics: topics, techniques, algorithms. — Cambridge : Cambridge University Press, 1994. — С. 331. — ISBN 0-521-45133-7.