Deviation inequality for the number of k -cycles in a random graph

We study the number of k-cycles in a random graph G(n, p). We estimate the probability that a random graph contains more k-cycles than expected. In this case, the usual martingale inequality with bounded difference is not effective. By constructing a variable that approximates to the number of k-cycles in a random graph and using a new and extensive martingale inequality, we get the results in this paper. Foundation item: Supported by the National Natural Science Foundation of China (10571139)