CSE 525 (Spring 2019): HW #3

Due: Fri, Apr 26, 11:59pm

Problem 1: Concentration in isolation

Consider a graph $G \sim \mathcal{G}_{n,p}$ with $p=D/n$ and $D > 0$ is some fixed number. Let $X$ be the number of isolated vertices in $G$ (i.e., the number of vertices that have no neighbors). Determine $\mathbb{E}[X]$ and then show that for any $\lambda > 0$,

[Hint: Setup an “edge exposure” martingale. You will need to control the number of exposure steps.]