Sarah's Oberwolfach Problem Page
678-915-3421
shollida@spsu.edu
This is a work in progress. Comments should be sent to shollida@spsu.edu. I am working to convert the LaTeX to HTML, but it is a much slower process than I imagined. I also need to update the references, as some have changed. Back to my homepage.
In the language of Robert³ {Beeler, Gardner, Jamison}, the Host graph for these decompositions is typically the complete graph, the complete bipartite graph, or the complete equipartite graph (possibly minus a one-factor). The Prototype graph for these decompositions is a 2-factorization, or a collection of cycles.


Jump to History
Jump to References
Jump to Top

History
The original problem was posed by Gerhard Ringel in 1967 at a graph theory conference in Oberwolfach, Germany. The most casual way to state this problem is to ask if some number of people can be seated at a specified number of round tables for a series of meals, with these restrictions: Each person is assigned one seat for each meal, all the people are friends (but not very good friends) and wish to be seated next to each other, so every person must have as a neighbor every other person (but just once). (A neighbor at a dinner table is defined to be only the person either to the immediate right or the immediate left, not any of the people across the table.) The original statement of the problem is as follows: At a gathering, there are n mathematicians, and we wish to seat them at s round tables of seating capacities k₁,k₂,k₃,...,k_s (3&le k_i, and ∑_{1&le i&le s}k_i=n) for x meals, so that every mathematician sits next to every other mathematician exactly once, and every mathematician is seated exactly once for each meal. In graph theory terminology, we are decomposing K_n into x parallel classes, each consisting of cycles of lengths k₁,k₂,k₃,...,k_s (so ∑_{1&le i&le s}k_i=n, x=(n-1)/2, so n must be odd).

The problem was discussed in AH and elsewhere, each giving some family of results. The first large set of results was found by Alspach, Schellenberg, Stinson and Wagner in ASSW, in which the authors give constructions for the case when all tables have the same size k; a solution in this case is known as a C_k-factorization of K_n.

This problem has also been referred to as the Dagstuhl's happy diners problem by Maurice Queyranne of Vancouver, BC, who stated the problem as ``What is the minimum number of meals so that each of n conference participants can share at least one meal with every other participant when eating at tables of at most t persons? Are there simple algorithms approaching this minimum number?''

A specific case is known in design theory as the Kirkman schoolgirl problem. The Kirkman schoolgirl problem was posed in 1850 by the Rev. T. P. Kirkman K1, and solved in 1851 K2. In 1981, Ray-Chaudhuri and Wilson generalized the statement.

Theorem 1[Kirkman schoolgirl problem K2]
Fifteen young ladies in a school walk out three abreast for seven days in succession: it is possible to arrange them daily, so that no two walk twice abreast.
Q.E.D

A Kirkman triple system is a set (V,T) of points and triples such that every pair of points appears in exactly one triple, and the triples can be sorted into parallel classes such that every point appears exactly once in each parallel class, and each triple occurs in exactly one parallel class. A Kirkman triple system on n=|V| points is denoted KTS(n), and a solution to the original Kirkman school-girl problem is called a KTS(15).

Theorem 2[Ray-Chaudhuri and Wilson RCW]
K_n has a C₃-factorization if and only if n≡ 3 mod 6.
Q.E.D



Theorem 3[Alspach, Häggvist, Schellenburg, Stinson, Wagner AH, ASSW]
K_n has a C_k-factorization if and only if n is odd and k|n.
Q.E.D

Wildon W2 presents a conjecture that if s_i persons are to remain seated between meals, the maximum number of people that can remain seated throughout the decomposition, a_i=∑_0≤i≤n-1s_i is bounded by (n-1)²

The next variation of the original problem is called the spouse-avoiding variant, in which all of the preceding restrictions apply, with the addition of the restriction that the diners are married couples, and no person can be seated next to their spouse. It is assumed that each person has exactly one spouse. The spouse avoiding variation of the problem is phrased as follows: At a gathering, there are n couples, and we wish to seat them at s round tables, k₁,k₂,k₃,...,k_s (and ∑_{1 &le i&le s}k_i=2n) for x meals, so that every person sits next to every other person except their spouse exactly once (but never next to the spouse), and every person is seated exactly once for each meal. In graph theory terminology, we are decomposing K_{2n} minus a one-factor into x parallel classes, each consisting of cycles of lengths k₁,k₂,k₃,...,k_s (so ∑_{1&le i&le s}k_i=2n).

