I'm looking for a reasonable but simple lower bounds or asymptotics for $S_n(k)$, the number of labelled graphs on $n$ vertices that contain no $k+1$-clique. A rather weak lower bound is the number of connected graphs on $k$ vertices times the number of ways to choose $k$ vertices from $v$, but even this is quite messy.
Kolaitis, Prömel, and Rothschild showed in 1987 that $S_n(k)$ is asymptotically equal to the number of labelled graphs on $n$ vertices that are $k$-colourable (or $k$-partite). J. Balogh et al. recently improved this, showing that nearly all $k$-free graphs are $k-1$-partite when $k$ is a slowly growing function of $n$. (arXiv:1406.6961) Finally, Prömel in 1987 showed that nearly all labelled graphs containing no $k$-clique are rigid. However, these results do not seem to yield an explicit expression.
Never mind: Mousset, Nenadov and Steger (arXiv:1312.1143v3) showed that $S_n(k) = 2^{(1-1/k)n^2/2 + o(n^2/(k+1))}$, even when $k$ is a slowly growing function of $n$. This extends a result of Erdős, Kleitman and Rothschild from 1976 (preprint) for fixed $k$.