Moderate deviations in cycle count.

We prove moderate deviations bounds for the lower tail of the number of odd cycles in a 풢(n,m) random graph. We show that the probability of decreasing triangle density by t3, is exp(−Θ(n2t2)) whenever n−3/4≪t3≪1. These complement results of Goldschmidt, Griffiths, and Scott, who showed that for n−3/2≪t3≪n−1, the probability is exp(−Θ(n3t6)). That is, deviations of order smaller than n−1 behave like small deviations, and deviations of order larger than n−3/4 behave like large deviations. 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. We give analogous results for the k‐cycle density, for all odd k. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs. [ABSTRACT FROM AUTHOR]