On the chromatic number of random geometric graphs

Given independent random points $X_1,\mathrm{.}\mathrm{.}\mathrm{.},X_n\in {\text{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,\mathrm{.}\mathrm{.}\mathrm{.},n\}$ where distinct $i$ and $j$ are adjacent when $\text{norm}{X}_i-X_j\le r$. Here $\text{norm}\mathrm{.}$ may be any norm on ${\text{eR}}^d$, and $\nu$ may be any probability distribution on ${\text{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 \mathrm{\infty }$. Both McDiarmid and Penrose considered the range of $r$ when $r \ll (\frac{\ln n}{n})^{1/d}$andtherangewhen$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\mathrm{/}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)}{n{r}^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\le 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.