General Mathematics Colloquium
Speaker: Dion Gijswijt (TU Delft)
Title: A solution to the cap set problem
A subset of GF(3)^n, the n-dimensional vector space over the field of 3 elements, is called a cap set if it does not contain an affine line. In dimension 4, this relates to the famous card game SET. There, a cap set corresponds to a collection of cards without a SET. The cap set problem is concerned with upper bounds on the size of cap sets.
A question raised by Frankl, Graham and Rödl is: do cap sets have exponentially small density? A positive answer implies the Erdös-Szemerédi sunflower conjecture. On the other hand, several approaches for fast matrix multiplication rely on a negative answer. In this talk we give a positive answer by showing that the maximum size of a cap set is O(c^n), where c=2.756. The proof is surprisingly simple and uses the polynomial method, building upon work of Croot, Lev and Pach.
This is joint work with Jordan Ellenberg.
Location: KdVI meeting room, Science Park 107, room F3.20
Science Park 107
Science Park 107 | 1098 XG AmsterdamGo to detailpage