Задача Конвея о 99-вершинном графе — нерешённая задача, которая спрашивает, существует ли неориентированный граф с 99 вершинами, в которых каждые две смежные вершины имеют в точности одного общего соседа и в которых две несмежные вершины имеют в точности два общих соседа. Эквивалентно, любое ребро должно быть частью единственного треугольника, а любая пара несмежных вершин должна быть на диагонали единственного 4-цикла. Джон Хортон Конвей объявил о призе в 1000 долларов тому, кто решит эту проблему[1].
Свойства
Если такой граф существует, он необходимо будет локально линейным сильно регулярным графом с параметрами (99,14,1,2). Первый, третий и четвёртый параметр кодируют утверждение проблемы — граф должен иметь 99 вершин, каждая пара смежных вершин должна иметь 1 одного общего соседа, а любые несмежные вершины должны иметь 2 общих соседа. Второй параметр означает, что граф является регулярным графом с 14 рёбрами на вершину[2].
Если этот граф существует, он не имеет любых симметрий порядка 11, откуда следует, что его симметрии не могут перевести любую вершину в любую другую вершину[3]. Известны и другие ограничения на возможные группы симметрий[4].
История
О возможном существовании графа с такими параметрами предполагал уже в 1969 году Норман Л. Биггс[5], а как открытую проблему существования среди прочих поставил Конвей[3][6][7][8]. Конвей сам работал над этой проблемой с 1975 года[6], но объявил приз в 2014 тому, кто решит проблему, как часть набора проблем, представленных на конференции DIMACS по важнейшим проблемам идентификации целочисленных последовательностей. Другие проблемы в этом наборе включает гипотезу о трекле, наименьшего расстояния множеств Данцера и вопрос, кто выигрывает после хода 16 в игре в «чеканку»[1].
Связанные графы
Более обще, существует только пять возможных комбинаций параметров, для которых сильно регулярный граф может существовать со свойством, что каждое ребро принадлежит единственному треугольнику, а каждое не-ребро (отсутствующее ребро двух несмежных вершин) образует диагональ единственного четырёхугольника. Известно только, что графы существуют с двумя из пяти этих комбинаций. Этими двумя графами являются граф Пэли с девятью вершинами (граф 3-3 дуопризмы) с параметрами (9,4,1,2) и граф Берлекэмпа — ван Линта — Зейделя с параметрами (243,22,1,2). Проблема 99-графа спрашивает о наименьшей из этих пяти комбинаций параметров, для которых существование графа неизвестно[4].
Примечания
- ↑ 1 2 John H. Conway. Five $1,000 Problems (Update 2017). — On-Line Encyclopedia of Integer Sequences. Архивировано 13 февраля 2019 года.
- ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Not Conway's 99-graph problem. — 2017. — arXiv:1707.08047.
- ↑ 1 2 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).
- ↑ 1 2 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.
- ↑ 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).
- ↑ 1 2 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.
- ↑ 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.
- ↑ Peter J. Cameron. Combinatorics: topics, techniques, algorithms. — Cambridge: Cambridge University Press, 1994. — С. 331. — ISBN 0-521-45133-7.
Эта страница в последний раз была отредактирована 1 января 2023 в 04:39.
Обычно почти сразу, изредка в течении часа.