Binomial random graph ($G(n,p)$)

The binomial random graph $G(n,p)$ has vertex set $\{1,\dots ,n\}$ and includes each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges independently with probability $p$.

For a fixed probability strictly between zero and one, the largest independent set has leading size $2{\log }_{1/(1-p)}n$, giving a lower bound for colouring. The matching upper bound uses independent sets in every large subset of a dense random graph, then repeatedly colours and removes such sets. A sufficiently strong probability estimate makes the failure contribution negligible for the expectation.

For fixed $p$ and $\gamma >0$, Janson inequality bounds the failure probability for a given large vertex subset by $\exp (-c|U{|}^2/(\log n{)}^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because vertex sets left by a greedy colouring procedure depend on the graph; one cannot assume each adaptively chosen remainder is an independent fresh random graph.

Group random edges by their larger endpoint. These independent coordinates each change edges incident to only one vertex. Removing that vertex leaves the same graph under any two outcomes, so their chromatic numbers differ by at most one. The McDiarmid inequality with $n$ coordinate ranges of length one gives the displayed concentration bound.

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

If $X_t$ counts copies of the complete graph $K_t$ in $G(n,p)$, thenConsequently $p{n}^{2/(t-1)}\to 0$ implies $\mathbb{P}(X_t>0)\to 0$ by the first moment method.

For the number $X$ of $k$-cliques in a binomial random graph $G(n,p)$, with $0<p<1$ and $\mu =\mathbb{E}X$,Two $k$-sets overlapping in $j$ vertices share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the second moment method.

If $X$ counts triangles in $G(n,p)$, thenandThus $np\to \infty$ implies $\mathrm{var}X/(\mathbb{E}X{)}^2\to 0$, and the second moment method gives $\mathbb{P}(X>0)\to 1$.

Partition the vertices into two sets of comparable size. If $np\to \infty$, the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at mostHence $G(n,p)$ contains a triangle with an attached leaf with probability tending to one.