гипотеза Коцига

Нерешенная задача по математике :

Существует ли конечный граф по крайней мере с двумя вершинами, в котором каждая пара различных вершин соединена ровно одним путем длины , где фиксировано? ${\displaystyle k}$ ${\displaystyle k\geq 3}$

(еще нерешенные проблемы по математике)

Гипотеза Коцига — недоказанное утверждение в теории графов , которое гласит, что конечных графов с определенными свойствами не существует. Граф является -графом, если каждая пара различных вершин соединена ровно одним путем длины . Гипотеза Коцига утверждает, что для не существует конечных -графов с двумя или более вершинами. Гипотеза была впервые сформулирована Антоном Коцигом в 1974 году. ^[1] Она была проверена для Александром Косточкой, ^[2] но остается открытой в общем случае (по состоянию на июль 2024 года). ${\displaystyle P_{k}}$ ${\displaystyle k}$ ${\displaystyle k\geq 3}$ ${\displaystyle P_{k}}$ ${\displaystyle k\leq 20}$

Гипотеза сформулирована для , поскольку -графы существуют для меньших значений . -графы являются в точности полными графами . Теорема о дружбе утверждает, что -графы являются в точности (треугольными) графами-мельницами (то есть конечным числом треугольников, соединенных в общей вершине; также известными как графы дружбы ). ${\displaystyle k\geq 3}$ ${\displaystyle P_{k}}$ ${\displaystyle k}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$

История

Гипотеза Коцига была впервые указана как открытая проблема Бонди и Мурти в 1976 году, ^[3] приписана Коцигу и датирована 1974 годом. ^[1] Первая собственная работа Коцига по этой гипотезе появилась в 1979 году. ^[4] Позднее он проверил гипотезу для и заявил о решении, хотя и неопубликованном, для . ^[5] Теперь известно, что гипотеза верна для благодаря работе Александра Косточки. ^[2] Косточка заявил, что его методы распространяются на , но доказательство этого не было опубликовано. ^[6] Обзор по -графам был написан Джоном А. Бонди , включая доказательства для многих утверждений, ранее сделанных Коцигом без письменных доказательств. ^[7] ${\displaystyle k\leq 8}$ ${\displaystyle k\leq 9}$ ${\displaystyle k\leq 20}$ ${\displaystyle k\leq 33}$ ${\displaystyle P_{k}}$

В 1990 году Син и Ху заявили о доказательстве гипотезы Коцига для . ^[8] В то время это, казалось, разрешило гипотезу, и до сих пор заставляет многих верить, что проблема решена. Однако доказательство Сина и Ху основывалось на неправильном понимании утверждения, доказанного Коцигом. Коциг показал, что -граф должен содержать -цикл для некоторого , ^[5] которое Син и Ху использовали в той форме, что циклы всех этих длин должны существовать. В своей статье Син и Ху показывают, что для -граф не должен содержать -цикл. Поскольку это противоречит их прочтению результата Коцига, они заключают (неверно), что -графы с не могут существовать. На эту ошибку впервые указал Роланд Хеггквист в 2000 году. ${\displaystyle k\geq 12}$ ${\displaystyle P_{k}}$ ${\displaystyle 2\ell }$ ${\displaystyle \ell \in \{3,...,k-4\}}$ ${\displaystyle k\geq 12}$ ${\displaystyle P_{k}}$ ${\displaystyle (2k-8)}$ ${\displaystyle P_{k}}$ ${\displaystyle k\geq 12}$

Гипотеза Коцига упоминается в Доказательствах из КНИГИ в главе о теореме о дружбе . ^[6] Утверждается, что общее доказательство гипотезы кажется «вне досягаемости».

Свойства П к {\displaystyle P_{k}} -графики

• -граф на вершинах содержит ровно путей длины . ${\displaystyle P_{k}}$ ${\displaystyle n}$ ${\displaystyle \textstyle {n \choose 2}}$ ${\displaystyle k}$

• Поскольку две конечные вершины ребра в -графе соединены уникальным -путем, каждое ребро содержится в уникальном -цикле. Следовательно, граф имеет уникальное разложение на непересекающиеся по ребрам -циклы, и нет других -циклов, кроме этих. В частности, -графы являются эйлеровыми . ^[4] ${\displaystyle P_{k}}$ ${\displaystyle k}$ ${\displaystyle (k+1)}$ ${\displaystyle (k+1)}$ ${\displaystyle (k+1)}$ ${\displaystyle P_{k}}$

