|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Bell Labs, Alcatel-Lucent Title: Asymptotic laws for coloring sparse random geometric graphs with constant number of colors Abstract: We study coloring random geometric graphs (RGGs), in an arbitrary but constant dimension, with constant number of colors. We ask what is the maximal number of nodes in a sparse RGG that can be properly colored with a given constant number of colors? We show the weak and strong law of large numbers as well as the central limit theorem type results for this value. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions. From a practical perspective, this work shows that by reducing the number of communication channels in a wireless network to a constant, while leaving an arbitrarily small fraction of users unassigned to communication channels, one can improve in the orders of magnitude the max-min throughput capacity for any constant communication rate, which otherwise tends to zero as the number of users increases. Joint work with Sem Borst. |
