Задача Конвея о 99-вершинном графе ({g;gcg Tkufyx k 99-fyjonuukb ijgsy)

Перейти к навигации Перейти к поиску
Нерешённые проблемы математики: Существует ли сильно регулярный граф с параметрами (99,14,1,2)?
Граф с 9 вершинами, в котором каждое ребро принадлежит единственному треугольнику, а любое не-ребро является диагональю в единственном четырёхугольнике. Проблема 99-графа задаёт вопрос о существование графа с 99 вершинами с теми же свойствами.

Задача Конвея о 99-вершинном графе — нерешённая задача, которая спрашивает, существует ли неориентированный граф с 99 вершинами, в которых каждые две смежные вершины имеют в точности одного общего соседа и в которых две несмежные вершины имеют в точности два общих соседа. Эквивалентно, любое ребро должно быть частью единственного треугольника, а любая пара несмежных вершин должна быть на диагонали единственного 4-цикла. Джон Хортон Конвей объявил о призе в 1000 долларов тому, кто решит эту проблему[1].

Свойства

[править | править код]

Если такой граф существует, он необходимо будет локально линейным сильно регулярным графом srg(99,14,1,2). Первый, третий и четвёртый параметр записи кодируют утверждение проблемы — граф должен иметь 99 вершин, каждая пара смежных вершин должна иметь 1 одного общего соседа, а любые несмежные вершины должны иметь 2 общих соседа. Второй параметр означает, что граф является регулярным графом степени 14.

Если этот граф существует, он не имеет любых симметрий порядка 11, откуда следует, что его симметрии не могут перевести любую вершину в любую другую вершину[2]. Известны и другие ограничения на возможные группы симметрий[3].

В 2023 были открыты[4] следующие пять свойств графа:

  1. Граф не является подграфом графа srg(243,22,1,2).
  2. Граф не содержит в качестве подграфа граф Хэмминга H(4,3).
  3. Число независимости графа не меньше 10.
  4. Граф не является графом Кэли.
  5. Граф не является прямым произведением нетривиальных графов.

Свойства 1 и 4 любопытны в связи с тем, что ранее уже был построен являющийся графом Кэли граф srg(243,22,1,2)[5]. Свойства 2 и 5, в свою очередь, любопытны в связи с тем, что единственный (с точностью до изоморфизма) граф srg(9,4,1,2) является, с одной стороны, графом Хэмминга H(2,3), с другой — прямым произведением треугольников. Так, неизвестно, существуют ли графы srg(99,14,1,2), содержащие в качестве подграфа граф srg(9,4,1,2) и граф H(3,3).

История

[править | править код]

О возможном существовании графа с такими параметрами предполагал уже в 1969 году Норман Л. Биггс[6], а как открытую проблему существования среди прочих поставил Конвей[2][7][8][9]. Конвей сам работал над этой проблемой с 1975 года[7], но объявил приз в 2014 тому, кто решит проблему, как часть набора проблем, представленных на конференции DIMACS по важнейшим проблемам идентификации целочисленных последовательностей. Другие проблемы в этом наборе включает гипотезу о трекле, наименьшего расстояния множеств Данцера и вопрос, кто выигрывает после хода 16 в игре в «чеканку»[англ.][1].

Связанные графы

[править | править код]

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

Примечания

[править | править код]
  1. ↑ 1 2 John H. Conway. Five $1,000 Problems (Update 2017). — On-Line Encyclopedia of Integer Sequences. Архивировано 13 февраля 2019 года.
  2. ↑ 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).
  3. ↑ 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.
  4. ↑ Эльмар Гусейнов. Пять фактов о 99-вершинном графе Конвея // figshare.com. — 2023.
  5. ↑ E. R. Berlekamp, J. H. Van lint, J. J. Seidel. CHAPTER 3 - A Strongly Regular Graph Derived from the Perfect Ternary Golay Code // A Survey of Combinatorial Theory / JAGDISH N. Srivastava. — North-Holland, 1973-01-01. — С. 25–30. — ISBN 978-0-7204-2262-7.
  6. ↑ 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).
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ Peter J. Cameron. Combinatorics: topics, techniques, algorithms. — Cambridge: Cambridge University Press, 1994. — С. 331. — ISBN 0-521-45133-7.
Ошибка в сносках?: Тег <ref> с именем «zd», определённый в <references>, не используется в предшествующем тексте.
Источник — https://ru.wikipedia.org/w/index.php?title=Задача_Конвея_о_99-вершинном_графе&oldid=141665346