The general problem is arranging a group of people into a number of tables so that everyone sits with everyone else. There are multiple versions for this.

  • The strict version is that all tables are the same size and that after the required number of rounds, everyone has shared a table with every other person exactly once
  • The lower version requires that each person shares a table with each other person at most once
  • The upper version requires that each person shares a table with each other person at least once

Some general thoughts. Each sitting defines a partition of the set of people, each part is one table.

A strict version is an affine plane. Example 25 people in 5 tables of 5, Point set is Z_5 x Z_5,we take the tables to be the lines L(a,b)={(x,y)| y=ax+b} and L(a)={(a,y)| y in Z_5}, the sitting is a parallel class (the 5 lines with the same slope a), so we have 6 sittings, L(a,b) for a=0,1,2,3,4 and then the parallel class of L(a).

More generally we want a resolvable 2-design. We want resolvable (v,k,1) designs. Resolvable is the parallelism. Maybe there is something like discrete hyperbolic geometry to deal with this, but we seem to have better combinatorial ideas below.

Versions include Kirkman's Schoolgirl Problem (15 children walk in groups of 3, can they do this so that all pairs of girls walk together exactly once over a whole week) {oeis}. This is the question as to resolvable (v,3,1) 2-designs, which if I understand it, exist iff v = 3 mod 6.

For pairs, resolvable (v,2,1) 2-designs exist only for even v, v >= 4.

Table size 4: Resolvable (v,k,1)- 2-designs. This paper says that nessesary numerical conditions are sufficient except for a case that need not concern us.

Just leave out some sittings on a strict version. Perhaps add a few nonexistant people to get a better distribution of people on tables with not all tables always full.

The “Dagstuhl Happy Diner problem” is the version where everyone meets at least once. {oeis}

Equitable Resolvable coverings also seem to be a more strict form, where we can allow people to meet at most twice. {ref}

If we have people sitting at round tables and only interacting with their neighbours, then we have the more difficult Oberwolfach Problem


part of category mathematics

  • table_seating.txt
  • Last modified: 2022-04-04 03:32
  • by nik