Clique Number of Random Geometric Fraphs in High Dimension

Professor Sebastien Bubek
Professor, Princeton University
Given on: Nov. 14th, 2013


In small dimension a random geometric graph behaves very differently from a standard Erdös-Rényi random graph. On the other hand, when the dimension tends to infinity (with the number of vertices being fixed) both models coincide. In this talk we study the behavior of the clique number of random geometric graphs when the dimension grows with the number of vertices. Surprisingly we use techniques from the theory of minimax lower bounds to prove the existence of threshold phenomena.


Sebastien Bubeck is an assistant professor in the department of Operations Research and Financial Engineering at Princeton University. He joined Princeton after a postdoc at the Centre de Recerca Matematica in Barcelona, where he was working with Gabor Lugosi. He received his Ph.D. in mathematics from the University of Lille 1, advised by Remi Munos, after undergraduate studies at the Ecole Normale Superieure de Cachan. His research focuses on the mathematics of machine learning, with emphasis on problems related to multi-armed bandits. His work was recognized by several awards, such as the COLT 2009 best student paper award, and the Jacques Neveu prize 2010 for the best French Ph.D. in Probability/Statistics.