# 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.]