Задача Конвея о 99 графах
В теории графов , проблема 99-графа Конвея — это нерешенная проблема, спрашивающая, существует ли неориентированный граф с 99 вершинами , в котором каждые две смежные вершины имеют ровно одного общего соседа, и в котором каждые две несмежных вершины имеют ровно двух общих соседей. Эквивалентно, каждое ребро должно быть частью уникального треугольника, а каждая несмежная пара должна быть одной из двух диагоналей уникального 4-цикла. Джон Хортон Конвей предложил приз в размере 1000 долларов за ее решение. [1]
Характеристики
Если такой граф существует, он обязательно будет локально линейным графом и сильно регулярным графом с параметрами (99,14,1,2). Первый, третий и четвертый параметры кодируют условие задачи: граф должен иметь 99 вершин, каждая пара смежных вершин должна иметь 1 общего соседа, а каждая пара несмежных вершин должна иметь 2 общих соседа. Второй параметр означает, что граф является регулярным графом с 14 ребрами на вершину. [2]
Если этот граф существует, он не может иметь симметрий, которые переводят каждую вершину в каждую другую вершину. [3] Известны дополнительные ограничения на его возможные группы симметрий. [4] [5]
История
Возможность графа с этими параметрами была предложена еще в 1969 году Норманом Л. Биггсом [6] , и ее существование было отмечено как открытая проблема другими до Конвея. [3] [7] [8] [9] Сам Конвей работал над этой проблемой еще в 1975 году [7] , но предложил премию в 2014 году как часть набора задач, поставленных на конференции DIMACS по проблемам идентификации целочисленных последовательностей. Другие задачи в наборе включают гипотезу о трэкле , минимальное расстояние между множествами Данцера и вопрос о том, кто победит после хода 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]
Ссылки
- ^ ab Conway, John H. , Five $1,000 Problems (Update 2017) (PDF) , On-Line Encyclopedia of Integer Sequences , получено 2019-02-12. См. также последовательность OEIS A248380.
- ^ Зехави, Саар; Дэвид де Оливера, Иво Фагундес (2017), Не проблема Конвея с 99 графами , arXiv : 1707.08047
- ^ ab Wilbrink, HA (август 1984 г.), «О (99,14,1,2) сильно регулярном графе», в de Doelder, PJ; де Грааф, Дж.; ван Линт, Дж. Х. (ред.), Статьи, посвященные Дж. Дж. Зайделу (PDF) , Отчет EUT, том. 84-WSK-03, Эйндховенский технологический университет, стр. 342–355.
- ^ ab Махнев, АА; Минакова, И.М. (январь 2004), "Об автоморфизмах сильно регулярных графов с параметрами " , Дискретная математика и приложения , 14 (2), doi :10.1515/156939204872374, MR 2069991, S2CID 118034273
- ^ Бехбахани, Маджид; Лам, Клемент (2011), «Строго регулярные графы с нетривиальными автоморфизмами», Дискретная математика , 311 (2–3): 132–144, doi : 10.1016/j.disc.2010.10.005 , MR 2739917
- ↑ Биггс, Норман (1971), Конечные группы автоморфизмов: курс, прочитанный в Университете Саутгемптона, октябрь–декабрь 1969 г., Серия лекций Лондонского математического общества, т. 6, Лондон и Нью-Йорк: Cambridge University Press, стр. 111, ISBN 9780521082150, МР 0327563
- ^ ab Guy, Richard K. (1975), «Проблемы», в Kelly, LM (ред.), Геометрия метрических и линейных пространств , Lecture Notes in Mathematics, т. 490, Berlin and New York: Springer-Verlag, стр. 233–244, doi :10.1007/BFb0081147, ISBN 978-3-540-07417-5, МР 0388240. См. задачу 7 (JJ Seidel), стр. 237–238.
- ^ Брауэр, А. Э.; Ноймайер, А. (1988), «Замечание о частичных линейных пространствах обхвата 5 с приложением к сильно регулярным графам», Combinatorica , 8 (1): 57–61, doi :10.1007/BF02122552, MR 0951993, S2CID 206812356
- ^ Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Кембридж: Cambridge University Press, стр. 331, ISBN 0-521-45133-7, г-н 1311922
