On the chromatic number of random geometric graphs (Q663092)

This paper studies the chromatic number \(\chi(G)\) and clique numbers \(\omega(G)\) of random geometric graphs, especially in a `threshold' case where earlier results had not given insight. In detail, let \(\|.\|\) be a norm on \({\mathbb{R}}^{d}\), with packing density \(\delta \in (0,1]\). (The packing density is, informally, the greatest proportion of \({\mathbb{R}}^{d}\) which can be filled with disjoint translates of the unit open ball \(B\).) Let \(\nu\) be a probability distribution on \({\mathbb{R}}^{d}\) with probability density function \(f\). Given a sequence \(X_{1},X_{2},\dots\) of independent random variables distributed as \(\nu\), we say that the random geometric graph \(G_{n}\) has vertices \(X_{1},\dots, X_{n}\) with two vertices \(X_{i}, X_{j}\) being adjacent if and only if \(\| X_{i}-X_{j}\| \leq r=r(n)\) for some function \(r(n)\), with \(\lim_{n\rightarrow \infty} r(n)=0\). The main result has four parts, depending on the value of \(nr^{d}\). Firstly, if \(nr^{d} \ll n^{-\alpha}\) for some fixed \(\alpha>0\), then with probability 1, for all but finitely many \(n\) \[ \chi(G_{n}) = \omega(G_{n}) \in \left\{\left\lfloor \frac{\ln(n)}{\ln(nr^{d})} + \frac{1}{2}\right\rfloor, \left\lfloor \frac{\ln(n)}{\ln(nr^{d})} + \frac{1}{2} \right\rfloor+1\right\}. \] Secondly, if \(n^{-\varepsilon} \ll nr^{d} \ll \ln(n)\) for all \(\varepsilon>0\), then \(\chi(G_{n})\) and \(\omega(G_{n})\) are both almost surely \(\sim \ln(n)/\ln (\ln(n)/(nr^{d}))\). This is a technical improvement of an earlier result in [\textit{M.~D.~Penrose}, Random Geometric Graphs, Oxford University Press (2003; Zbl 1029.60007)]. Thirdly (this `threshold' case is the main novelty) is the case where \(nr^{d}\) is roughly a constant times \(\ln(n)\). In detail, let \(\sigma = \sup\{t : \operatorname{vol}(\{x: f(x)>t\}) >0\}\) be the essential supremum of \(f\) (\(\operatorname{vol}\) denotes Lebesgue measure). The result is then that, if \(\sigma nr^{d}/\ln(n) \rightarrow t\) as \(n \rightarrow \infty\), then \(\chi(G_{n}) \sim f_{\chi}(t)\sigma nr^{d}\) almost surely, for a (complicated!) continuous non-increasing function \(f_{\chi}\), which depends on \(d\) and \(\|.\|\) only. Further \(\lim_{t\rightarrow \infty} f_{\chi}(t) = \operatorname{vol} (B)/(2^{d}\delta)\) and \(\lim_{t\rightarrow 0} f_{\chi}(t) = \infty\). Here the clique number behaves differently from chromatic number: again assuming \(\sigma nr^{d}/\ln(n)\rightarrow t\), we have \(\omega(G_{n}) \sim f_{\omega}(t)\sigma nr^{d}\) almost surely, where \(f_{\omega}\) is a (complicated!) continuous, strictly decreasing function with \(\lim_{t\rightarrow\infty} f_{\omega} (t) = \operatorname{vol}(B)/2^{d}\): in particular, it is a factor (about) \(1/\delta\) away from \(f_{\chi}\) for large \(t\) (provided \(\delta<1\)). Finally, for \(nr^{d} \gg \ln(n)\) (but \(r(n)\rightarrow 0\) still) we have (again sharpening a result of Penrose) that, almost surely, \[ \chi(G_{n}) \sim \frac{\operatorname{vol}(B)\sigma nr^{d}}{2^{d}\delta}, \quad \omega(G_{n}) \sim \frac{\operatorname{vol}(B)\sigma nr^{d}}{2^{d}} \] so again \(\chi\) and \(\omega\) differ provided \(\delta<1\). Proof techniques include showing that the chromatic number of the random geometric graph is approximated by the fractional chromatic number, and a large amount of detailed analysis of so-called generalised scan statistics.