Edge density in subgraphs of an Erdos-Renyi graph $G(n,p)$

Question

Given an Erdos-Renyi random graph $G\sim G(n,p)$, I want to estimate the probability that all the subgraphs of $G$ (that are not too small, say subgraphs on $m>\epsilon n$ vertices) have edge density of approximately $p$. That is: $$Pr\left(\forall H\in G : V(H)>\epsilon n, \left|\frac{E(H)}{V(H)2}-p\right|<\epsilon'\right).$$ I suspect that this probably tends to $1$ as $n\rightarrow \infty$, but not sure how to show this.

Answer 1

The following will work if $p=p(n) \geq n^{- 1 + \delta} $ for some arbitrarily small $\delta >0$.

Fix some $\epsilon > 0$ and let $A$ be any set of $\epsilon n$ vertices. The subgraph $G[A]$ has an expected $\mu = p \binom{|A|}{2} \approx \frac12 p \epsilon^2 n^2 \geq n^{1+\delta}$ edges. By Chernoff's Bound, \begin{equation} \mathbb{P}\left[ |E (G[A]) - \mu| \geq \epsilon' \mu \right ] \leq 2 \exp\left\{ - \frac13 (\epsilon')^2 \mu \right\} \leq \exp\left\{ - C n^{1+\delta} \right\}, \end{equation} where $C$ is some constant. The probability that some set $A$ violates the above is at most $2^n$ times the above (there are at most $2^n$ subsets of vertices of $G$), giving failure probability \begin{equation} \exp\left\{n \ln 2 -C n^{1+ \delta} \right\} \to 0. \end{equation}