The Banquet Seating Problem
MSRI-UP 2015: Geometric Combinatorics Motivated by the Social Sciences June 13, 2015 - July 26, 2015
Location: MSRI: Baker Board Room
Suppose you want to seat n = mk people around k tables with m people at each table. Each person gives you a list of j people next to whom they would enjoy sitting. What is the smallest j for which you can always make a seating arrangement that would seat each person next to one of the people on their list? In this paper we show that j must be strictly more than half of n, the total number of people. Our key tool is a particular ‘blue-green-red’ lemma that helps us construct ‘worst-case scenario’ seating arrangements. We consider cases with two tables and more than two tables and explore seating arrangements with particular kinds of preferences.
Perez, Scruse, Torre
If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.
See more of our Streaming videos on our main VMath - Streaming Video page.