CSE 525 (Spring 2019): HW #3

Due: Fri, Apr 26, 11:59pm

Problem 1: Concentration in isolation

Consider a graph with $p=D/n$ and $D > 0$ is some fixed number. Let be the number of isolated vertices in (i.e., the number of vertices that have no neighbors). Determine and then show that for any ,

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