Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
table_seating [2021-12-08 08:44] – timbotable_seating [2026-07-11 11:04] (current) – [Upper Version] 88.207.115.163
Line 1: Line 1:
 ==== 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. 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 **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 **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+  * 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. Some general thoughts. Each sitting defines a partition of the set of people, each part is one table.
  
-===Strict=== +====Strict==== 
-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). +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)$. 
  
-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.+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.
  
  
-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.+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\text{–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.+For pairs, resolvable $(v,2,1) 2\text{–designs}$ exist only for $even v, v >= 4$.
  
-Table size 4: Resolvable (v,k,1)- 2-designs.  +Table size 4: Resolvable $(v,k,1) 2\text{–designs}$.  
-[[https://www.semanticscholar.org/paper/The-spectrum-of-resolvable-designs-with-block-size-Vasiga-Furino/364fb4a75a38493ed2c86fa3589adfee6d2714f5|This paper]] says that nessesary numerical conditions are sufficient except for a case that need not concern us.+[[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====
- +
- +
-=== 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. 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 ===+==== 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]]} 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]]}
Line 37: Line 33:
  
 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]]
 +
 +==== Discussion ====
 +
 +A summary of the problem and motivations, [[https://loosediary.wordpress.com/2021/12/20/may-i-sit-here/|May I sit here?]] by Tim Boykett
  
 ---- ----

User Tools

Page Tools

Site Tools