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

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

Формулировка

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

Обобщение на чётное число вершин

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

Связанные проблемы

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