Chris Rodger R presents a spouse-friendly variant, in which each diner is seated with their spouse twice. When n is even, each vertex has odd degree, so one could add a matching instead of deleting a matching. More generally, add lambda 1 edges between vertices in the same part, and have lambda 2 edges between vertices in different parts. When all tables have size 4 this is solved when the number of vertices "a" in each part is even: MR2378028 (2008j:05047) Billington, Elizabeth J.; Rodger, C. A. Resolvable 4-cycle group divisible designs with two associate classes: part size even. Discrete Math. 308 (2008), no. 2-3, 303--307. The case when a is 1 mod 4 is close to done, with much stuff in: MR2381429 (2008j:05287) Rodger, C. A.(1-ABRN-S); Tiemeyer, Michael(1-ABRN-S) $C\sb 4$-factorizations with two associate classes. (English summary) Australas. J. Combin. 40 (2008), 217--228. 05C70

In many instances, the original Oberwolfach problem and the spouse-avoiding variant are both called ``The Oberwolfach Problem'', and it is left to the reader to determine which version is implied. Fortunately, one needs only to look at the sum of the table sizes, which gives the total number of vertices in the graph. If this number is even, one may assume that a one-factor is removed before the decomposition is formed.

In the case where not all tables have the same size, two cases are known to be impossible. The first impossible case is when there are 9 diners and the tables have sizes 4 and 5; the second is when there are 11 diners, and the tables have sizes 3, 3, and 5, as mentioned in K3, P2. The cases settled thus far are given below.

Theorem 4[Huang, Köhler, Kotzig, Rosa HKR, K4, K3]
The following Oberwolfach problems have solutions:

1. When one table has size 3, and the other has size k, for all odd k&ge 5,
2. When one table has size 3, and the other two tables have size 4k, for all k&ge 1,
3. When one table has size 3, and the other has size 8k-2, for all k&ge 1,
4. When one table has size 4, and the other has size k, for all even k&ge 4,
5. When the table sizes are k,k,2⌈ k/2 ⌉+2c, for all k&ge 3 and each c=0,2,3,&hellip,
6. When the table sizes are 2k+1,2k+1,2k+2, for all k&ge 1,
7. When the table sizes are 2k+1,4,&hellip ,4, for all k&ge 1 and arbitrarily many tables of size 4, and
8. When the table sizes are 2k+1,4k,&hellip ,4k, for all k&ge 1 and arbitrarily many tables of size 4k.

Q.E.D

Rumor has it that Darren Bryant has resolved ALL bipartite 2-factorizations.

Theorem 5[Bryant B]
For all k&ge 3, the Oberwolfach problem is solved for the case where each 2-factor consists of two cycles, one of length k and one of length k+1 (i.e., there is one table of size k and one of size k+1), and for the case where the 2-factors consist of two cycles of lengths k and k+2.
Q.E.D



Theorem 6[Hilton, Johnson HJ]
Let r&ge 3, k&ge 1 and n be integers. Then a solution to the Oberwolfach problem for k tables of size r and one table of size n-kr exists if

1. for even r, either n&ge 6kr-3 or n∈ {2r(2k+i)-3,2r(2k+i)-2|i=1,2,&hellip k-1},
2. for odd r, even k, either n&ge 6kr-3, or n∈ A∪ B, where A={2r(2k+2i+1)-1,2r(2k+2i+1),2r(2k+2i+2)-3,2r(2k+2i+2)-2|i=0,1,&hellip,⌊(k-3)/2⌋},B={2r(3k-1)-1,2r(3k-1)},
3. for odd r, odd k, either n&ge 6kr-1, or n∈ A (where A is as in part (2)),
4. n=4kr-2.

Q.E.D



Theorem 7[Hilton, Johnson HJ]
Let 3&le r&le 9, n&ge r+3 be integers. Then the cases when one table has size r and the other has size n-r has a solution except for the cases when both tables have size 3, and when one table has size 4 and the other size 5. Let 3&le r&le 4, n&ge 2r+3 be integers. Then the cases when there are two tables of size r and one of size n-2r has a solution except for the case when the table sizes are 3, 3 and 5.
Q.E.D



A complete multipartite graph is a graph with a partition of the vertices into partite sets such that all vertices in each partite set are mutually non-adjacent, and each vertex is adjacent to every other vertex not in its own partite set.

Another way of looking at the spouse-avoiding variation of the Oberwolfach problem is to consider the complete multipartite graph with n parts each of size 2. In this instance, as in the original, the problem has been entirely solved when all tables have the same size in HS and HKR.

Theorem 8[Alspach, Häggvist, Hoffman, et al. AH, ASSW, HS] (1,r,k)^*
For the complete multipartite graph with n parts of 2 vertices each, there is a C_k-factorization if and only if k|2n and (k,n)\notin {(3,3),(3,6)}.
Q.E.D



