I'd like to get an estimate on the number of $H$-free graphs, i.e. graphs in which no set of $|V(H)|$ vertices induces a copy of $H$. There are results on this, but I have some problems in interpreting the probabilistic arguments. For simplicity, let $H = K_3$, a triangle.
Let $G$ be a random graph on $n$ vertices in which each edge appears with probability $1/2$.
From this paper, we have that $Pr[G$ is $H$-free$] \leq e^{-c n^3/8}$ for some constant $c$ (see abstract, put $p = 1/2$ and $H = K_3$).
This probability seems very low, and I must be misinterpreting something. Here's my problem.
Let $f(n)$ be the number of $H$-free graphs on $n$ vertices. Then since $G$ is equally likely to be any graph on $n$ vertices, $$Pr[G\mbox{ is }H\mbox{-free}] = f(n)/2^{{n \choose 2}}$$
i.e. the number of $H$-free graphs divided by the total number of graphs.
But
$$ f(n)/2^{{n \choose 2}} = Pr[G\mbox{ is }H\mbox{-free}] \leq e^{-c n^3/8} $$
implies
$$ f(n) \leq 2^{n \choose 2}e^{-c n^3/8} < 1 $$
for large enough $n$.
Hence there are no triangle-free graphs.
Where is the mistake?
The mistake occurs in the application of their theorem. You are right that any probability below $\frac{1}{2^{{n \choose 2}}}$ must be zero. But per their abstract, $M=n^2 p$ rather than $m=n^3 p^3$.