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 construct-ing 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.