• ${\displaystyle P_{k}}$-графы не являются двудольными : если нечетно и являются вершинами в одном и том же классе двудольности, никакой -путь не может их соединить. Аналогично, если четно и являются вершинами в разных классах двудольности, никакой -путь не может их соединить. ${\displaystyle k}$ ${\displaystyle v,w}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v,w}$ ${\displaystyle k}$

• Чётные циклы образуют важные подструктуры в -графах. Леденец (иногда также монокль ) представляет собой объединение чётного -цикла с путём, пересекающим циклы ровно в одной из его конечных вершин. Путь должен быть короче, чем , поскольку в противном случае он приводил бы к двум -путям с теми же конечными вершинами. Поэтому существование и распределение леденцов и, в более общем смысле, чётных циклов, было тщательно изучено. Известно, что должен существовать чётный цикл длины для некоторых , ^[5] и что не может существовать чётных циклов длины , , , , ^[5] или . ^[8] ${\displaystyle P_{k}}$ ${\displaystyle 2\ell }$ ${\displaystyle k-\ell }$ ${\displaystyle k}$ ${\displaystyle 2\ell }$ ${\displaystyle \ell \in \{3,...,k-5\}}$ ${\displaystyle 4}$ ${\displaystyle 2k}$ ${\displaystyle 2k-2}$ ${\displaystyle 2k-4}$ ${\displaystyle 2k-6}$ ${\displaystyle 2k-8}$

• -граф не может содержать цикл (четный или нечетный) длины не менее . В то же время должен существовать цикл длины не менее . Объединение этих ограничений дает . ^[2] ${\displaystyle P_{k}}$ ${\displaystyle {\tfrac {4}{3}}k-2}$ ${\displaystyle k+5}$ ${\displaystyle k\geq 21}$

• Любые два -цикла в -графе должны иметь не менее трех ^[7] и не более ^[2] общих вершин. В частности, является 2-связным. Кроме того, Коциг утверждает, что любые два -цикла имеют не менее семи общих вершин, ^[5] хотя доказательство не было опубликовано. ${\displaystyle (k+1)}$ ${\displaystyle P_{k}}$ ${\displaystyle k-2}$ ${\displaystyle G}$ ${\displaystyle (k+1)}$

• Пусть обозначает число -циклов в данном -графе. Тогда . Если четно, то . ^[2] Если нечетно, то . ^[7] Следовательно, число ребер в -графе (при нечетном) ограничено, а поскольку -графы связны, то ограничено и число вершин. ${\displaystyle c_{k+1}}$ ${\displaystyle (k+1)}$ ${\displaystyle P_{k}}$ ${\displaystyle c_{k+1}\geq 3}$ ${\displaystyle k}$ ${\displaystyle c_{k+1}\geq 4}$ ${\displaystyle k}$ ${\displaystyle c_{k+1}\leq {\tfrac {1}{2}}(k-1)}$ ${\displaystyle P_{k}}$ ${\displaystyle k}$ ${\displaystyle P_{k}}$

Ссылки

1. Bondy & Murty 1976, стр. 246, Задача 4
2. Косточка, А. В. (1988). Несуществование некоторых обобщенных графов дружбы. В комбинаторике (Эгер, 1987) (стр. 341-356). Северная Голландия, Амстердам.
3. Бонди, JA; Мурти, USR (1976). Теория графов с приложениями (PDF) . Macmillan.
4. Kotzig, A. (1979). Избранные открытые проблемы теории графов. Теория графов и смежные темы, 371.
5. Коциг, А. (1983). Регулярно связные графы с k-путями. Congressus Numerantium, 40, 137-141.
6. Aigner, M., Ziegler, GM (2004). О друзьях и политиках. В: Proofs from THE BOOK. Springer, Берлин, Гейдельберг. https://doi.org/10.1007/978-3-662-05412-3_34
7. Bondy, JA (1985). Гипотеза Коцига об обобщенных графах дружбы — обзор. В North-Holland Mathematics Studies (т. 115, стр. 351-366). North-Holland.
8. Xing, K., & Hu, B. (1994). О гипотезе Коцига для графов с регулярной линейной связностью. Дискретная математика, 135(1-3), 387-393.