caa a22 4500 445358637 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00493-011-2403-3 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2403-3 On the chromatic number of random geometric graphs [Elektronische Daten] [Colin Mcdiarmid, Tobias Müller] Given independent random points X 1,...,X n ∈ℝ d with common probability distribution ν, 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 ‖X i −X j ‖≤r. Here ‖·‖ may be any norm on ℝ d , and ν may be any probability distribution on ℝ d with a bounded density function. We consider the chromatic number χ(G n ) of G n and its relation to the clique number ω(G n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$$ and the range when $$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{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 \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$$ with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $$\tfrac{{\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≤t 0 then $$\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$$ tends to 1 almost surely, but if t>t 0 then $$\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$$ tends to a limit >1 almost surely. János Bolyai Mathematical Society and Springer Verlag, 2011 Mcdiarmid Colin Department of Statistics, 1 South Parks Road, OX1 3TG, Oxford, UK aut Müller Tobias Centrum Wiskunde & Informatica, P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands aut Combinatorica Springer-Verlag 31/4(2011-11-01), 423-488 0209-9683 31:4<423 2011 31 493 https://doi.org/10.1007/s00493-011-2403-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2403-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mcdiarmid Colin Department of Statistics, 1 South Parks Road, OX1 3TG, Oxford, UK aut NATIONALLICENCE 700 1- Müller Tobias Centrum Wiskunde & Informatica, P.O. Box 94079, 1090 GB, Amsterdam, The Netherlands aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/4(2011-11-01), 423-488 0209-9683 31:4<423 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer