Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph (Q6101707): Difference between revisions

The Erdös-Rényi graph $G(n,p)$ is a graph of $n$ nodes where each edge is included with probability $p$ independently of other edges. These graphs are being investigated with a lot of interest for the last sixty years. The center of attraction is the distribution of the number of triangles in $G(n,p)$ in particular and certain subgraphs in general. The authors here are interested in extracting the Hoeffding-type exponential inequalities for the probability tails of the number of copies of a fixed subgraph in $G(n,p)$. In fact, they derive upper exponential inequalities for the tail probabilities of $R_n$, which are uniform in $n$, where $R_n$ is the centered and normalized number of copies of a fixed graph $G$ contained in the Erdös-Rényi graph with $n$ vertices.