The Random Threshold Graph Model

Speaker:
Organiser:
Jaikumar Radhakrishnan
Date:
Friday, 19 Oct 2012, 10:00 to 11:00
Venue:
A-212 (STCS Seminar Room)
Category:
Abstract
Let $G$ be a random graph generated as follows:- each vertex $i$ of the vertex set $\{1,\ldots,n\}$ has an associated random variable $X_i$ where $\{X_i : i \ge 1\}$ are i.i.d. Two vertices $i$ and $j$ are connected by an edge if and only if, $X_i + X_j > \theta$ where $\theta$ is a given threshold value. We study some properties of this graph $G$.