Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Van Vu

UCSD

New bound on Erdos distinct distances problem

Abstract:

One of the most well known questions of Erdos in discrete geometry is the following: Given n points in $R^d$, what is the smallest number of distinct distances among them ? Here d is fixed and n tends to inifnity. We denote by $f_d(n)$ is smallest number of distince distances. The problem of determining $f_d(n)$ has been attacked by many researchers (including Erdos, Beck, Chung, Trotter, Szemeredi, Beck, Ssekely, Solymosi-Toth, Sharir, etc) for decades. In this talk, I will give a brief overview and also present a new result (joint with Solymosi). This result gives an almost sharp estimate for $f_d(n)$ for relatively large dimension $d$. The main tool is what we call "decomposition technique", which appears to be useful in other problems as well.

Host:

February 24, 2004

3:00 PM

AP&M 7321

****************************