Задача Конвея о 99-вершинном графе

Граф с 9 вершинами, в котором каждое ребро принадлежит единственному треугольнику, а любое не-ребро является диагональю в единственном четырёхугольнике. Проблема 99-графа задаёт вопрос о существование графа с 99 вершинами с теми же свойствами.

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

Свойства

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

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

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

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

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

История

О возможном существовании графа с такими параметрами предполагал уже в 1969 году Норман Л. БиггсШаблон:R, а как открытую проблему существования среди прочих поставил КонвейШаблон:R. Конвей сам работал над этой проблемой с 1975 годаШаблон:R, но объявил приз в 2014 тому, кто решит проблему, как часть набора проблем, представленных на конференции DIMACS по важнейшим проблемам идентификации целочисленных последовательностей. Другие проблемы в этом наборе включает гипотезу о трекле, наименьшего расстояния множеств Данцера и вопрос, кто выигрывает после хода 16 в игре в Шаблон:Не переведено 5Шаблон:R.

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

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