The Problem Statement: What is the minimum number of meals so that each of the n conference participants can share at least one meal with every other participant when eating at tables of at most k persons? We call this number T(n,k).

In particular, we have an unlimited number of tables, and we do not require that any two participants have a meal together exactly once, or that every table is fully occupied.

Legend:

• We use lower-case letters a-z (or ↘) to justify lower bounds and upper-case letters A-Z (or ↖) to justify upper bounds. These bounds are explained under Lower Bounds and Upper Bounds.
• No explanation is given when n ≤ k or k = 2 or the value can be derived from the inequality T(n,k) ≤ T(n+1,k).
• We have the relation T(n+1,k+1) ≤ T(n,k) (see Relations). If we use this as an upper bound we write ↖ (the value in this cell is at most the value to the top-left of this cell) and as a lower bound we write ↘ (this value is at least the value to the bottom-right).
• The bolded values indicate perfect solutions (see Terminology).
• The upper bound J has not been verified by the authors of this table.

• Dual problem statement: What is the maximum number of conference participants so that each participant can share at least one of the T meals with any other participant when eating at tables of at most k participants?
• This is the maximal n = n(T,k) such that T(n,k) ≤ T.
• This table has the same information as the previous one, organized differently.
• This table is harder to read, but much more informationally dense.
• If you want to read a value of T(n,k) from this table:
  • Look at the k-th column.
  • Find the smallest T that possibly satisfies n(T,k) ≥ n. Then T(n,k) ≥ T.
  • Find the smallest T' that definitely satisfies n(T',k) ≥ n. Then T(n,k) ≤ T'.
  • For example, to find T(14,3) we see that T = 7 is the first value where n(T,3) ≥ 14 (since n(7,3) = 15), so T(14,3) = 7.
  • For example, to find T(24,6), as of August 2019 we see that n(5,6) is in the range 18-24 and n(6,6) is in the range 26-30. We see that n(5,6) ≥ 24 is possible but not guaranteed and that n(6,6) ≥ 24 is guaranteed. So T(24,6) is either 5 or 6.
  • Using similar logic we can conclude that T(25,6) = T(26,6) = 6. Even though the exact values in the table are not known, we do know that T = 6 is the smallest value where n(T,6) is at least n (when n is 25 or 26).
  • With only this information it is possible that T(27,6) > 6.
• In this table the upper-case (or ←) letters show why the entry is not smaller (why it is possible to have a solution with this number of participants) and the lower-case (or →) letters show why the entry is not larger (why it is not possible to have a solution with one more partipant).
• The use of T(n+1,k+1) ≤ T(n,k) is indicated with ← and →. ← means that this cell strictly greater than the cell to the left, while → means that this cell is strictly smaller than the cell to the right.
• Sometimes two cells point at each other (e.g. (T,k) = (4,4) and (T,k) = (4,5)). This looks circular, but it is not. It means that the upper bound of the left cell follows from the upper bound of the right cell and the lower bound of the right cell follows from the lower bound of the left cell.
• For k > 3 and T > 12 we only put values where either the lower bound or the upper bound is nontrivial (not obtained by ← → a c B)
• The upper bound J has not been verified by the authors of this table.

• Given a table assignment for 1 or more meals. We say that this is a valid solution if every participant meet every other participant at least once.
• A valid solution with n participants and table size of at most k is called a (n,k)-solution.
• Given a valid solution. We say that it is an optimal solution if there is no valid solution (with the same n and k) with fewer days.
• Given a valid solution. We say that it is a perfect solution if every participant meets every other participant exactly once and all tables have k participants every meal.
• A distribution is a seating assignment for a single meal.
• A configuration is an assignment for the number of participants to each table for a single meal (but not stating which participant goes where).
• We say that a configuration C is dominated if it has two tables with a and b participants and a + b ≤ k.
  • In this case, we can merge these two tables and still have a valid solution, so we may assume we have a solution without dominated configurations.
• A connection is a pair of people sitting at the same table. A new connection is a connection that was not yet formed on a previous day. The number of connections a table of size l makes is s(l) = l(l-1)/2, not all of which might be new connections. The number of new connections s(c) of a configuration c is the sum.
• The optimal configuration opt is the configuration with the most connections. It has ⌊ n / k ⌋ tables of size k and one table of size n mod k, and it is unique.
• If k < n ≤ k^2 - 1 then it is not possible to create 2 * s(opt) new connections after two days, since at least one pair of participants has to sit at the same table on both days, or a configuration other than the optimal configuration has to be used. Let s(c1,c2) the maximum number of new connections c2 can make on day 2 is c1 was used on day 1.

