Description
CACAAG seminar II.
Speaker: Mrinal Kumar.
Affiliation: Computer Science Department, IIT Bombay.
Date and Time: Friday 11 October, 4:30 pm - 5:30 pm.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Some applications of the Polynomial Method in Combinatorics.
Abstract: In the next couple of lectures, we will see some applications of
the so called Polynomial Method to problems in Combinatorics. We will
focus on the following three applications:
1. Joints Problem: For a set L of lines in R^3, a point p in R^3 is said
to be a joint in L if there are at least three non-coplanar lines in L
which pass through p. We will discuss a result of Guth and Katz who showed
an upper bound on the maximal number of joints in an arrangement of N
lines.
2. Lower bounds on the size of Kakeya sets over finite fields: For a
finite field F, a Kakeya set is a subset of F^n that contains a line in
every direction. We will discuss a result of Dvir showing a lower bound
of C_n*q^n on the size of any Kakeya set over F^n, where C_n only depends
on n and F is a finite field of size q.
3. Upper bounds on the size of 3-AP free sets over finite fields: We will
then move on to discuss a recent result of Ellenberg and Gijswijt who
showed that if F is a finite field with three elements, and S is a subset
of of F^n such that S does not that does not contain three elements in an
arithmetic progression, then |S| is upper bounded by c^n for a constant c
< 3.