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

Гіпо́теза Алспаха — це математична теорема, яка описує покриття циклами, що не перетинаються, ребер повних графів за заданих довжин циклів. Гіпотезу названо ім'ям Браяна Алспаха, який висловив її як дослідницьке завдання у 1981. 2014 року Даррін Браянт, Даніель Горслі та Вільям Петтерсон опублікували доведення теореми[1].

Формулювання

У цьому контексті покриття циклами, що не перетинаються, являє собою набір простих циклів, жоден з яких не використовує одне і те ж ребро і які містять всі ребра графа. Щоб покриття ребер неперетинними циклами існувало, необхідно, щоб кожна вершина мала парний степінь, оскільки степінь кожної вершини дорівнює подвоєному числу циклів, які містять цю вершину, тобто парне число. А для циклів у покритті циклами, що не перетинаються, з даним набором довжин необхідно, щоб сума довжин циклів збігалася із загальним числом ребер у графі. Алспах висловив гіпотезу, що для повних графів ці дві необхідні умови є достатніми — якщо ${\displaystyle n}$ непарне (так що степені парні) і задано список довжин циклів (усі довжини яких не перевищують ${\displaystyle n}$), які мають сумарну довжину ${\displaystyle {\tbinom {n}{2}}}$ (число ребер у повному графі), то повний граф ${\displaystyle K_{n}}$ можна розкласти на цикли заданої довжини. Це те твердження, яке довели Браянт, Горслі та Петтерссон.

Узагальнення на парне число вершин

Для повних графів ${\displaystyle K_{n}}$, число вершин ${\displaystyle n}$ яких парне, Алспах припустив, що завжди можна розкласти граф на досконале парування і набір циклів заданих довжин, що дають загальну довжину ${\displaystyle {\tbinom {n}{2}}-n/2}$. У цьому випадку парування виключає непарність степеня кожної вершини, залишаючи граф з парними степенями, і залишається умова, що сума довжин циклів дорівнює числу ребер, що залишилися. Цей варіант гіпотези Браянт, Горслі та Петтерссон також довели.

Пов'язані задачі

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

Примітки

1. Bryant, Horsley, Pettersson, 2014.

Література

• Alspach B. Problem 3 // Discrete Mathematics. — 1981. — Т. 36, вип. 3 (14 грудня). — С. 333. — DOI:10.1016/s0012-365x(81)80029-5.
• Darryn Bryant, Daniel Horsley, William Pettersson. Cycle decompositions V: Complete graphs into cycles of arbitrary lengths // Proceedings of the London Mathematical Society. — 2014. — Т. 108, вип. 5 (14 грудня). — С. 1153–1192. — (Third Series). — DOI:10.1112/plms/pdt051.
• Gary Chartrand, Linda Lesniak, Ping Zhang. Alspach's conjecture // Graphs & Digraphs. — 6th. — CRC Press, 2015. — Т. 39. — С. 349. — (Textbooks in Mathematics) — ISBN 9781498735803.