Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revisionBoth sides next revision
table_seating [2021-06-12 12:02] niktable_seating [2021-12-08 08:44] timbo
Line 2: Line 2:
  
  
-arranging a group of people into a number of tables so that everyone sits with everyone else.+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.
  
-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 thisbut we seem to have better combinatorial ideas below.+  * The strict version is that all tables are the same size and that after the required number of roundseveryone 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.
  
-Strict versions include [[https://en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem|Kirkman's Schoolgirl Problem]] (15 children walk in groups of 3can they do this so that all pairs of girls walk together exactly once over whole week) {[[https://oeis.org/search?q=schoolgirl&sort=&language=german&go=Suche|oeis]]}+===Strict=== 
 +A strict version is an affine planeExample 25 people in 5 tables of 5Point 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). 
  
-In less strict cases we allow people to meet more oftenor not to meet.+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 thisbut 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. 
 + 
 +For pairs, resolvable (v,2,1) 2-designs exist only for even v, v >= 4. 
 + 
 +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 nessesary 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]]} 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]]} [[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]]
  
  • table_seating.txt
  • Last modified: 2022-04-04 03:32
  • by nik