Задача Обервольфаха

Нерозв'язана проблема математики: Чи для будь-якого 2-регулярного графа ${\displaystyle G}$ з ${\displaystyle n}$ вершинами повний граф ${\displaystyle K_{n}}$ можна розкласти на неперетинні по ребрах копії графа ${\displaystyle G}$? (більше нерозв'язаних проблем математики)

Зада́ча Обервольфаха — це нерозв'язана математична задача, яку можна сформулювати як задачу розподілу місць для обідів, або, абстрактніше, як задачу теорії графів про покриття циклами ребер повних графів. Назва задачі походить від назви математичного інституту Обервольфаха, де її сформулював 1967 року ^[ru].

Розклад повного графа ${\displaystyle K_{7}}$ на три копії графа ${\displaystyle C_{3}+C_{4}}$, що розв'язує задачу Обервольфаха для даних ${\displaystyle (3,4)}$

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

На конференціях, що проводяться в Обервольфасі, прийнято обідати разом у залі з круглими столами, не всі з яких мають однаковий розмір, а місця за столами змінюються від обіду до обіду. Задача Обервольфаха запитує, як задати розподіл місць за столами, щоб усі місця були зайняті та всі пари учасників конференції сиділи поряд лише раз. Примірник задачі можна позначити як ${\displaystyle OP(x,y,z,\dots )}$, де ${\displaystyle x,y,z,\dots }$ задає розміри столів. Альтернативно, коли деякі розміри столів повторюються, це може позначатись як верхній індекс, наприклад ${\displaystyle OP(5^{3})}$ описує задачу з трьома столами на п'ять місць.

При формулюванні задачі як задачі теорії графів пари людей, що сидять поруч за конкретним обідом, можна подати як ^[en] циклів ${\displaystyle C_{x}+C_{y}+C_{z}+\cdots }$ певної довжини, по одному циклу для кожного обіднього столу. Це об'єднання циклів є 2-регулярним графом, а будь-який 2-регулярний граф має такий вигляд. Якщо ${\displaystyle G}$ є таким 2-регулярним графом та має ${\displaystyle n}$ вершин, питання ставлять так: чи можна повний граф ${\displaystyle K_{n}}$ подати як об'єднання копій графа, що не перетинаються по ребрах ${\displaystyle G}$.

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

Відомі результати

Відомі лише такі екземпляри завдання Обервольфаха, про які відомо, що вони не мають розв'язку: ${\displaystyle OP(3^{2})}$, ${\displaystyle OP(3^{4})}$, ${\displaystyle OP(4,5)}$ і ${\displaystyle OP(3,3,5)}$. Поширена думка, що решта екземплярів розв'язки мають, але поки що доведено розв'язність лише спеціальних випадків.

Випадки, для яких відомі розв'язки:

• Усі примірники ${\displaystyle OP(x^{y})}$, за винятком ${\displaystyle OP(3^{2})}$ і ${\displaystyle OP(3^{4})}$.
• Усі примірники, в яких усі цикли мають парну довжину.
• Усі примірники (крім відомих винятків) з ${\displaystyle n\leqslant 40}$.
• Усі примірники для деяких ${\displaystyle n}$, що належать нескінченному набору простих чисел.
• Усі примірники ${\displaystyle OP(x,y)}$ крім відомих винятків ${\displaystyle OP(3,3)}$ і ${\displaystyle OP(4,5)}$.

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

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

Примітки

1. Hanfried Lenz, . A brief review on Egmont Köhler's mathematical work // . — 1991. — Т. 97, вип. 1—3. — С. 3–16. — DOI:10.1016/0012-365X(91)90416-Y.
2. Charlotte Huang, Anton Kotzig, Alexander Rosa. On a variation of the Oberwolfach problem // Discrete Mathematics. — 1979. — Т. 27, вип. 3. — С. 261–277. — DOI:10.1016/0012-365X(79)90162-6.
3. Roland Häggkvist. A lemma on cycle decompositions // Cycles in graphs (Burnaby, B.C., 1982). — North-Holland, 1985. — Т. 115. — С. 227–232. — (North-Holland Math. Stud.). — DOI:10.1016/S0304-0208(08)73015-9.
4. Brian Alspach, Roland Häggkvist. Some observations on the Oberwolfach problem // . — 1985. — Т. 9, вип. 1. — С. 177–187. — DOI:10.1002/jgt.3190090114.
5. Brian Alspach, Schellenberg P. J., Stinson D. R., David Wagner. The Oberwolfach problem and factors of uniform odd length cycles // . — 1989. — Т. 52, вип. 1. — С. 20–43. — DOI:10.1016/0097-3165(89)90059-9.
6. Hoffman D. G., Schellenberg P. J. The existence of ${\displaystyle C_{k}}$-factorizations of ${\displaystyle K_{2n}-F}$ // . — 1991. — Т. 97, вип. 1—3. — С. 243–250. — DOI:10.1016/0012-365X(91)90440-D.
7. Darryn Bryant, Peter Danziger. On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ and the Oberwolfach problem // . — 2011. — Т. 68, вип. 1. — С. 22–37. — DOI:10.1002/jgt.20538.
8. Deza A., Franek F., Hua W., Meszka M., Rosa A. Solutions to the Oberwolfach problem for orders 18 to 40 // Journal of Combinatorial Mathematics and Combinatorial Computing. — 2010. — Т. 74. — С. 95–102.
9. Darryn Bryant, Victor Scharaschkin. Complete solutions to the Oberwolfach problem for an infinite set of orders // . — 2009. — Т. 99, вип. 6. — С. 904–918. — DOI:10.1016/j.jctb.2009.03.003.
10. Brian Alspach, Darryn Bryant, Daniel Horsley, Barbara Maenhaut, Victor Scharaschkin. On factorisations of complete graphs into circulant graphs and the Oberwolfach problem // . — 2016. — Т. 11, вип. 1. — С. 157–173.
11. Tommaso Traetta. A complete solution to the two-table Oberwolfach problems // . — 2013. — Т. 120, вип. 5. — С. 984–997. — DOI:10.1016/j.jcta.2013.01.003.