Гипотеза Алспаха

Гипотеза Олспаха — математическая теорема , которая характеризует непересекающиеся циклические покрытия полных графов с предписанными длинами циклов. Она названа в честь Брайана Олспаха , который сформулировал ее как исследовательскую задачу в 1981 году. Доказательство было опубликовано Даррином Брайантом, Дэниелом Хорсли и Уильямом Петтерссоном (2014).

В этом контексте непересекающееся покрытие циклов — это набор простых циклов, никакие два из которых не используют одно и то же ребро, которые включают все ребра графа . Для существования непересекающегося покрытия циклов необходимо, чтобы каждая вершина имела четную степень , поскольку степень каждой вершины в два раза больше числа циклов, включающих эту вершину, четное число. А для того, чтобы циклы в непересекающемся покрытии циклов имели заданный набор длин, также необходимо, чтобы сумма заданных длин циклов равнялась общему числу ребер в заданном графе. Алспах предположил , что для полных графов эти два необходимых условия также достаточны: если нечетно (так что степени четны) и заданный список длин циклов (все не более ) добавляется к (числу ребер в полном графе), то полный граф всегда можно разложить на циклы заданной длины. Именно это утверждение доказали Брайант, Хорсли и Петтерссон.${\displaystyle n}$${\displaystyle n}$${\displaystyle {\tbinom {n}{2}}}$${\displaystyle K_{n}}$

Для полных графов с четным числом вершин Алспах предположил, что всегда возможно разложить граф на совершенное паросочетание и набор циклов предписанной длины, в сумме дающих . В этом случае паросочетание устраняет нечетную степень в каждой вершине, оставляя подграф четной степени, и оставшееся условие снова состоит в том, что сумма длин циклов равна числу ребер, которые нужно покрыть. Этот вариант гипотезы также доказали Брайант, Хорсли и Петтерссон.${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle {\tbinom {n}{2}}-{\tfrac {n}{2}}}$

Проблема Обервольфаха о разложениях полных графов на копии заданного 2- регулярного графа связана, но ни одна из них не является частным случаем другой. Если — 2-регулярный граф с вершинами, образованный из несвязного объединения циклов определенных длин, то решение проблемы Обервольфаха для также даст разложение полного графа на копии каждого из циклов . Однако не каждое разложение на такое количество циклов каждого размера можно сгруппировать в несвязные циклы, которые образуют копии , и, с другой стороны, не каждый пример гипотезы Алспаха включает наборы циклов, которые имеют копии каждого цикла.${\displaystyle G}$${\displaystyle n}$${\displaystyle G}$${\displaystyle (n-1)/2}$${\displaystyle G}$${\displaystyle K_{n}}$${\displaystyle G}$${\displaystyle (n-1)/2}$

• Alspach, B. (1981), "Проблема 3", Исследовательские проблемы, Дискретная математика , 36 (3): 333, doi :10.1016/s0012-365x(81)80029-5
• Брайант, Даррин; Хорсли, Дэниел; Петтерссон, Уильям (2014), «Разложение циклов V: Полные графы в циклы произвольной длины», Труды Лондонского математического общества , Третья серия, 108 (5): 1153– 1192, arXiv : 1204.3709 , doi : 10.1112/plms/pdt051, MR  3214677
• Чартран, Гэри ; Лесняк, Линда; Чжан, Пин (2015), «Гипотеза Альспаха», Графики и орграфы , Учебники по математике, том. 39 (6-е изд.), CRC Press, с. 349, ISBN 9781498735803