We next look at the ``Emily Post'' version, in which men and women must be alternated, as well as maintaining the conditions that every person is seated once for each meal, and has different neighbors at each meal. We are decomposing K_n,n, n even, into x parallel classes consisting of cycles of lengths k₁,k₂,k₃,...,k_s, (so ∑_{1&le i&le s}k_i=2n). Piotrowski entirely solved this version of the problem in Pio.

Theorem 9[Piotrowski Pio, P2]
The complete bipartite graph K_n,n has a 2- factorization in which each 2-factor consists of cycles of length k₁,k₂,&hellip ,k_s if and only if n and all k_i are even with ⊃ k_i=2n, except for n=6, s=2, k₁=k₂=6.
Q.E.D



At the Midwestern Conference on Combinatorics and Computing in 1999, Saad "the beekeeper" El-Zanati posed the following variation: At a gathering, there are n couples, and we wish to seat them at s round tables, of sizes k₁,k₂,k₃,&hellip ,k_s with all k_i even (and ∑_{1&le i&le s} k_i=2n) for x meals, alternating gender so that every person sits next to every person of opposite gender except their spouse exactly once, and every person is seated exactly once for each meal. The solution for all tables having the same size is:

Theorem 10[Hoffman, sh³ SHHH] (a,2,k)^*
The complete bipartite graph K_n,n with a 1-factor removed has a C_k-factorization if and only if n is odd, k is even, and k|2n.
Q.E.D



In 1999, Liu posed the problem in L: if there are m delegations of n people each, we would like to seat them so that every person has as a neighbor each person not in their own delegation. Or, restated, we want a complete equipartite graph with n parts each of size m, resolvably decomposed into cycles of uniform length k. The complete solution appears in L2.

Theorem 11[Liu L,L2] (a,r,k)
For k&ge 3 and r&ge 3, the complete r-partite graph with partite sets of size a has a C_k-factorization if and only if a(r-1) is even, ar is divisible by k, and (a,r,k)\notin {(2,3,3),(2,6,3),(6,3,3)}.
Q.E.D

Hoffman H presents the gregarious cycle decomposition, in which each cycle must have a vertex from each partite set.

In another variation, n people are seated to dinner so that every person has every other person as a neighbor exactly λ times. This variation was completely solved by Gvozdjak in 1997.

Theorem 12[Gvozdjak Gvo] Let λ, d and k be positive integers with k&ge 3. Then λ K_{dk} (or λ K_{dk}-I when λ is odd and dk is even, and I is a one-factor of λ K_{dk}) has a C_k-factorization if and only if none of the following is the case:

1. λ ≡ 2 (\textrm{mod } 4), d=2, k=3
2. λ odd, d=2, k=3
3. λ =1, d=4, k=3

Q.E.D



Another generalization of the Oberwolfach problem is known as the Hamilton-Waterloo problem, where K_n is factored into s 2-factors each consisting of cycles of lengths p₁, p₂, &hellip, p_u and the remaining t 2-factors consist of cycles of lengths q₁, q₂, &hellip, q_v (where necessarily ∑_{i=1}^u p_i = ∑ _{j=1}^v q_j = n and s+t=\frac{n-1}{2}). As with the original Oberwolfach problem, the majority of work to date has dealt with cycles of uniform lengths, so we let p_i=k, 1&le i&le u and q_j=l, 1&le j&le v. It is necessary that both k and l divide n, and that s+t=(n-1)/2. In this variation of the Oberwolfach problem the conference is held jointly at Hamilton and Waterloo with s days at Hamilton and t days at Waterloo where the round tables at Hamilton have size k and the tables at Waterloo have size l.

Theorem 13[Adams, Bryant, El-Zanati, Gavlas [ABEG]]
For each positive integer n, the complete graph K_{10n} can be factored into \alpha C₅-factors and \beta 1-factors for all nonnegative integers \alpha and \beta with 2\alpha + \beta =10n-1.
Q.E.D

Theorem 14[Adams, Billington, Bryant, El-Zanati ABBE]
There exists a solution for certain s and t to the Hamilton-Waterloo problem for all (k,l)∈{(4,6), (4,8), (4,16), (8,16)}, for any n, and (k,l)∈{(3,15), (5,15)} for odd n and (k,l)=(3,5) for certain odd n.

Q.E.D



The problem that I focused on in my dissertation [SHHH] is the following: Given r delegations of a people each, the Captain of the ship will marry couples so that no person is married to anyone in their own delegation, and everyone is married exactly once. Thus, the Captain of the ship will decide who is to be married to whom. The Ship's Captain will now seat these people to dinner for x meals at s round tables of uniform size k, (sk=ar), with the restriction that each person has every other person except those in their own delegation and their own spouse, as a neighbor exactly once. In graph theoretic terms, we will not attempt to do this for all one-factors, but show that we can decompose the complete equipartite graph minus a one-factor into x parallel classes consisting of cycles of length k.

