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

Нерешенная задача по математике :

Для которого 2-регулярные

n

-вершинные графы

G

можно полный график

K_{n}

разложить на непересекающиеся по ребрам копии

G

?

(еще нерешенные задачи по математике)

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с Ленц, Ханфрид ; Рингель, Герхард (1991), «Краткий обзор математической работы Эгмонта Келера», Discrete Mathematics , 97 (1–3): 3–16, doi : 10.1016/0012-365X(91)90416-Y , MR 1140782
^ Jump up to: ^а ^б Хуанг, Шарлотта; Коциг, Антон ; Роза, Александр (1979), «О вариации задачи Обервольфаха», Discrete Mathematics , 27 (3): 261–277, doi : 10.1016/0012-365X(79)90162-6 , MR 0541472
^ Jump up to: ^а ^б Саласса, Ф.; Драготто, Г.; Траэтта, Т.; Буратти, М.; Делла Кроче, Ф. (2019), Объединение комбинаторного проектирования и оптимизации: проблема Обервольфаха , arXiv : 1903.12112 , Bibcode : 2019arXiv190312112S
^ Глок, Стефан; Йоос, Феликс; Ким, Джехун; Кюн, Даниэла ; Остус, Дерик (2021), «Решение проблемы Обервольфаха», Журнал Европейского математического общества , 23 (8): 2511–2547, arXiv : 1806.04644 , doi : 10.4171/jems/1060 , MR 4269420
^ Киваш, Питер ; Стаден, Кэтрин (2022), «Обобщенная проблема Обервольфаха» (PDF) , Журнал комбинаторной теории , серия B, 152 : 281–318, arXiv : 2004.09937 , doi : 10.1016/j.jctb.2021.09.007 , MR 4332743
^ Jump up to: ^а ^б Хэггквист, Роланд (1985), «Лемма о разложении циклов», Циклы в графах (Бернаби, Британская Колумбия, 1982) , North-Holland Math. Студ., вып. 115, Амстердам: Северная Голландия, стр. 227–232, doi : 10.1016/S0304-0208(08)73015-9 , ISBN. 978-0-444-87803-8 , МР 0821524
^ Олспах, Брайан ; Хэггквист, Роланд (1985), «Некоторые наблюдения по проблеме Обервольфаха», Журнал теории графов , 9 (1): 177–187, doi : 10.1002/jgt.3190090114 , MR 0785659
^ Олспах, Брайан ; Шелленберг, П.Дж.; Стинсон, Др. ; Вагнер, Дэвид (1989), «Проблема Обервольфаха и факторы равномерных циклов нечетной длины», Журнал комбинаторной теории , серия A, 52 (1): 20–43, doi : 10.1016/0097-3165(89)90059-9 , МР 1008157
^ Хоффман, Д.Г.; Шелленберг, П.Дж. (1991), «Существование $C_{k}$ -факторизации $K_{2n}-F$ ", Дискретная математика , 97 (1–3): 243–250, doi : 10.1016/0012-365X(91)90440-D , MR 1140806
^ Jump up to: ^а ^б Брайант, Дэррин; Данцигер, Питер (2011), «О двудольных 2-факторизациях $K_{n}-I$ и проблема Обервольфаха» (PDF) , Journal of The Graph Theory , 68 (1): 22–37, doi : 10.1002/jgt.20538 , MR 2833961
^ Деза, А.; Франек, Ф.; Хуа, В.; Мешка, М.; Роза, А. (2010), «Решения проблемы Обервольфаха для порядков от 18 до 40» (PDF) , Журнал комбинаторной математики и комбинаторных вычислений , 74 : 95–102, MR 2675892
^ Брайант, Дэррин; Шарашкин, Виктор (2009), «Полные решения проблемы Обервольфаха для бесконечного множества порядков», Журнал комбинаторной теории , серия B, 99 (6): 904–918, doi : 10.1016/j.jctb.2009.03.003 , МР 2558441
^ Олспах, Брайан ; Брайант, Дэррин; Хорсли, Дэниел; Менхаут, Барбара; Шарашкин, Виктор (2016), «О факторизации полных графов в циркулянтные графы и проблема Обервольфаха» , Ars Mathematica Contemporanea , 11 (1): 157–173, arXiv : 1411.6047 , doi : 10.26493/1855-3974.770.150 , MR 3546656
^ Траэтта, Томмазо (2013), «Полное решение двухтабличных задач Обервольфаха», Журнал комбинаторной теории , серия A, 120 (5): 984–997, doi : 10.1016/j.jcta.2013.01.003 , MR 3033656

