Skip to Main content Skip to Navigation
Conference papers

Colouring random geometric graphs

Abstract : A random geometric graph $G_n$ is obtained as follows. We take $X_1, X_2, \ldots, X_n ∈\mathbb{R}^d$ at random (i.i.d. according to some probability distribution ν on $\mathbb{R}^d$). For $i ≠j$ we join $X_i$ and $X_j$ by an edge if $║X_i - X_j ║< r(n)$. We study the properties of the chromatic number $χ _n$ and clique number $ω _n$ of this graph as n becomes large, where we assume that $r(n) →0$. We allow any choice $ν$ that has a bounded density function and $║. ║$ may be any norm on $ℝ^d$. Depending on the choice of $r(n)$, qualitatively different types of behaviour can be observed. We distinguish three main cases, in terms of the key quantity $n r^d$ (which is a measure of the average degree). If $r(n)$ is such that $\frac{nr^d}{ln n} →0$ as $n →∞$ then $\frac{χ _n}{ ω _n} →1$ almost surely. If n $\frac{r^d }{\ln n} →∞$ then $\frac{χ _n }{ ω _n} →1 / δ$ almost surely, where $δ$ is the (translational) packing density of the unit ball $B := \{ x ∈ℝ^d: ║x║< 1 \}$ (i.e. $δ$ is the proportion of $d$-space that can be filled with disjoint translates of $B$). If $\frac{n r^d }{\ln n} →t ∈(0,∞)$ then $\frac{χ _n }{ ω _n}$ tends almost surely to a constant that can be bounded in terms of $δ$ and $t$. These results extend earlier work of McDiarmid and Penrose. The proofs in fact yield separate expressions for $χ _n$ and $ω _n$. We are also able to prove a conjecture by Penrose. This states that when $\frac{n r^d }{ln n} →0$ then the clique number becomes focussed on two adjacent integers, meaning that there exists a sequence $k(n)$ such that $\mathbb{P}( ω _n ∈\{k(n), k(n)+1\}) →1$ as $n →∞$. The analogous result holds for the chromatic number (and for the maximum degree, as was already shown by Penrose in the uniform case).
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184397
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:39:40 AM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:07:11 AM

File

dmAE0101.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184397, version 1

Collections

Citation

Colin J. H. Mcdiarmid, Tobias Müller. Colouring random geometric graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.1-4. ⟨hal-01184397⟩

Share

Metrics

Record views

70

Files downloads

732