Sumproduct estimates via combinatorial geometry
Sumproduct estimates via combinatorial geometry

PoShen Loh, Princeton University and UCLA
Fine Hall 314
Every twodimensional drawing of any graph with $V$ vertices and $E\ge 4V$ edges necessarily has at least $E3/V2$ pairs of crossing edges. Also, for every set $A$ of real numbers, one of $A+A$ (the set of all pairwise sums of elements of $A$) or $A\cdot A$ (the set of all pairwise products) has size at least $A5/4$. What could these two theorems possibly have in common, besides the fact that Endre Szemerédi coauthored both? Surprisingly, quite a lot. We will see the proof of the first result, followed by a series of fascinating consequences which culminate in the second result. Of course, the Probablistic Method will make a crucial appearance.