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

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

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

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

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

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

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

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

Ссылки

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