Computer Science/Discrete Mathematics Seminar II

Erdos conjectured that N points in the plane determine at least c N (log N)^{-1/2} different distances. Building on work of Elekes-Sharir, Nets Katz and I showed that the number of distances is at least c N (log N)^{-1} . (Previous estimates had lower bounds like N^{.86}.) Elekes and Sharir made a connection between the distinct distance problem and 3-dimensional incidence geometry. Recently there has been progress in 3-dimensional incidence geometry using the polynomial method. In 2007, Dvir used the polynomial method to prove the Kakeya conjecture over finite fields. This can be considered a problem of incidence geometry. Nets Katz and I adapted this method to incidence geometry in Euclidean space in a 2008 paper where we proved the joints conjecture. Elekes and Sharir conjectured that if we have L lines in Euclidean space and at most L^{1/2} of them lie in any plane or any regulus, then the number of points where at least k lines intersect is at most C L^{3/2} k^{-2} . They proved this conjecture when k=3 , using the polynomial method. Nets and I proved this conjecture for other values of k . The most interesting wrinkle is that the proof uses a little bit of topology -- a version of the ham sandwich theorem.