Every pair side by side, once

A round table with no couple together counted the ways to seat couples so that nobody sits beside their partner: a question about keeping certain pairs apart at one sitting, answered by inclusion and exclusion. Its opposite is a question about bringing every pair together over many sittings, and it has no formula at all.

A conference has $2n + 1$ guests, lasts $n$ nights, and dines at round tables whose sizes are fixed in advance, the same every night. Can the guests be seated so that every two of them sit side by side on exactly one night? Gerhard Ringel asked this at the mathematics institute at Oberwolfach in 1967, where the dining room had round tables and the guests changed places every evening, and it has been called the Oberwolfach problem ever since.

The arithmetic always fits. At a round table of any size, each guest has two neighbours, so a night supplies exactly $2n + 1$ side-by-side pairs, and $n$ nights supply $n(2n + 1)$ — exactly the number of pairs among $2n + 1$ guests. Nothing in the count rules any plan out. And yet some plans are impossible, and the reasons are not counts but shapes.

A night is a derangement #

There is a way to see the problem that puts it beside the hats of nobody gets their own hat. Read each round table clockwise and send every guest to the guest on their right. A night’s seating becomes a permutation of the guests with no fixed point — nobody is their own neighbour — and with cycles of exactly the table sizes. It is a derangement of a prescribed shape, and the guest on each person’s left is given by the inverse permutation.

On the square grid whose rows and columns are the guests, a permutation is a placement of non-attacking rooks, one per row and column, as in the cells a permutation must miss. A night together with its inverse puts two rooks in each row. The requirement that every pair sit side by side exactly once becomes a tiling statement: the $n$ nights and their inverses, $2n$ rook placements in all, must cover every cell off the diagonal of the grid exactly once. Each placement must also have the right cycle structure, and that is what separates this from the problems inclusion and exclusion can count. Counting derangements of one shape is a formula; fitting $2n$ of them together without overlap is a search.

One table, and a zigzag #

For a single table the problem has a complete answer, found in the nineteenth century and credited to Walecki by Édouard Lucas, who published it among his puzzles about round dances. Put one guest at the centre and the other $2n$ round a circle. Seat them on the first night by a zigzag: start at a point of the circle, cross to the next point on the opposite side, then back to the next on the first side, and so on, closing through the centre. On each later night turn the zigzag one place round.

The zigzag uses one chord of each length in each of two directions, and turning it through all $n$ positions uses every chord of every length exactly once; the centre guest meets two circle guests each night, a different pair each time. So every pair of guests is side by side exactly once. In the language of graphs this is a decomposition of the complete graph on $2n + 1$ points into $n$ cycles each passing through every point, and it is the same construction that a cycle for every pair set beside its own.

Six guests at two tables of three #

With several tables the question becomes a question about how the tables fit together, and the smallest case already fails. The problem needs an odd number of guests, so that each guest has an even number of others to meet two at a time. With an even number the standard variant pairs the guests into couples who never need to be seated together — every pair except a couple must sit side by side once — and the smallest plan with more than one table is six guests, three couples, two nights at two tables of three.

The first night seats two triangles. Whatever they are, the six pairs left over form a single hexagon, a cycle through all six guests. A hexagon alternates between two sets of three guests, and every one of its pairs joins one set to the other, so no three of its guests are pairwise joined: it contains no triangle. The second night needs two triangles and there are none. Six guests cannot be seated at two tables of three, and the reason is that what one night leaves is bipartite.

Every plan for up to eleven guests #

For larger plans the hexagon argument does not generalise, and the practical way to decide a plan is to search.

The symmetry matters enormously. Run naively, the search for nine guests at tables of four and five examined over a hundred million partial seatings before concluding that none completes; fixing the first night and the guest beside guest 1 on each later night brings that down to about twenty thousand, because every seating the naive search tried is, up to relabelling and reordering, one of the few the reduced search tries. The reductions are safe only because they are genuine symmetries of the problem: any valid schedule can be relabelled so that its first night is the fixed one, and its nights reordered so that the pairs at guest 1 come in increasing order. A reduction that is not a genuine symmetry would make the search faster and its crosses worthless, which is the same hazard the search for a smallest circuit and every other proof by exhaustion runs. The search builds the seating night by night and table by table, trying every guest for every seat and undoing a choice when it leads nowhere. It uses only the symmetry that is really there: for an odd number of guests the first night can be fixed, since every seating of one plan is a relabelling of every other; each later night can be taken to be the one that seats guest 1 beside the lowest-numbered guest not yet beside them; and each table can be read in one direction.

With that, every plan for six to eleven guests is decided in about a second. Nineteen of the twenty-two have a seating. Three do not: the two tables of three already met, nine guests at tables of four and five, and eleven guests at tables of three, three and five. The search proves the second and third impossible by trying everything, and nothing shorter than that is known for them.

The possible plans include some famous objects. Nine guests at three tables of three, over four nights, is a seating in which every pair shares a table exactly once — at a table of three everyone is beside everyone — and that is the smallest case of Kirkman’s schoolgirl problem: a resolvable triple system, the affine plane of order three. The general problem with every table of size three is the Kirkman problem in the variant where the days must be split into perfect sets of triples, and the Oberwolfach problem is its generalisation to tables of any sizes.

The even variant works the same way once the couples are excused. Eight guests at two tables of four, three nights: each table is a four-cycle, each night two of them, and every pair that is not a couple appears as neighbours exactly once. A seating for this plan is found at once.

Why an even number needs couples #

The odd number of guests is not a convention. Each night a guest has two neighbours, so after all the nights each guest has sat beside an even number of others. With $2n + 1$ guests each guest has $2n$ others to meet, an even number, and it works. With $2n$ guests each has $2n - 1$ others, an odd number, and no schedule of round tables can seat a guest beside an odd number of people exactly once each. Something has to give.

