Проблема Обервольфаха - Oberwolfach problem

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

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

В Проблема Обервольфаха - это нерешенная проблема в математике, которую можно сформулировать либо как задачу планирования рассадки посетителей, либо, более абстрактно, как задачу в теория графов, на крышки цикла края из полные графики. Он назван в честь Математический научно-исследовательский институт Обервольфаха, где проблема была поставлена ​​в 1967 г. Герхард Рингель.^[1]

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

На конференциях, проводимых в Обервольфахе, участники обычно обедают вместе в комнате с круглыми столами, не все одинакового размера, и с определенными сиденьями, которые меняют участников от приема пищи к обеду. Задача Обервольфаха состоит в том, чтобы составить схему рассадки для данного набора столов, чтобы все столы были заполнены при каждом приеме пищи, а все пары участников конференции сажались рядом друг с другом ровно один раз. Пример проблемы можно обозначить как ${\displaystyle OP(x,y,z,\dots )}$ куда ${\displaystyle x,y,z,\dots }$ - данные размеры таблицы. В качестве альтернативы, когда некоторые размеры таблиц повторяются, они могут быть обозначены с использованием экспоненциальной записи; например, ${\displaystyle OP(5^{3})}$ описывает экземпляр с тремя таблицами пятого размера.^[1]

Сформулированная как проблема теории графов, пары людей, сидящих рядом друг с другом за одним приемом пищи, могут быть представлены как несвязный союз из графики цикла ${\displaystyle C_{x}+C_{y}+C_{z}+\cdots }$ указанной длины, с одним циклом для каждого обеденного стола. Это объединение циклов является 2-регулярный граф, и каждый 2-регулярный граф имеет такой вид. Если ${\displaystyle G}$ это 2-регулярный граф и имеет ${\displaystyle n}$ вершин, вопрос в том, ${\displaystyle K_{n}}$ можно представить как непересекающееся по ребрам объединение копий ${\displaystyle G}$.^[1]

Чтобы решение существовало, общее количество участников конференции (или, что эквивалентно, общая емкость таблиц или общее количество вершин данных графов циклов) должно быть нечетным числом. Ведь во время каждого приема пищи каждый участник сидит рядом с двумя соседями, поэтому общее количество соседей каждого участника должно быть четным, а это возможно только тогда, когда общее количество участников нечетное. Однако проблема распространилась и на четные значения ${\displaystyle n}$ попросив, для тех ${\displaystyle n}$, все ли ребра полного графа, кроме идеальное соответствие покрывается копиями данного 2-регулярного графа. Словно проблема с мужем (другая математическая задача, связанная с расположением обедающих и столами), этот вариант задачи можно сформулировать, предположив, что ${\displaystyle n}$ обедающие организованы в ${\displaystyle n/2}$ супружеские пары, и что при рассадке следует разместить каждого посетителя рядом друг с другом, за исключением их собственного супруга, ровно один раз.^[2]

Известные результаты

Единственные примеры проблемы Обервольфаха, которые, как известно, неразрешимы, - это ${\displaystyle OP(3^{2})}$, ${\displaystyle OP(3^{4})}$, ${\displaystyle OP(4,5)}$, и ${\displaystyle OP(3,3,5)}$^[3]. Широко распространено мнение, что во всех других случаях есть решение, но доказано, что только частные случаи разрешимы.

Случаи, для которых известно решение, включают:

• Все экземпляры ${\displaystyle OP(x^{y})}$ Кроме ${\displaystyle OP(3^{2})}$ и ${\displaystyle OP(3^{4})}$.^{[4][5][6][7][2]}
• Все экземпляры, в которых все циклы имеют одинаковую длину.^[4][8]
• Все экземпляры (кроме известных исключений) с ${\displaystyle n\leq 60}$.^[9][3]
• Все экземпляры для определенного выбора ${\displaystyle n}$, принадлежащих бесконечным подмножествам натуральных чисел.^[10][11]
• Все экземпляры ${\displaystyle OP(x,y)}$ кроме известных исключений ${\displaystyle OP(3,3)}$ и ${\displaystyle OP(4,5)}$.^[12]

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

