99-графовая задача Конвейса - Conways 99-graph problem - Wikipedia

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Существует ли сильно регулярный граф с параметрами (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 по проблемам идентификации целочисленных последовательностей. догадка, минимальный интервал Наборы Danzer, и вопрос о том, кто выиграет после 16-го хода игры серебряная чеканка.[1]

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

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

Рекомендации

  1. ^ а б Конвей, Джон Х., Пять проблем по 1000 долларов (обновление 2017 г.) (PDF), Он-лайн энциклопедия целочисленных последовательностей, получено 2019-02-12. Смотрите также OEIS последовательность A248380.
  2. ^ Зехави, Саар; Давид де Оливера, Иво Фагундес (2017), Не проблема Конвея с 99-графами, arXiv:1707.08047
  3. ^ а б Уилбринк, Х. А. (август 1984 г.), "О сильно регулярном графе (99,14,1,2)", у де Дёльдера, П. Дж .; de Graaf, de, J .; ван Линт, Дж. Х. (ред.), Статьи, посвященные Дж. Дж. Зайделю (PDF), Отчет EUT, 84-WSK-03, Технологический университет Эйндховена, стр. 342–355
  4. ^ а б Махнев, А. А .; Минакова И. М. (январь 2004 г.) «Об автоморфизмах сильно регулярных графов с параметрами. , ", Дискретная математика и приложения, 14 (2), Дои:10.1515/156939204872374, МИСТЕР  2069991, S2CID  118034273
  5. ^ Биггс, Норман (1971), Конечные группы автоморфизмов: курс, прочитанный в Саутгемптонском университете, октябрь – декабрь 1969 г., Серия лекций Лондонского математического общества, 6, Лондон и Нью-Йорк: Издательство Кембриджского университета, стр. 111, ISBN  9780521082150, МИСТЕР  0327563
  6. ^ а б Гай, Ричард К. (1975), «Проблемы», в Келли, Л.М. (ред.), Материалы конференции, состоявшейся в Университете штата Мичиган, Ист-Лансинг, штат Мичиган, 17–19 июня 1974 г., Конспект лекций по математике, 490, Берлин и Нью-Йорк: Springer-Verlag, стр. 233–244, Дои:10.1007 / BFb0081147, МИСТЕР  0388240. См. Задачу 7 (J. J. Seidel), pp. 237–238.
  7. ^ Брауэр, А.Э.; Neumaier, A. (1988), «Замечание о частичных линейных пространствах обхвата 5 с приложением к сильно регулярным графам», Комбинаторика, 8 (1): 57–61, Дои:10.1007 / BF02122552, МИСТЕР  0951993, S2CID  206812356
  8. ^ Кэмерон, Питер Дж. (1994), Комбинаторика: темы, техники, алгоритмы, Кембридж: Издательство Кембриджского университета, стр. 331, ISBN  0-521-45133-7, МИСТЕР  1311922