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.