CRI Doctoral Forum Lecture, 2008-2009

Tobias Mueller
Tel Aviv University
Wednesday, May 6, 14:10-15:10

Title: Colouring Random Geometric Graphs


Abstract:

The random geometric graph G(n,r) is constructed by picking n vertices X_1,...,X_n from the d-dimensional unit cube [0,1]^d (i.i.d. uniformly at random) and adding an edge X_iX_j if |X_i-X_j|< r. In this talk, I will discuss the behaviour of the chromatic number of G(n,r) and some related random variables when n tends to infinity and r=r(n) is allowed to vary with n.


Host: Raphy Yuster



Martin Charles Golumbic