## Publication Date:

November 2011

## Journal:

Combinatorica, Volume 31 (2011), Number 4, Pages 423-488

## Last Updated:

2020-05-14T15:13:26.7+01:00

## Issue:

4

## Volume:

31

## DOI:

10.1007/s00493-011-2403-3

## page:

423-488

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

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.

## Symplectic id:

115860

## Download URL:

## Submitted to ORA:

Submitted

## Publication Type:

Journal Article