Upper tails for subgraph counts in random graphs (Q1881736): Difference between revisions

Let \(X\) be the number of copies of a fixed graph \(G\) contained in the random graph on \(n\) vertices with edge probability \(p\). The upper tail of the probability distribution of \(X\) is shown to have best possible (in a certain sense) upper and lower bounds in terms of \(n\) and \(p\). Similar bounds are also proved for the random graph on \(n\) vertices with a fixed number of edges.