Two-point concentration in random geometric graphs |
| |
Authors: | Tobias Müller |
| |
Affiliation: | (1) Department of Statistics, University of Oxford, 1 South Parks Road, Oxford, OX1 3TG, UK |
| |
Abstract: | A random geometric graph G n is constructed by taking vertices X 1,…,X n ∈ℝ d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X i and X j if ‖X i -X j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr d = o(lnn) then the probability distribution of the clique number ω(G n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds. |
| |
Keywords: | KeywordHeading" >Mathematics Subject Classification (2000) 05C80 05C15 05C69 60D05 |
本文献已被 SpringerLink 等数据库收录! |
|