Sites Inria

Version française

Séminaire des équipes de recherche

Maximum Coloring of Random Geometric Graphs

© INRIA Sophie Auvin - R comme Robot

Milan Bradonjic from Bell Labs Nokia US will be speaking about "Maximum Coloring of Random Geometric Graphs".

  • Date : 18/01/2017
  • Place : Inria de Paris, Building C, Room C334 - 14h00
  • Guest(s) : Milan Bradonjic (Bell Labs Nokia US)

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. B{\l}aszczyszyn, we study the distributional properties of maximum vertex colorings of random geometric graphs. Moreover, we intend to generalize the study over weakly-$\mu$-sub-Poisson processes.

Keywords: Maximum coloring of random Geometric Graphs Dyogene Rap Seminar