The standard fix pairs the guests into couples and excuses each couple: every guest then has $2n - 2$ others to meet, even again, and $n - 1$ nights supply exactly the pairs required. In the grid of rooks this removes a second diagonal — the couples’ cells — alongside the first, and the tiling has to cover everything else. The ménage problem kept couples apart at one table by forbidding exactly those cells; here the same cells are simply never used, over many nights at many tables.

The even variant has exceptions of its own: the six guests at two tables of three are one, and the same shortage of triangles returns at twelve guests with four tables of three, where a schedule would be a nearly Kirkman arrangement and none exists. For six guests the reason is the hexagon; for twelve the argument is a case analysis rather than a picture, but the shortage is again one of triangles. Tables of three are the most demanding tables there are, because a table of three uses up every pair among its guests at once and leaves nothing to spare, and every known exception, odd or even, has at least one of them or is the plan of four and five.

What an impossibility costs #

The asymmetry between the two answers is stark. A possible plan is usually decided within a few hundred steps, because the search stops at the first complete schedule and schedules are plentiful. An impossible plan has to be refuted in every branch: nine guests at tables of four and five took about twenty thousand steps even with the first night fixed, and eleven guests at three, three and five took seventeen million. The proof that a seating does not exist is the whole search tree, and its size is the price of the answer.

That price grows explosively with the number of guests. Beyond eleven guests only a few further exceptions are known, all involving tables of three, and the searches that settled every plan for up to forty guests needed far more than exhaustive enumeration: constructions that build schedules with symmetry, turned into searches over much smaller spaces. In all that range no new kind of exception appeared.

What makes a plan impossible #

Only the first of the three impossible plans has a reason as short as the hexagon. For nine guests at tables of four and five, and eleven at three, three and five, no argument of a paragraph’s length is known to show why every attempt fails; the exhaustive search is the proof. The obstructions are small and specific, they differ from plan to plan, and there is no uniform description of what makes a plan fail — which is why it is not known whether any further exceptions exist.

That is the character of decomposition problems generally. Whether a large complete graph can be cut into copies of a given small graph, with every edge used once, is a question whose answer is “yes, unless something small goes wrong”, and the small things that go wrong are found one at a time. Ringel’s other famous question, whether every tree with $n$ edges tiles the complete graph on $2n + 1$ points, is of the same kind, and a labelling every tree seems to have followed it to the graceful tree conjecture.

Solved in pieces, and for all large numbers #

The problem has been solved in large families. When all tables have the same size, Brian Alspach, Paul Schellenberg, Douglas Stinson and David Wagner settled the odd case in 1989, and Darryl Hoffman and Paul Schellenberg the even case in 1991; the only failures are tables of three for six and for twelve guests. When every table has an even size, Darryn Bryant and Peter Danziger settled it in 2011. When there are exactly two tables, Tommaso Traetta settled it in 2013, and the only failures are 3+3 and 4+5.

The families share a method: a construction with a large symmetry group, usually a rotation of the guests round a circle as in Walecki’s zigzag, which reduces the problem to choosing one night’s seating so that its rotations cover every pair. That turns a search over schedules into a search over single nights with a difference condition, which is small enough to solve by hand or by computer for each family. The method fails exactly where no symmetric schedule exists, and the exceptions are where it fails with nothing to replace it.

In 2021 Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus proved that for every sufficiently large number of guests, every table plan has a seating — and Peter Keevash and Katherine Staden proved it independently by other means. The proofs are probabilistic: most of the schedule is assembled at random from nearly correct pieces, and a carefully prepared reserve of structure absorbs the errors at the end. It is the method of what counting can prove exists turned constructive — random choices shown to succeed with positive probability, then repaired — and it needs the number of guests to be large for the same reason: the random part must be large enough that its errors are small compared with the reserve. They say nothing explicit about how large “sufficiently large” is, and it is very large.

What the search cannot show #

The search decides each plan up to eleven guests completely, and the three crosses are proofs. What it cannot do is reach far. Twelve guests already have more plans and a much larger space, and the growth is steep enough that the searches reaching forty guests had to use symmetric constructions rather than enumeration. Nothing drawn here bears on the range between forty and wherever the 2021 theorem begins.

The drawings show schedules found by a search that stops at the first answer. They are single examples among many, not canonical ones, and a different order of trying guests would find different schedules.

And the “couples” variant for even numbers of guests is one of two conventions. The other replaces the missing night by doubling one pair’s meeting instead of excusing a couple; the answers differ in detail, and the table here uses the convention most of the literature uses.

Still open: the middle #

The Oberwolfach problem is solved for single tables, for equal tables, for even tables, for two tables, for every plan up to forty guests and for every plan beyond some enormous number. Whether every plan outside the few known exceptions has a seating, for every number of guests, is still open, and the unsolved plans are exactly those with a middling number of guests and a mixture of odd table sizes. No one expects another exception, and no argument yet covers the middle.

Seating as the opposite of avoiding #

The ménage problem asked for the number of ways to keep pairs apart and got an exact formula by inclusion and exclusion, because avoiding is a condition that can be counted. Bringing every pair together exactly once is a condition of a different kind: not a count but a tiling, where every pair must be used and none twice, and where the obstruction, when there is one, is a shape like the hexagon that no count can see. The single table has a construction that works for every size; almost every other plan has a seating; and the few that do not are found only by looking. Between the zigzag that settles one table for ever and the searches that settle one plan at a time lies the whole of the problem, and the 2021 theorem shows that the answer is eventually always yes — for every plan, once the room is large enough, though by a proof that builds no zigzag and names no schedule.