Processing math: 19%

Colin J. H. Mcdiarmid ; Tobias Müller - Colouring random geometric graphs

dmtcs:3440 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3440
Colouring random geometric graphsConference paper

Authors: Colin J. H. McDiarmid ; Tobias Müller 1

  • 1 Department of Statistics [Oxford]

A random geometric graph Gn is obtained as follows. We take X1,X2,,XnRd at random (i.i.d. according to some probability distribution ν on Rd). For ij we join Xi and Xj by an edge if XiXj<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).


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: random geometric graphs,graph colouring,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 230 times.
This article's PDF has been downloaded 407 times.