• T(n+1,k) ≥ T(n,k) ≥ T(n+1,k+1) ≥ T(n,k+1).
  • If a value in the table can be derived from the first inequality, no other explanation is given.
  • The second inequality follows by treating two of the n+1 people as a single person (always seating them together), and then applying a (n,k)-solution.
• T(n,k) ≤ T(n,m) * T(m,k).
  • If we have a seating arrangement for n participants at table size m, then we can give a seating arrangement for table size k by simulating tables of size m over T(m,k) meals.
  • This subsumes the relation T(n+1,k) ≥ T(n,k) ≥ T(n,k+1) above since T(k,k+1)=1.
  • If there is a perfect (n,m)-solution and a perfect (m,k)-solution then there is a perfect (n,k)-solution.

• Necessarily, every perfect solution is optimal.
• Necessary requirements for a perfect (n,k)-solution to exist are k - 1 | n - 1 and k | n (or n = 1).
• A perfect (n,k)-solution exists iff T(n,k) = (n-1)/(k-1).
• The perfect solutions are in boldface in the tables above.
• Perfect solutions are also called Kirkman Systems in the literature.
• Perfect solutions are also characterized by the Social Golfer Problem or resolvable 2-designs.
• We give various explicit perfect solutions in literature.md
• The upper bounds F, H and (some of) J all give families of perfect solutions.

• T(n,k) = 1 if n ≤ k trivially.
• T(n,2) = n if n is odd, T(n,2)=n-1 if n is even.
  • The lower bound is given by a.
  • The upper bound can be obtained as follows.
    • Suppose n = 4m: split it up in 2 groups of size 2m, first do those groups independently in 2m-1 days, then in the next 2m days on day i let person j in group 1 sit with person i+j (mod 2m) in group 2.
      • This also follows from upper bound A.
    • Suppose n = 2m with m odd:
      • For the first m days: on day i let person i sit with i+m and person i+j with i-j.
      • For the next m-1 days, on day 2k-1 and 2k let person i sit with the persons i+2k-1 and i-(2k-1). If i is even it will sit with i+2k-1 first, and if i is odd it will sit with i-(2k-1) first.
    • Suppose n is odd, then we can use the solution for n+1 participants.
• If k is even and k < n ≤ 2k then T(n,k) = 3. Also, if k is odd and k < n < 2k then T(n,k) = 3. These are all the values for (n,k) where T(n,k) = 3.
  • If n > k then T(n,k) ≥ 3 is explained by the lower bound d.
  • If k is even and n ≤ 2k then T(n,k) ≤ 3 is explained by the upper bound B.
  • If k is odd and n < 2k then T(n,k) ≤ 3 is explained by T(n,k) ≤ T(n-1,k-1) ≤ 3, using the previous bullet point.
  • For smaller n we have T(n,k) = 1 trivially and for larger n we have T(n,k) ≥ 4 by lower bound f.

• ↘/→: The relation T(n,k) ≥ T(n+1,k+1) can sometimes be used as a lower bound. See Relations.
• T(n,k) ≥ (n-1)/(k-1) (special case of a). Every participant can see only k-1 participants per meal, and needs to see n-1 participants.
• a: Suppose n = m*k+l with 0 ≤ l < k. There are n(n-1)/2 pairs. At most m*k*(k-1)/2+l*(l-1)/2 pairs can be formed per meal. So T(n,k) is at least equal to the quotient of these 2.
• b: obsolete.
• c: If n = m*k+1 then the bound from a is n(n-1)/(m*k*(k-1)) = n/(k-1). Suppose k - 1 | n (i.e. n ≡ -(k-1) mod k(k-1)) and k > 2. Then T(n,k) ≥ n/(k-1)+1, because if it's possible after n/(k-1) days, we need to form m*k*(k-1)/2 new connections every meal. This means that
  • Every table needs to be size k, except for 1 table of size 1 every meal.
  • Nobody can meet the same person twice. This means that after every meal, the number of participants participant A has met is divisible by k-1, so it can never equal n-1.
