Next revision | Previous revision Next revisionBoth sides next revision |
table_seating [2021-06-12 11:59] – created nik | table_seating [2024-04-11 10:13] – [Strict] nik |
---|
==== Table Seatings ==== | ==== Table Seatings ==== |
| |
| 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. |
| |
arranging a group of people into a number of tables so that everyone sits with everyone else. | * 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 |
| |
A strict version is an affine plane. More generally we want a [[https://en.wikipedia.org/wiki/Block_design#Resolvable_2-designs|resolvable 2-design]]. 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. | Some general thoughts. Each sitting defines a partition of the set of people, each part is one table. |
| |
| ====Strict==== |
| A strict version is an affine plane. Example 25 people in 5 tables of 5, Point set is $Z_5 \times 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). |
| |
Strict 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) | More generally we want a [[https://en.wikipedia.org/wiki/Block_design#Resolvable_2-designs|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. |
- https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem | |
- https://oeis.org/search?q=schoolgirl&sort=&language=german&go=Suche | |
| |
In less strict cases we allow people to meet more often, or not to meet. | |
| |
The "Dagstuhl Happy Diner problem" is the version where everyone meets at least once. | Versions include [[https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem|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) {[[https://oeis.org/search?q=schoolgirl&sort=&language=german&go=Suche|oeis]]}. This is the question as to resolvable $(v,3,1) 2-designs$, which if I understand it, exist $iff v = 3 mod 6$. |
- https://github.com/fpvandoorn/Dagstuhl-tables | |
- https://oeis.org/A318240 | |
| |
Equitable Resolvable coverings also seem to be a more strict form, where we can allow people to meet at most twice. | For pairs, resolvable (v,2,1) 2-designs exist only for even v, v >= 4. |
- https://www.researchgate.net/publication/227715273_Equitable_resolvable_coverings | |
- https://onlinelibrary.wiley.com/doi/epdf/10.1002/jcd.10024?saml_referrer | Table size 4: Resolvable (v,k,1)- 2-designs. |
| [[https://www.semanticscholar.org/paper/The-spectrum-of-resolvable-designs-with-block-size-Vasiga-Furino/364fb4a75a38493ed2c86fa3589adfee6d2714f5|This paper]] says that necessary numerical conditions are sufficient except for a case that need not concern us. |
| |
| ==== Lower Version==== |
| |
| 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. |
| |
| ==== Upper Version ==== |
| |
| The "[[https://github.com/fpvandoorn/Dagstuhl-tables|Dagstuhl Happy Diner problem]]" is the version where everyone meets at least once. {[[https://oeis.org/A318240|oeis]]} |
| |
| [[https://www.researchgate.net/publication/227715273_Equitable_resolvable_coverings|Equitable Resolvable coverings]] also seem to be a more strict form, where we can allow people to meet at most twice. {[[https://onlinelibrary.wiley.com/doi/epdf/10.1002/jcd.10024|ref]]} |
| |
If we have people sitting at round tables and only interacting with their neighbours, then we have the more difficult [[https://en.wikipedia.org/wiki/Oberwolfach_problem|Oberwolfach Problem]] | If we have people sitting at round tables and only interacting with their neighbours, then we have the more difficult [[https://en.wikipedia.org/wiki/Oberwolfach_problem|Oberwolfach Problem]] |