Erdos conjectured that N points in the plane determine at least c N (log N)^{-1/2} different distances. Recently Nets Katz and I came close to proving the conjecture, showing that the number of distinct distances is at least c N (log N)^{-1}.

Elekes and Sharir made a connection between the distinct distance problem and incidence geometry - the study of intersection patterns of points and lines. There has been a lot of progress in this area over the last few years starting with Dvir's solution of the Kakeya problem in finite fields using the polynomial method. The new wrinkle in our proof is a way to mix polynomial methods with topological methods.

The \emph{choice number} or \emph{list-chromatic number} $\chi_\ell(G)$ of a graph $G=(V,E)$ is the minimum $k$ such that for every assignment of a list $s(v)$ of $k$ colors to each $v\in V$ there exists a proper coloring $c$ of $V$ that colors each $v$ by a color from $s(v)$. The \emph{coloring number} $\col(G)$ of $G$ is the minimum $k$ such that there is an enumeration $V=\{v_0,v_1,\dots,v_{n-1}\}$ satisfying that for each $i<n$ the vertex $v_i$ has fewer than $k$ neighbors among $\{v_j:j<i\}$. For every $G$ it holds that $\chi(G)\le\chi_\ell(G)\le \col(G)$ (where $\chi(G)$ is the usual \emph{chromatic number} of $G$.)

N. Alon proved that $\col(G) \le c2^{\chi_\ell(G)}$ for some constant $c$ for every finite graph $G$ and asked if some analogous bound holds in the infinite case. Using S. Shelah's \emph{revised GCH Theorem} in cardinal arithmetic we shall prove that for every graph $G$ with infinite $\chi_\ell(G)$ it holds that \[\col(G) \le \beth_\om(\chi_\ell(G)),\] where $\beth_\om(\kappa)$ of a cardinal $\kappa$ is the limit of $\kappa_n$ where $\kappa_0=k$ and $\k_{n+1}=2^{\kappa_n}$.