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

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

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

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

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

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

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

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

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

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

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

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

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

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