Colloquium Mathematics, Dr. Milan Bradonjic (Rutgers University)

Title:

Maximum Coloring of Random Geometric Graphs.

Abstract:

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.
Blaszczyszyn, 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.