Задача Конвея о 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 году Норман Л. Биггс[5], а как открытую проблему существования среди прочих поставил Конвей[3][6][7][8]. Конвей сам работал над этой проблемой с 1975 года[6], но объявил приз в 2014 тому, кто решит проблему, как часть набора проблем, представленных на конференции DIMACS по важнейшим проблемам идентификации целочисленных последовательностей. Другие проблемы в этом наборе включает гипотезу о трекле, наименьшего расстояния множеств Данцера и вопрос, кто выигрывает после хода 16 в игре в «чеканку»[англ.][1].

Связанные графы[править | править код]

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

Примечания[править | править код]

  1. ↑ 1 2 John H. Conway. Five $1,000 Problems (Update 2017). — On-Line Encyclopedia of Integer Sequences. Архивировано 13 февраля 2019 года.
  2. ↑ Sa'ar Zehavi, Ivo Fagundes, David de Olivera. Not Conway's 99-graph problem. — 2017. — arXiv:1707.08047.
  3. ↑ 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).
  4. ↑ 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.
  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. ↑ 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.
  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.
Источник — https://ru.wikipedia.org/w/index.php?title=Задача_Конвея_о_99-вершинном_графе&oldid=127590401