Oberwolfach Problem

The Oberwolfach problem is an unsolved problem in mathematics that may be formulated either as a problem of scheduling seating assignments for diners,
or more abstractly as a problem in graph theory, on the edge cycle covers of complete graphs. It is named after the Oberwolfach Research Institute for Mathematics, where the problem was posed in 1967 by Gerhard Ringel. It is known to be true for all sufficiently-large complete graphs.

Formulation

In conferences held at Oberwolfach, it is the custom for the participants to dine together in a room with circular tables, not all the same size, and with assigned seating that rearranges the participants from meal to meal. The Oberwolfach problem asks how to make a seating chart for a given set of tables so that all tables are full at each meal and all pairs of conference participants are seated next to each other exactly once. An instance of the problem can be denoted as $OP(x,y,z,\dots)$ where $x,y,z,\dots$ are the given table sizes. Alternatively, when some table sizes are repeated, they may be denoted using exponential notation; for instance, $OP(5^3)$ describes an instance with three tables of size five.

Formulated as a problem in graph theory, the pairs of people sitting next to each other at a single meal can be represented as a disjoint union of cycle graphs $C_x+C_y+C_z+\cdots$ of the specified lengths, with one cycle for each of the dining tables. This union of cycles is a 2-regular graph, and every 2-regular graph has this form. If $G$ is this 2-regular graph and has $n$ vertices, the question is whether the complete graph $K_n$ of order $n$ can be represented as an edge-disjoint union of copies of $G$.

In order for a solution to exist, the total number of conference participants (or equivalently, the total capacity of the tables, or the total number of vertices of the given cycle graphs) must be an odd number. For, at each meal, each participant sits next to two neighbors, so the total number of neighbors of each participant must be even, and this is only possible when the total number of participants is odd. The problem has, however, also been extended to even values of $n$ by asking, for those $n$, whether all of the edges of the complete graph except for a perfect matching can be covered by copies of the given 2-regular graph. Like the ménage problem (a different mathematical problem involving seating arrangements of diners and tables), this variant of the problem can be formulated by supposing that the $n$ diners are arranged into $n/2$ married couples, and that the seating arrangements should place each diner next to each other diner except their own spouse exactly once.

Known results

The only instances of the Oberwolfach problem that are known not to be solvable are $OP(3^2)$, $OP(3^4)$, $OP(4,5)$, and $OP(3,3,5)$. It is widely believed that all other instances have a solution.
This conjecture is supported by recent non-constructive and asymptotic solutions for large complete graphs of order greater than a lower bound that is however unquantified.

Cases for which a constructive solution is known include:
*All instances $OP(x^y)$ except $OP(3^2)$ and $OP(3^4)$.
*All instances in which all of the cycles have even length.
*All instances (other than the known exceptions) with $n\le 60$.
*All instances for certain choices of $n$, belonging to infinite subsets of the natural numbers.
*All instances $OP(x,y)$ other than the known exceptions $OP(3,3)$ and $OP(4,5)$.

Related problems

Kirkman's schoolgirl problem, of grouping fifteen schoolgirls into rows of three in seven different ways so that each pair of girls appears once in each triple, is a special case of the Oberwolfach problem, $OP(3^5)$. The problem of Hamiltonian decomposition of a complete graph $K_n$ is another special case, $OP(n)$.

Alspach's conjecture, on the decomposition of a complete graph into cycles of given sizes, is related to the Oberwolfach problem, but neither is a special case of the other.
If $G$ is a 2-regular graph, with $n$ vertices, formed from a disjoint union of cycles of certain lengths, then a solution to the Oberwolfach problem for $G$ would also provide a decomposition of the complete graph into $(n-1)/2$ copies of each of the cycles of $G$. However, not every decomposition of $K_n$ into this many cycles of each size can be grouped into disjoint cycles that form copies of $G$, and on the other hand not every instance of Alspach's conjecture involves sets of cycles that have $(n-1)/2$ copies of each cycle.

References