• d: If n > k then T(n,k) ≥ 3.
  • It cannot be done in 2 days, because on day 1 there are at least 2 tables. All participants on table 1 need to be sit with all participants not on table 1 on day 2, but that means that everyone needs to sit together on day 2. Contradiction.
• e: proven for this special case, see below.
• f: If k is odd then T(2k,k) ≥ 4.
  • This also implies that for even k we have T(2k+1,k) ≥ T(2(k+1),k+1) ≥ 4
  • Note that all non-dominated distributions use 2 or 3 tables.
  • Suppose this can be done in 3 days.
  • Suppose the assignment for day 1 is {a, b, c} with k ≥ |a| ≥ |b| ≥ |c| ≥ 0. We may assume that |a| is the largest among all table sizes on all days.
  • Let x ∈ a and let x ∈ a₂ ⊆ a, b₂ ⊆ b and c₂ ⊆ c be the participants of the table containing x on day 2. We may assume that b₂ ≠ ∅ (by interchanging day 2 and 3), and from this we can conclude that a₂ ≠ a (otherwise |a| was not largest).
  • Now on day 3, all of the following must be true
    • Everyone in a₂ has to meet everyone in b \ b₂ and c \ c₂, so they must all be at the same table.
    • Everyone in a \ a₂ has to meet everyone in b₂ and c₂.
    • Everyone in b₂ has to additionally meet everyone in c \ c₂.
  • Since not everyone can be at the same table, this means that c₂ = c.
  • The table assignment on day 3 must be { a₂ ∪ (b \ b₂), (a \ a₂) ∪ b₂ ∪ c }.
  • b₂ ≠ b, since otherwise |a₂ ∪ b₂ ∪ c₂| > k.
  • Everyone in b \ b₂ has never seen anyone in c, which means that c = ∅.
  • This means that |a| = |b| = k
  • Everyone in a \ a₂ and everyone in b \ b₂ must have seen each other on day 2, so the table assignment on day 2 was { a₂ ∪ b₂ (a \ a₂) ∪ (b \ b₂) }.
  • Since k is odd, we have max(|a₂|, |a \ a₂|) > k / 2 and max(|b₂|, |b \ a₂|) > k / 2, which means that on either day 2 or day 3 there was a table with more that k participants. Contradiction!
• g: Improvement of a when k < n ≤ k^2 - 2
  • The idea for this lower bound is that every day after the first day many connections are already present on day 1. This means that the number of connections you can make on most (all but one) days is much less than calculated at a.
  • On day 1 at most s(opt) connections can be added
  • On subsequent days fewer connections can be added. We can give an upper bound, and run through all (sensible) pairs of non-dominated configurations to find the maximal number s of connections that can be added on day 2 (where we can choose the configuration of day 1 to be as optimal as possible).
  • This means that after T+1 days at most s(opt) + T * s connections can be made, which gives a lower bound for the number of days.
  • The Mathematica function doing this is given in lowerbound.txt. It is not optimal, and is not necessarily increasing in n. In some cases we can probably increase the lower bound by 1 using a similar but more precise argument.
• h: If there is no perfect (n,k)-solution but k | n and k - 1 | n - 1, then T(n-1, k) > (n - 1) / (k - 1).
  • To see this, first notice that T(n-1, k) ≥ (n - 1) / (k - 1) is given by the lower bound a.
  • The only way equality can hold is if all but 1 table has size k every meal, and seating every participant exactly once with every other participant.
  • This means that every participant sits at a table of size k - 1 exactly once.
  • We can add a participant at the empty seat every meal, and then we get a perfect (n, k)-solution, which contradicts the assumption.
  • For (n,k) = (36,6) there is no perfect solution, see Latin Squares.
• i: Let n = mk + l, and let d be the lower bound given by a. Suppose that (d-1)(k-1) + (l-1) < n-1, then there is no solution in d days with an optimal configuration.
  • The reason is as follows: Let A be any participant sitting at the smallest table in the optimal configuration: it can meet at most l-1 participants that meal, and at most k-1 participants every other meal, which is not enough.
  • This means that for any solution in d days, the smallest table size is (n-1)-(d-1)(k-1).
  • We can now check whether it is possible to create at least n(n-1) / 2d connections in a single day, with this extra condition on the smallest table size. If not, then T(n,k) > d.
  • We don't use i if a or c applies. This bound is always at least as strong as a or c. When n < k^2 most of the time g is stronger.
