The Banquet Seating Problem

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.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.