Monday, October 29th, 2012 | 4:00pm-5:00pm | Burnside 1205 |

School of Mathematics and Statistics, Carleton University

Optimizing an imperfect tournament

A computer science department holds an annual video game olympics with 64 participants playing 8 games. There are 8 rooms each with a fixed video game and there are 8 rounds. In each round 8 people will be in each room. Every person will play each game exactly once. We would like to find a schedule for all the players, rooms and rounds that is as balanced as possible, i.e. no pair of players plays together in the same room too frequently and as few pairs of people playing together are missed. It can be shown that some pairs must be missed and some pairs must repeat. We set up a combinatorial framework to quantify the repetition and missing pairs and try several different approaches to optimise the tournament. For various criteria we will find solutions constructed from lines in finite planes, ovals in finite geometries and finally a set of solutions that are related to Costas sonar and radar sequences.