• Priority of labels: nothing (it follows from the cell above), then ↘/→, then a/c, then d/f/g/h/i, then e
  • If a label with earlier (higher) priority applies, we don't write this label. We do write multiple labels with the same priority.

• ↖/←: The relation T(n+1,k+1) ≤ T(n,k) can be used as an upper bound. See Relations.
• A: T(km,k) ≤ T(m,k) + m if m is coprime with (k-1)!.
  • Divide the participants into k groups of m people. On the first T(m,k) days, everyone meets every participant of their group.
  • Number the participants in each group using the remainder classes modulo m.
  • On the m days after that, on day i (0≤i<m) make a table with participant j from the first group, j+i from the second group, j+2i from the third group, and so on. If m has no divisor smaller than k, then every participant will meet every participant from another group this way.
  • In particular, this shows that if there is a perfect (m,k)-solution and m is coprime with (k-1)! then there is a perfect (km,k)-solution. In particular, if p is prime there is a perfect (p^k,p)-solution.
• B: T(nl,kl) ≤ T(n,k). This can be seen by making n groups of l people each and always seating all people in a single group together.
• C: obsolete.
• D: obsolete.
• E: found solution for this special case, see below. (We don't use E if another letter applies.)
• F, G: a solution has been given in the literature. An explicit solution is given in literature.md.
  • The result in literature was solving a different problem.
  • See Relation to the Social Golfer Problem.
  • See Relation to Block Designs.
• H: If k is a prime power and n is a power of k, then there is a perfect (n,k)-solution.
  • Consider the field F of order k, and a vector field V with cardinality n over F.
  • For every 1-dimensional subspace L of V the sets of 1-dimensional affine spaces parallel to L forms a partition of V. This defines a table assignment for a single meal.
  • The set of all table assignments determined by all 1-dimensional subspaces in this way forms a perfect (n,k)-solution. The reason that it is perfect follows from the fact that 1-dimensional affine spaces stand in bijective correspondence to pairs of points in V.
  • This idea is due to Neil Strickland.
  • If k is prime (not just a prime power) and n is a power of k, then the existence of a perfect (n,k)-solution also follows from upper bound A.
• J: see Kirkman Systems.
• K: From a perfect solution, we can get new solutions with the table size two larger.
  • Given an (n,k)-solution in T days and a subset A ⊆ n of participants such that no i+1 participants from A sit at the same table during the same meal (let's say that A is i-good in this case), then there is a (n+|A|,k+i)-solution in T days, by replacing everyone in A with a pair of people.
  • If we start with a perfect (n,k)-solution (with k > 2) and a 2-good set A such that |A|+(k-2)|A|(|A|-1)/2 < n, then we can find a 2-good set with one more participant. The reason is that every pair of people in A sit at the same table exactly once, with k-2 other people. Therefore, at most |A|+(k-2)|A|(|A|-1)/2 other people cannot be added to A while keeping A 2-good, which means that there is someone we can add to A so that the new set is 2-good.

• Priority of labels: nothing (it follows from the cell below), then ↖/←, then A/B/H/K, then F/G, then E, then J.
  • If a label with earlier (higher) priority applies, we don't write this label. We do write multiple labels with the same priority.

• The Social Golfer Problem is a problem similar to Dagstuhl's Happy Diner Problem: given a group of m*k golfers playing in m groups of k golfers each day. No two golfers play together more than once. What is the maximum possible of days they can play? Call this number G(m,k).
• From a good solution G(m,k) of the Social Golfer Problem we can retrieve a (m*k,k)-solution to the Happy Diner Problem.
• F: There is a perfect (m*k,k)-solution iff G(m,k) = (m*k - 1) / (k - 1) iff T(m*k,k) = (m*k - 1) / (k - 1).
• G: If G(m,k)*(k-1) = m*k - 2 then T(m*k,k) = G(m,k) + 1. This is a lower bound by a and a upper bound using the solution to G(m,k): take the solution to G(m,k) for the first G(m,k) meals. Then everyone has seen all other participants, but 1. For the last meal, have one table for each of the pair of participants which still need to see each other.
• G: If G(m,k)*(k-1) = m*k - 3 (and k ≥ 3) then T(m*k,k) ≤ G(m,k) + 2. After the solution to G(m,k) every participant still needs to meet 2 other participants, which can be easily achieved in two days, by splitting everyone up in group of 2 or 3 people.
• We only use the letters F and G if we could find an explicit, valid solution.
• A trivial upper bound is G(m,k) ≤ (mk-1)/(k-1). We call a solution to the Social Golfer Problem good if it is close to this trivial upper bound.
• See External Links for more sources on the Social Golfer Problem. In particular many solutions of the Social Golfer Problem can be found in this Mathematica Demonstration.
  • The external links contain the following good solutions (only solutions that give new results for the Dagstuhl Happy Dinner Problem are included here). Explicit solutions are given in literature.md.
    • G(5,3) = 7 gives T(15,3) = 7 (MD).
    • G(6,3) = 8 gives T(18,3) = 9 (MD).
    • G(7,3) = 10 gives T(21,3) = 10 (MD).
    • G(11,3) = 16 gives T(33,3) = 16 (Survey).
    • G(7,4) = 9 gives T(28,4) = 9 (MD).
    • G(8,4) = 10 gives T(32,4) = 11 (MD).
    • G(10,4) = 13 gives T(40,4) = 13 (Survey).
    • G(13,4) = 17 gives T(52,4) = 17 (CRCB).
    • G(13,5) = 16 gives T(65,5) = 16 (Survey).
  • Many of these solutions are also found in the literature, see J.

• J: A perfect (n,3)-solution for n ≥ 3 is called a Kirkman Triple System and is possible iff n ≡ 3 mod 6.
  • This is proven in Solution of Kirkman's schoolgirl problem, Ray-Chaudhuri and Wilson (1971).
  • This shows that G(2k+1,3) = 3k+1.
  • Together with lower bound a, this gives that T(6k+1,3) = T(6k+2,3) = T(6k+3,3) = 3k+1.
• J: The optimal (6m,3)-solution for m > 1 has 3m days.
  • This follows from the study of Nearly Kirkman Triple Systems.
  • A Nearly Kirkman Triple System is a (6m,3)-solution in 3m days where on the first 3m-1 days, all tables have 3 participants, and on the last day every table has 2 participants. In such a solution, all participants meet all other participants exactly once.
  • A Nearly Kirkman Triple Systems exists for 6m ≥ 18.
    • ANKS states this and gives references.
  • For 6m = 12 there is a optimal (12,3)-solution in 6 days which is not a Nearly Kirkman Triple System. (see E)
• J: A Kirkman System is an alternative name for an optimal solution.
  • According to On resolvable designs they exist for all (n,4) with n ≡ 4 mod 12.
  • ANKS cites papers that show that for every k there is a Kirkman System for all but finitely many n ≡ k mod k(k-1).
• J: A Nearly Kirkman System is an (n,k)-solution where all participants meet each other exactly once, on all but 1 days all tables contain k participants and on the last day all tables contain k-1 participants.
  • A necessary condition for a Nearly Kirkman System is that n ≡ 0 mod k(k-1).
  • If a Nearly Kirkman System exists for (n,k) then T(n,k) = n / (k-1)
  • ANKS proves that for every k there is a Nearly Kirkman System for all but finitely many n ≡ 0 mod k(k-1).
  • It also states that for k = 4 and n ≡ 0 mod 12 there is a Nearly Kirkman System for all n, except possibly for n in {12, 84, 132, 264, 372, 456, 552, 660, 804, 852}

• The Social Golfer Problem G(n,n) is related to finding mutually orthogonal Latin squares.
  • Let L(n) is the maximal number of mutually orthogonal Latin squares of order n, that is L(n) = A001438(n).
  • The relation is G(n,n) = L(n) + 2.
    • The reason is that the first two days specify a bijection between the participants and the squares in a n × n grid (the cell (i,j) corresponds to the participant p(i,j) that was in group i on day 1 and in group j on day 2.)
    • Every day d ≥ 3 produces a Latin square by putting k in cell (i,j) if participant p(i,j) was in group k.
    • The fact that this is a Latin square follows from the fact that no pair of participants was in the same group on day d, 1 and 2.
    • Days d₁, d₂ ≥ 3 have no pair of participants in the same group iff the corresponding Latin Squares are orthogonal.
  • There is no pair of mutually orthogonal squares of order 6, so L(6) = 1 and G(6,6) = 3 ([OEIS(https://oeis.org/A001438)). In particular there is no perfect (36,6)-solution, so T(36,6) > 7.
  • L(10) is the smallest unknown value. According to this Math Stack Exchange answer L(10) < 9. This implies that there is no perfect (100,10)-solution, so T(100,10) > 11.

• A resolvable 2-(n,k,1) design is an equivalent characterization of a perfect (n,k)-solution. This is also called a (n,k,1)-RBIBD (resolvable balanced incomplete block design).
  • It is a special case of a BIBD (or 2-design) with (v,b,r,k,λ) = (n,b,r,k,1) (where b = n(n-1)/(k(k-1)) and r = (n-1)/(k-1)).
    • This 2-design is equivalently characterized as the Steiner System S(2,k,n).
  • J: In RBIBD5 it is shown that a (n,5,1)-RBIBD exists for all n ≡ 5 mod 20, except possibly for n in {45, 185, 225, 345, 465, 645}.
• A (K,λ)-RGDD (resolvable group divisible design) is a generalization, where the participants are partitioned in groups, and every pair of participants from two different groups meet exactly λ times and every pair of distinct participants from the same group never meet. The table sizes must all be in the set K.
  • Dagstuhl's Happy diner problem is asks to find a ({1,...,k},1)-GDD but where participants can meet each other multiple times.
  • Many solutions to (K,1)-RGDDs will give solutions to Dagstuhl's Happy Diner problem.
    • If all groups have size 1, then the solution is immediate.
    • If all groups are size ≤ k then we get an solution by adding 1 day where all participants meet everyone in their group.

• The solution T(6,3) ≥ 4 is very detailed. Other solutions with the same techniques will have much less explanation. So if you don't understand the reasoning, read T(6,3) ≥ 4 first (See Examples).
• The code using the Mathematica SAT-solver was written by Michael Trott and optimized by Floris van Doorn.
• If the SAT-solver took longer than ~10s, we write the time as an indication for its difficulty.

• Solution found by Mathematica SAT-solver:

159 278 3AC 46B
12C 345 8AB 679
12B 348 79A 56C
168 25A 39B 47C
14A 236 57B 89C
137 249 BC 58 6A

• Solution found by Mathematica SAT-solver:

1234 5678 9ABC DEFG H
1469 28EH 7ACG B 35DF
7 48CD 26BF 1AEG 359H
1BDH 8A 6CF 379E 245G
1 45BE 67GH 89DF 23AC
29 CEH 56AD 38BG 147F
36E 158C 9G 27BD 4AFH

• Solution found by Mathematica SAT-solver:

12345 6789A BC
1279 38B 456AC
128C 4579B 36A
126AB 379C 458

• This solution was found part by hand, part by computer brute-force.
• Suppose there is a valid solution in 4 days.
• (5,5,3) or (5,4,4) has to occur at least once.
• If (5,5,3) never occurs, then from day 2 on at most 18 connections are possible. Contradiction.
• So day 1 is (5,5,3) (23 connections).
• From then on, at most 19 connections are possible, which has to occur at least once, so day 2 is (5,5,3) with 8+8+3 new connections. This can be done in 1 way (up to renaming participants)
• Then there are 8 ways for day 3 to have 18 connections (and more is impossible), possibly counting things twice. We found this number by brute force.
• For none of those 8 ways, there is a valid 4th day.

• Solution found by Mathematica SAT-solver:

123456 789ABC DEFGHI JKLM
458FIM 26ABDK 379GHL 1CEJ
3ABFIJ 45CGHK 18DL 2679EM
45ABEL 3CDM 268GHJ 179FIK
38EK 4579DJ 1ABGHM 26CFIL

• Solution found by Mathematica SAT-solver:

235KLP 78BHJM 16ADEG 49CFINO
25EGIJO 1348BFL 6CMNP 79ADHK
47EFGHP 25689B 3ACDJLN 1IKMO
46FJK 8ABDIOP 1257CHN 39EGLM
367HILO 19JP 245ADFM 8BCEGKN

• Solution found by Mathematica SAT-solver:

12345678 9ABCDEFG HIJKLM
47ACIK 1369BDHM 258EFGJL
258ACHM 136EFGIK 479BDJL
47EFGHM 136ACJL 2589BDIK

• Examples of specific upper and lower bounds.
• These all follow from other values or a general principle.
• These were found before we had these general principles, and we did them individually.
• Examples that do not follow from other principles are listed under Solutions for Individual Cases.

• This is a special case of f.
• Suppose there is a solution in 3 days.
• At least 2 days need configuration (3,3).
  • The reason is that we need to establish 15 connections between participants over 3 days.
  • We can establish at most 6 connections during a single day by configuration (3,3).
  • Configuration (2,2,2) is not dominated, but establishes only 3 connections
  • Any other configuration is dominated by either (3,3) or (2,2,2).
  • If there is at most 1 day with configuration (3,3), then the maximum number of established connections is 6 + 3 + 3 = 12 < 15, which is not enough.
• Without loss of generality we can assume that the first day has configuration (3,3), distributed as 123 456 (i.e. 1, 2 and 3 sit together and 4, 5 and 6 sit together).
• Now on the other days, we can establish at most 4 connections.
  • The reason is that if we use configuration (3,3), then 2 participants on the first table already sat together on table 1, and the same for the second table.
  • Therefore, configuration (3,3) gives at most 4 new connections.
  • We already saw that the only other non-dominated configuration gives at most 3 new connections.
• Therefore, the maximal number of connections we can establish is 6 + 4 + 4 = 14 < 15, which is not enough.
• So there is no valid (6,3)-solution with 3 days.

• This also follows from T(10,4) ≤ T(9,3) = 4. (Relations and either A or H)
• Solution found by hand:

1234 5678 90
1259 3670 48
1280 4679 35
045 1267 389

• This also follows from g.
• Suppose there is a solution in 4 days.
• The only configurations which are not dominated are (4,4,3) and (3,3,3,2). The first adds at most 15 connections, the second at most 10.
• Therefore, on at least 3 days we need a (4,4,3) configuration, WLOG on day 1.
• For the other days any table of size 4 has 1 pair in common with day 1, so adds at most 5 new connections. Therefore, at most 13 new connections can be added during each day.
• This means we cannot get 55 connections, therefore we get a contradiction.

• This is a special case of f.
• Suppose there is a valid solution in 3 days.
• The only configurations which are not dominated are (5,5) (<= 20 conns), (4,4,2) (<= 13 conns) and (4,3,3) (<= 12 conns).
• Therefore, we need (5,5) at least once. WLOG day 1 is distributed 01234 56789.
• From now on (5,5) has at most 12 new conns, (4,4,2) has at most 9 new conns and (4,3,3) has at most 8 new conns.
• This means we cannot get 45 connections, therefore we have no valid solution in 3 days.

• This is a special case of f.
• Suppose there is a valid solution in 3 days.
• The configurations with at least 26 connections which are not dominated are (6,6,1) and (6,5,2), one of which has to occur at least once.
  • Suppose day 1 is (6,6,1). Then no other day can have more than 20 connections. Day 2 has
    • (6,6,1) at most 11+9 = 20 connections
    • (6,5,2) at most 11+8+1 = 20 connections (actually, less)
    • (6,4,3) and (5,5,3) and (5,4,4) also have less than 20 connections, all other configurations are dominated.
  • Suppose no day is (6,6,1). Then every day needs 26 connections exactly, which is impossible.
• Alternatively, this can be derived from T(13,6) ≥ T(14,7) ≥ 4

• This also follows from g.
• Suppose there is a valid solution in 4 days.
• 181 connections have to be made, and at most 45 connections can be made per day, with configuration (6,6,6,1). Every other configuration has at most 41 connections.
• This means that (6,6,6,1) has to appear, WLOG on day 1. Now on every other day, the configuration (6,6,6,1) can give at most 13+12+12=37 connections, which means that there is no way to get 181 connections in 4 days.

• This was found by manually modifying T(16,4) = 5, using the same method as K.
• K only shows that T(20,6) ≤ 5.
• If you replace 1H, 2I, 5J, 6K and 9L by single participants, you get a perfect (16,4)-solution

1234HI 5678JK 9ABCL DEFG
179DHL 26AFIK 38CE 45BGJ
18BFH 25CDIJ 37AG 469EKL
15AEHJ 289GIL 36BDK 47CF
16CGHK 27BEI 359FJL 48AD

• This is a special case of f.
• Suppose there is a valid solution in 3 days.
• The configuration (7,7) has to occur, since there is no way to make at least 61 connections in 2 days otherwise.
• After (7,7) at most 24 connections can be made per day. So there are at most 42 + 24 + 24 = 90 < 91 connections, which is not enough.

• This also follows from T(21,7) ≥ T(20,7) ≥ 5 where the second inequality follows from g.
• Suppose there is a valid solution in 4 days.
• 210 connections have to be made, and at most 63 connections can be made per day, with configuration (7,7,7).
• It is impossible to have a non-dominated solution where 5 tables are used every day.
• If (7,7,7) appears, WLOG on day 1, then at most 48 connections can be made every other day, but 63+48+48+48=207<210 is not enough.
• If (7,7,7) doesn't appear, then every day has 4 tables. Then at most 57 connections can be made on day 1, and at most 49 connections on future days (since all 7s lose at least 3 and all 6s lose at least 2 connections). This is also not enough, since 57+49+49+49=204<210.

• The condition n ≡ k mod k(k-1) is necessary for a perfect (n,k)-solution to exist. To what extend is it sufficient?
  • It is true when k is a prime power and n is a power of k, see H.
  • In the smallest case where k is not a prime power, the first non-trivial example is immediately a counterexample. There is no perfect (36,6)-solution (see Latin Squares).
  • It is true for k = 2 and k = 3.
  • For k = 4 it's true according to On resolvable designs.
  • According to ANKS for every k this is true for all but finitely many n (Theorem 1, citing The existence of resolvable block designs. Survey of combinatorial theory, D Ray-Chaudhuri, R Wilson - 1973).
    • This shows that for a fixed k the asymptotic behavior of T(n,k) is T(n,k) ≤ (n-1)/(k-1) + O(1), i.e. T(n,k) - (n-1)/(k-1) is bounded by a constant (possibly depending on k).
• For every n and k is there an optimal (n,k)-solution in which, during every meal, at most one table is not completely occupied?
  • This is false. All optimal (8,5)-solutions have at least one day with two tables of four participants. This was found by brute force, but is quite easy to see by hand (to do).
  • It is probably even false that there always is an optimal (n,k)-solution where there are ⌈ n/k ⌉ tables each day (where ⌈ x ⌉ is the smallest integer which is at least x). The Mathematica SAT-solver easily found a solution that T(12,3) ≤ 6, but didn't terminate within reasonable time when the additional condition was imposed that only 4 tables could be used per day.
• In all cases we know the following holds: if there is a perfect (n,k) solution, then T(n+1,k) = T(n,k) + 2.
  • Does this always hold? Or maybe T(n+1,k) ≥ T(n,k) + 2?

• Dagstuhl's Happy Diner Problem:
  • We submitted two sequences to the OEIS: A318240 and A318241.
  • The problem is stated on Sarah's Oberwolfach Problem Page. Finding the perfect (n,3)-solutions is a special case of the Oberwolfach Problem.
  • Someone asked the value of T(18,4) - 1 on Math Stack Exchange
• Social Golfer Problem:
  • Wolfram Mathworld
  • Warwick's result page (2002)
  • Markus Triska's master thesis (2008)
  • Edd Pegg Jr.'s Math Game page (2007)
  • A107431.
  • Mathematica Demonstration
  • Math Stack Exchange
  • This page contains a solution that G(8,5) ≥ 8.
• Kirkman System:
  • Wolfram Mathworld,
  • Dutch dissertation by Pieter Mulder (1917).
  • Solution of Kirkman's schoolgirl problem, Ray-Chaudhuri and Wilson, 1971. In Proc. of Symp. in Pure Math, Vol 19.
  • Kirkman triple systems and their generalizations: A survey, Rees and Wallis, 2002. Springer
  • Asymptotic Existence of Nearly Kirkman Systems, Hao Chen, Wen-Song Chu
• Block Designs:
  • A Survey of Resolvable Solutions of Balanced Incomplete Block Designs, Sanpei Kageyama, Rev. Inst. Internat. Statist., 40, 269–273. JSTOR
  • On Cyclically Resolvable Cyclic Steiner 2-Designs, Clement Lam and Ying Miao, Journal of Combinatorial Theory, Series A, Volume 85, Issue 2, February 1999, Pages 194-207. ScienceDirect
  • On resolvable designs, Haim Hanani, D.K. Ray-Chaudhuri, Richard M. Wilson Discrete Mathematics, 1972, 3:343-357.
• Oberwolfach Problem: Sarah's Oberwolfach Problem Page.

• Contributions are welcome! Feel free to add any information. Please provide links or justifications of claims you make.