On the chromatic number of random geometric graphs

Abstract

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)}{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.

56 pages, to appear in Combinatorica. Some typos corrected

Cited by in corpus (2)

• A geometric Achlioptas process
• Scaling Laws for Maximum Coloring of Random Geometric Graphs