{{reflist, 30em, refs=

{{citation
, last1 = Alspach , first1 = Brian , author1-link = Brian Alspach
, last2 = Bryant , first2 = Darryn
, last3 = Horsley , first3 = Daniel
, last4 = Maenhaut , first4 = Barbara
, last5 = Scharaschkin , first5 = Victor
, issue = 1
, journal = Ars Mathematica Contemporanea
, mr = 3546656
, pages = 157–173
, title = On factorisations of complete graphs into circulant graphs and the Oberwolfach problem
, url = https://amc-journal.eu/index.php/amc/article/view/770
, volume = 11
, year = 2016, doi = 10.26493/1855-3974.770.150 , arxiv = 1411.6047

{{citation
, last1 = Alspach , first1 = Brian , author1-link = Brian Alspach
, last2 = Häggkvist , first2 = Roland
, doi = 10.1002/jgt.3190090114
, issue = 1
, journal = Journal of Graph Theory
, mr = 785659
, pages = 177–187
, title = Some observations on the Oberwolfach problem
, volume = 9
, year = 1985

{{citation
, last1 = Alspach , first1 = Brian , author1-link = Brian Alspach
, last2 = Schellenberg , first2 = P. J.
, last3 = Stinson , first3 = D. R. , author3-link = Doug Stinson
, last4 = Wagner , first4 = David
, doi = 10.1016/0097-3165(89)90059-9
, issue = 1
, journal = Journal of Combinatorial Theory
, mr = 1008157
, pages = 20–43
, series = Series A
, title = The Oberwolfach problem and factors of uniform odd length cycles
, volume = 52
, year = 1989, doi-access = free

{{citation
, last1 = Bryant , first1 = Darryn
, last2 = Danziger , first2 = Peter
, doi = 10.1002/jgt.20538
, issue = 1
, journal = Journal of Graph Theory
, mr = 2833961
, pages = 22–37
, title = On bipartite 2-factorizations of $K_n-I$ and the Oberwolfach problem
, url = https://people.smp.uq.edu.au/DarrynBryant/Preprints/BryDanBipartiteOberwolfach.pdf
, volume = 68
, year = 2011

{{citation
, last1 = Bryant , first1 = Darryn
, last2 = Scharaschkin , first2 = Victor
, doi = 10.1016/j.jctb.2009.03.003
, issue = 6
, journal = Journal of Combinatorial Theory
, mr = 2558441
, pages = 904–918
, series = Series B
, title = Complete solutions to the Oberwolfach problem for an infinite set of orders
, volume = 99
, year = 2009, doi-access = free

{{citation
, last1 = Deza , first1 = A.
, last2 = Franek , first2 = F.
, last3 = Hua , first3 = W.
, last4 = Meszka , first4 = M.
, last5 = Rosa , first5 = A.
, journal = Journal of Combinatorial Mathematics and Combinatorial Computing
, mr = 2675892
, pages = 95–102
, title = Solutions to the Oberwolfach problem for orders 18 to 40
, url = http://www.cas.mcmaster.ca/~deza/jcmcc2010.pdf
, volume = 74
, year = 2010

{{citation
, last1 = Glock , first1 = Stefan
, last2 = Joos , first2 = Felix
, last3 = Kim , first3 = Jaehoon
, last4 = Kühn , first4 = Daniela , author4-link = Daniela Kühn
, last5 = Osthus , first5 = Deryk
, arxiv = 1806.04644
, doi = 10.4171/jems/1060
, issue = 8
, journal = Journal of the European Mathematical Society
, mr = 4269420
, pages = 2511–2547
, title = Resolution of the Oberwolfach problem
, volume = 23
, year = 2021

{{citation
, last = Häggkvist , first = Roland
, contribution = A lemma on cycle decompositions
, doi = 10.1016/S0304-0208(08)73015-9
, mr = 821524
, pages = 227–232
, publisher = North-Holland , location = Amsterdam
, series = North-Holland Math. Stud.
, title = Cycles in graphs (Burnaby, B.C., 1982)
, volume = 115
, year = 1985

{{citation
, last1 = Huang , first1 = Charlotte
, last2 = Kotzig , first2 = Anton , author2-link = Anton Kotzig
, last3 = Rosa , first3 = Alexander
, doi = 10.1016/0012-365X(79)90162-6
, issue = 3
, journal = Discrete Mathematics
, mr = 541472
, pages = 261–277
, title = On a variation of the Oberwolfach problem
, volume = 27
, year = 1979, doi-access = free

{{citation
, last1 = Hoffman , first1 = D. G.
, last2 = Schellenberg , first2 = P. J.
, doi = 10.1016/0012-365X(91)90440-D
, issue = 1–3
, journal = Discrete Mathematics
, mr = 1140806
, pages = 243–250
, title = The existence of $C_k$-factorizations of $K_{2n}-F$
, volume = 97
, year = 1991, doi-access = free

{{citation
, last1 = Keevash , first1 = Peter , author1-link = Peter Keevash
, last2 = Staden , first2 = Katherine
, doi = 10.1016/j.jctb.2021.09.007
, journal = Journal of Combinatorial Theory
, mr = 4332743
, pages = 281–318
, series = Series B
, title = The generalised Oberwolfach problem
, url = http://klstaden.site11.com/docs/factors.pdf
, volume = 152
, year = 2022

{{citation
, last1 = Lenz , first1 = Hanfried , author1-link = Hanfried Lenz
, last2 = Ringel , first2 = Gerhard , author2-link = Gerhard Ringel
, doi = 10.1016/0012-365X(91)90416-Y
, issue = 1–3
, journal = Discrete Mathematics
, mr = 1140782
, pages = 3–16
, title = A brief review on Egmont Köhler's mathematical work
, volume = 97
, year = 1991, doi-access = free

{{citation
, last = Traetta , first = Tommaso
, issue = 5
, journal = Journal of Combinatorial Theory
, mr = 3033656
, pages = 984–997
, series = Series A
, title = A complete solution to the two-table Oberwolfach problems
, doi = 10.1016/j.jcta.2013.01.003
, volume = 120
, year = 2013, doi-access = free

{{citation
, last1 = Salassa , first1 = F.
, last2 = Dragotto , first2 = G.
, last3 = Traetta , first3 = T.
, last4 = Buratti , first4 = M.
, last5 = Della Croce , first5 = F.
, title = Merging Combinatorial Design and Optimization: the Oberwolfach Problem
, year = 2019, arxiv = 1903.12112
, bibcode = 2019arXiv190312112S

Mathematical problems
Unsolved problems in graph theory