Game, Set and Bound!

11 October 2017
11:00
to
12:30
Adam Keilthy
Abstract


In the game 'Set', players compete to pick out groups of three cards sharing common attributes. But how many cards must be dealt before such a group must appear? 
This is an example of a "cap set problem", a problem in Ramsey theory: how big can a set of objects get before some form of order appears? We will translate the cap set problem into a problem of geometry over finite fields, discussing the current best upper bounds and running through an elementary proof. We will also (very) briefly discuss one or two implications of the cap set problem over F_3 to other questions in Ramsey theory and computational complexity