We study coloring of sparse random geometric graphs, in an arbitrary but constant dimension, with a constant number of colors. We show the weak and strong law of large numbers, as well as the central limit theorem type results for the maximum number of nodes that can be properly colored. This object is neither scale-invariant nor smooth. Hence we design the tools that with the main method of subadditivity allow us to show the weak and strong laws. Additionally, by proving the Lindeberg conditions, we show the normal limiting distribution. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions. This work is motived by wireless networks, and the results show that by excluding an arbitrarily small fraction of users from service, the max-min throughput capacity of a large wireless network can be improved by orders of magnitude.
Joint work with Sem Borst.
The ACO Seminar (2014–2015)