Theorem 15[Hoffman, sh³ [SHHH]]
The complete equipartite graph with r parts each of size a minus a one-factor can be resolvably decomposed into k-cycles if r is even, a is odd, k|ra, and k is even.


Jump to Top

References
[ABBE] P. Adams, E. J. Billington, D. Bryant, and S. I. El-Zanati, On the Hamilton-Waterloo Problem, Graphs and Combinatorics 18(2002), 31-51.
[ABEG] P. Adams, D. Bryant, S. I. El-Zanati, and H. Gavlas, {K₂,C₅}-Factorizations of the Complete Graph, to appear.
[AH] B. Alspach, and R. Häggkvist, Some observations on the Oberwolfach problem, J Graph Theory 9(1985), 177-187.
[ASSW] B. Alspach, P.J. Schellenburg, D.R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, Journal of Combinatorial Theory, Ser. A 52(1989), 20-43.
[BFM] J.-C. Bermond, O. Favaron, and M. Maheo, Hamilton Decomposition of Cayley Graphs of Degree 4, Journal of Combinatorial Theory, Ser. B 46(1989), 142-153.
[B] D. Bryant, On the Oberwolfach Problem with Two Similar Length Cycles, Graphs Combin., 17(2001), no. 2, 199-206.
[BEZR] D. Bryant, S. El-Zanati, and C. A. Rodger, Maximal Sets of Hamilton Cycles in K_n,n, J Graph Theory, 33(2000), 25-31.
[DAVEN] M. S. Daven, Connectivity of Two Families of Regular Graphs, Ph.D. dissertation, Auburn University, 1999.
[Gvo] P. Gvozdjak, On the Oberwolfach problem for complete multigraphs, Discrete Mathematics, 173(1997), 61-69.
[H] Hoffman, Gregarious cycles
[HJ] A. J. W. Hilton and Matthew Johnson, Some results on the Oberwolfach problem, J. London Math Soc. (2) 64(2001), 513-522.
[HS] D.G. Hoffman and P.J. Schellenburg, The existence of C_k-factorizations of K_{2n}-F, Discrete Mathematics, 97(1991), 243-250.
[SHHH] S. H. Holliday, The Ship Captain's Problem, Ph.D. dissertation, Auburn University, 2003.
[HKR] C. Huang, A Kotzig, and A. Rosa, On a variation of the Oberwolfach problem, Discrete Mathematics 27(1979), 261-277.
[K1] Rev. T. P. Kirkman, Query VI., Lady's and Gentleman's Diary, (1850), 48.
[K2] Rev. T. P. Kirkman, Solution to Query VI., Lady's and Gentleman's Diary, (1851), 48.
[K4] E. Köhler, Das Oberwolfacher problem, Mitt. Math. Ges. Hamburg 10(1973), 52-57.
[K3] E. Köhler, \"Uber das Oberwolfacher problem, in: Beiträge zur Geometrishcen Algebra (H. Arnold, W. Benz, H. Wefelsheid: eds.), Birkhäuser Verlag, Basel, 1977, 189-201.
[LR] C. C. Lindner, and C. A. Rodger, Design Theory, CRC Press, Boca Raton, FL, 1997.
[L] J. Liu, A Generalization of the Oberwolfach Problem and C_t-factorizations of Complete Equipartite Graphs, Journal of Combinatorial Designs 8(2000), 42-49.
[L2] J. Liu, A Complete Solution to the Generalized Oberwolfach Problem with Uniform Table Sizes, J. Combin. Theory Ser. A. 101 (2003), no. 1, 20--34.
[Pio] W. L. Piotrowski, The solution of the bipartite analogue of the Oberwolfach problem, Discrete Mathematics 97(1991), 339-356.
[P2] W. L. Piotrowski, Untersuchungen \"uber das Oberwolfacher Problem, preprint.
[R] Chris Rodge, Presentation, October 2008 AMS sectional.
[RCW] D. K. Ray-Chaudhuri, and R. M. Wilson, Solution of Kirkman's school-girl problem, Proc. Symp. Pure Math., Amer. Math. Soc., Providence, RI, 19(1971), 187-203.
[Storer] T. Storer, Cyclototmy and Difference Sets, Markham Publishing Company, Chicago, IL, 1967.
[W] D. B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996.
[W2] Wildon, email communication, 2008.
Jump to Top