Проблема школьницы Киркмана, группирование пятнадцати школьниц в ряды по три семь различными способами так, чтобы каждая пара девочек появлялась один раз в каждой тройке, является частным случаем проблемы Обервольфаха, ${\displaystyle OP(3^{5})}$. Проблема Гамильтоново разложение полного графа ${\displaystyle K_{n}}$ это еще один частный случай, ${\displaystyle OP(n)}$.^[8]

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

Рекомендации

1. Ленц, Ханфрид; Рингель, Герхард (1991), «Краткий обзор математической работы Эгмонта Келера», Дискретная математика, 97 (1–3): 3–16, Дои:10.1016 / 0012-365X (91) 90416-Y, МИСТЕР  1140782
2. Хуанг, Шарлотта; Коциг, Антон; Роза, Александр (1979), "Об одном варианте проблемы Обервольфаха", Дискретная математика, 27 (3): 261–277, Дои:10.1016 / 0012-365X (79) 90162-6, МИСТЕР  0541472
3. Salassa, F .; Dragotto, G .; Traetta, T .; Buratti, M .; Делла Кроче, Ф. (2019), Слияние комбинаторного дизайна и оптимизации: проблема Обервольфаха, arXiv:1903.12112, Bibcode:2019arXiv190312112S
4. Хэггквист, Роланд (1985), "Лемма о циклических разложениях", Циклы в графиках (Бернаби, Британская Колумбия, 1982), Северная Голландия Math. Stud., 115, Амстердам: Северная Голландия, стр. 227–232, Дои:10.1016 / S0304-0208 (08) 73015-9, МИСТЕР  0821524
5. Альспах, Брайан; Хэггквист, Роланд (1985), "Некоторые наблюдения по проблеме Обервольфаха", Журнал теории графов, 9 (1): 177–187, Дои:10.1002 / jgt.3190090114, МИСТЕР  0785659
6. Альспах, Брайан; Schellenberg, P.J .; Стинсон, Д.; Вагнер, Дэвид (1989), "Проблема Обервольфаха и факторы однородных циклов нечетной длины", Журнал комбинаторной теории, Серия А, 52 (1): 20–43, Дои:10.1016/0097-3165(89)90059-9, МИСТЕР  1008157
7. Hoffman, D. G .; Шелленберг, П. Дж. (1991), "Существование ${\displaystyle C_{k}}$-факторизация ${\displaystyle K_{2n}-F}$", Дискретная математика, 97 (1–3): 243–250, Дои:10.1016 / 0012-365X (91) 90440-D, МИСТЕР  1140806
8. Брайант, Даррин; Данцигер, Питер (2011), "О двудольных 2-факторизациях ${\displaystyle K_{n}-I}$ и проблема Обервольфаха " (PDF), Журнал теории графов, 68 (1): 22–37, Дои:10.1002 / jgt.20538, МИСТЕР  2833961
9. Deza, A .; Franek, F .; Хуа, Вт .; Мешка, М .; Роза, А. (2010), «Решения проблемы Обервольфаха для заказов с 18 по 40» (PDF), Журнал комбинаторной математики и комбинаторных вычислений, 74: 95–102, МИСТЕР  2675892
10. Брайант, Даррин; Шарашкин, Виктор (2009), "Полные решения проблемы Обервольфаха для бесконечного множества порядков", Журнал комбинаторной теории, Серия B, 99 (6): 904–918, Дои:10.1016 / j.jctb.2009.03.003, МИСТЕР  2558441
11. Альспах, Брайан; Брайант, Даррин; Хорсли, Дэниел; Менгаут, Барбара; Щарашкин, Виктор (2016), «О факторизациях полных графов в циркулянтные графы и проблеме Обервольфаха», Ars Mathematica Contemporanea, 11 (1): 157–173, arXiv:1411.6047, Дои:10.26493/1855-3974.770.150, МИСТЕР  3546656
12. Traetta, Tommaso (2013), «Полное решение двухстолбцовых проблем Обервольфаха», Журнал комбинаторной теории, Серия А, 120 (5): 984–997, Дои:10.1016 / j.jcta.2013.01.003, МИСТЕР  3033656