Maximum Coloring of Random Geometric Graphs

Speaker : Milan Bradonjic
Nokia Bell Labs, US
Date: 26/10/2016
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


We have examined maximum vertex coloring of random geometric graphs, in an arbitrary but fixed dimension, with a constant number of colors, in a recent work with S.~Borst. Since this problem is neither scale-invariant nor smooth, the usual methodology to obtain limit laws cannot be applied. We therefore leverage different concepts based on subadditivity to establish convergence laws for the maximum number of vertices that can be colored. For the constants that appear in these results, we have provided the exact value in dimension one, and upper and lower bounds in higher dimensions.In an ongoing work with B. Blaszczyszy, we study the distributional properties of maximum vertex coloring of random geometric graphs. Moreover, we intend to generalize the study over weakly-$mu$-sub-Poisson processes.