Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, April 14, 2015 - 2:30pm

Milan Bradonjic

Bell Labs

Location

University of Pennsylvania

DRL 4E9

We study coloring of sparse random geometric graphs, in an arbitrary but constant dimension, with a constant number of colors. We show the 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, so we design the tools that with the main method of subadditivity allow us to show the law of large numbers. Additionally, by proving the Lindeberg conditions, we show that the limiting distribution is Gaussian. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions. Joint work with Sem Borst.