On the chromatic number of random geometric graphs

Given independent random points $X_1,...,X_n\in\eR^d$ with common probability
distribution $\nu$, and a positive distance $r=r(n)>0$, we construct a random
geometric graph $G_n$ with vertex set $\{1,...,n\}$ where distinct $i$ and $j$
are adjacent when $\norm{X_i-X_j}\leq r$. Here $\norm{.}$ may be any norm on
$\eR^d$, and $\nu$ may be any probability distribution on $\eR^d$ with a
bounded density function. We consider the chromatic number $\chi(G_n)$ of $G_n$
and its relation to the clique number $\omega(G_n)$ as $n \to \infty$. Both
McDiarmid and Penrose considered the range of $r$ when $r \ll (\frac{\ln
n}{n})^{1/d}$ and the range when $r \gg (\frac{\ln n}{n})^{1/d}$, and their
results showed a dramatic difference between these two cases. Here we sharpen
and extend the earlier results, and in particular we consider the `phase
change' range when $r \sim (\frac{t\ln n}{n})^{1/d}$ with $t>0$ a fixed
constant. Both McDiarmid and Penrose asked for the behaviour of the chromatic
number in this range. We determine constants $c(t)$ such that
$\frac{\chi(G_n)}{nr^d}\to c(t)$ almost surely. Further, we find a "sharp
threshold" (except for less interesting choices of the norm when the unit ball
tiles $d$-space): there is a constant $t_0>0$ such that if $t \leq t_0$ then
$\frac{\chi(G_n)}{\omega(G_n)}$ tends to 1 almost surely, but if $t > t_0$ then
$\frac{\chi(G_n)}{\omega(G_n)}$ tends to a limit $>1$ almost surely.