[lr-1] Jump up to: ^а ^б ^с Ленц, Ханфрид ; Рингель, Герхард (1991), «Краткий обзор математической работы Эгмонта Келера», Discrete Mathematics , 97 (1–3): 3–16, doi : 10.1016/0012-365X(91)90416-Y , MR 1140782

[hkr-2] Jump up to: ^а ^б Хуанг, Шарлотта; Коциг, Антон ; Роза, Александр (1979), «О вариации задачи Обервольфаха», Discrete Mathematics , 27 (3): 261–277, doi : 10.1016/0012-365X(79)90162-6 , MR 0541472

[opsd-3] Jump up to: ^а ^б Саласса, Ф.; Драготто, Г.; Траэтта, Т.; Буратти, М.; Делла Кроче, Ф. (2019), Объединение комбинаторного проектирования и оптимизации: проблема Обервольфаха , arXiv : 1903.12112 , Bibcode : 2019arXiv190312112S

[gjkko-4] Глок, Стефан; Йоос, Феликс; Ким, Джехун; Кюн, Даниэла ; Остус, Дерик (2021), «Решение проблемы Обервольфаха», Журнал Европейского математического общества , 23 (8): 2511–2547, arXiv : 1806.04644 , doi : 10.4171/jems/1060 , MR 4269420

[ks-5] Киваш, Питер ; Стаден, Кэтрин (2022), «Обобщенная проблема Обервольфаха» (PDF) , Журнал комбинаторной теории , серия B, 152 : 281–318, arXiv : 2004.09937 , doi : 10.1016/j.jctb.2021.09.007 , MR 4332743

[h-6] Jump up to: ^а ^б Хэггквист, Роланд (1985), «Лемма о разложении циклов», Циклы в графах (Бернаби, Британская Колумбия, 1982) , North-Holland Math. Студ., вып. 115, Амстердам: Северная Голландия, стр. 227–232, doi : 10.1016/S0304-0208(08)73015-9 , ISBN. 978-0-444-87803-8 , МР 0821524

[ah-7] Олспах, Брайан ; Хэггквист, Роланд (1985), «Некоторые наблюдения по проблеме Обервольфаха», Журнал теории графов , 9 (1): 177–187, doi : 10.1002/jgt.3190090114 , MR 0785659

[assw-8] Олспах, Брайан ; Шелленберг, П.Дж.; Стинсон, Др. ; Вагнер, Дэвид (1989), «Проблема Обервольфаха и факторы равномерных циклов нечетной длины», Журнал комбинаторной теории , серия A, 52 (1): 20–43, doi : 10.1016/0097-3165(89)90059-9 , МР 1008157

[hs-9] Хоффман, Д.Г.; Шелленберг, П.Дж. (1991), «Существование $C_{k}$ -факторизации $K_{2n}-F$ ", Дискретная математика , 97 (1–3): 243–250, doi : 10.1016/0012-365X(91)90440-D , MR 1140806

[bd-10] Jump up to: ^а ^б Брайант, Дэррин; Данцигер, Питер (2011), «О двудольных 2-факторизациях $K_{n}-I$ и проблема Обервольфаха» (PDF) , Journal of The Graph Theory , 68 (1): 22–37, doi : 10.1002/jgt.20538 , MR 2833961

[dfhmr-11] Деза, А.; Франек, Ф.; Хуа, В.; Мешка, М.; Роза, А. (2010), «Решения проблемы Обервольфаха для порядков от 18 до 40» (PDF) , Журнал комбинаторной математики и комбинаторных вычислений , 74 : 95–102, MR 2675892

[bs-12] Брайант, Дэррин; Шарашкин, Виктор (2009), «Полные решения проблемы Обервольфаха для бесконечного множества порядков», Журнал комбинаторной теории , серия B, 99 (6): 904–918, doi : 10.1016/j.jctb.2009.03.003 , МР 2558441

[abhms-13] Олспах, Брайан ; Брайант, Дэррин; Хорсли, Дэниел; Менхаут, Барбара; Шарашкин, Виктор (2016), «О факторизации полных графов в циркулянтные графы и проблема Обервольфаха» , Ars Mathematica Contemporanea , 11 (1): 157–173, arXiv : 1411.6047 , doi : 10.26493/1855-3974.770.150 , MR 3546656

[t-14] Траэтта, Томмазо (2013), «Полное решение двухтабличных задач Обервольфаха», Журнал комбинаторной теории , серия A, 120 (5): 984–997, doi : 10.1016/j.jcta.2013.01.003 , MR 3033656

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]