Seminar at SMU Delhi

September 26, 2012 (Wednesday) , 3:30 PM at Webinar
Speaker: Ghurumuruhan Ganesan, Indian Statistical Institute, Delhi
Title: Size of Giant Component and Infection Spread in Random Geometric Graphs
Abstract of Talk
Consider \(n\) nodes independently and uniformly distributed in the unit square \(S\) centred at origin. Connect two nodes by an edge if the distance between them is less than \(r_n,\) where \(nr_n^2 \longrightarrow \infty\) and \(nr_n^2 \leq A\log{n}\) for some constant \(A.\) The resulting graph \(G\) is called the random geometric graph. In the first part of the talk, we show that the giant component of \(G\) contains at least \(n - o(n)\) nodes with probability at least \(1 - o(1).\) In the second part of the talk, we study infection spread in \(G.\) We prove that the infection spreads with speed at least \(D_1nr_n^2\) and at most \(D_2nr_n^2\) for some positive constants~\(D_1\) and~\(D_2.\) This is unlike infection spread in regular graphs (like e.g. \(\mathbb{Z}^2\)) where infection spreads at a constant speed. Reference: G. Ganesan. (2012). Size of the Giant Component in a Random Geometric Graph. Accepted for Publ. in Ann. Inst. Henri Poin.