  We prove moderate deviations bounds for the lower tail of the number of odd
cycles in a $\calG(n, m)$ random graph. We show that the probability of
decreasing triangle density by $t^3$, is $\exp(-\Theta(n^2 t^2))$ whenever
$n^{-3/4} \ll t^3 \ll 1$, while for $k \ge 5$ we give the same estimate for the
probability of decreasing the $k$-cycle density by $t^k$, but for the larger
range $n^{-1} \ll t^k \ll 1$. When $m \ge \frac 12 \binom n2$, we also find the
leading coefficient in the exponent. This complements results of Goldschmidt et
al., who showed that for $n^{-3/2} \ll t^k \ll n^{-1}$, the probability is
$\exp(-\Theta(n^3 t^{2k}))$. That is, deviations of order smaller than $n^{-1}$
behave like small deviations, and deviations of order larger than $n^{-3/4}$
(for triangles) or $n^{-1}$ (for $k$-cycles with $k \ge 5$) behave like large
deviations. For triangles, we conjecture that a sharp change between the two
regimes occurs for deviations of size $n^{-3/4}$, which we associate with a
single large negative eigenvalue of the adjacency matrix becoming responsible
for almost all of the cycle deficit. Our results can be interpreted as finite
size effects in phase transitions in constrained random graphs.
