Sum-product estimates via combinatorial geometry
Sum-product estimates via combinatorial geometry
-
Po-Shen Loh, Princeton University and UCLA
Fine Hall 314
Every two-dimensional 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 $|A|5/4$. What could these two theorems possibly have in common, besides the fact that Endre Szemerédi co-authored 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.