Title: The polynomial method in combinaotrics (I) Let q be a prime and n an integer. How small can a subset of the vector space (F_q)^n be if it contains a line in every direction? (II) Let n be a large integer. How large can a subset of (F_3)^n be if it contains no solution to the equation x+y+z=0? Several important problems in extermal combinaotrics were solved in recent years by introducing polynomials into the problem in a clever way. In many cases, this approach produces incredibly simple and elegant proofs that rely on no more than standard linear algebra. We will talk about the two famous examples above: (I) Dvir's proof of the finite field Kakeya conjecture, and (II) the recent solution of the cap-set problem by Eilenberg and Gijswijt that is based on a breakthrough of Croot-Lev-Pach.
Thu, 24/05/2018 - 12:45 to 14:00