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 set of $r$ vertices, exclude all triangles meeting that set. Their total expectation is $r\log (n/c)+o(1)$. Distinct triangle pairs sharing an edge contribute $O_r(n^3{p}^5)=o(1)$ to the Janson dependency sum. Harris' inequality and Janson inequality bound the avoidance probability between matching exponentials, giving $(c/n{)}^r(1+o(1))$. The factorial-moment criterion for Poisson convergence then gives the displayed law.

Construct an independent set by choosing a candidate vertex, exposing only its incident edges, and retaining its non-neighbours as candidates. Once the chosen independent set is removed, every exposed edge has a removed endpoint. Thus the remaining internal edges still have their independent original laws, conditional on the revealed history. This special exposure rule permits fresh-binomial estimates for successive classes; an arbitrary adaptively selected vertex subset does not have that property.

A finite graph $H$ with at least one edge is strictly balanced when every proper nonempty subgraph $F$ has smaller edge-to-vertex ratio. It is connected and has no isolated vertices: otherwise a component of at least the average density, or deletion of isolated vertices, violates the inequality. The density condition suppresses overlapping copies at the sparse appearance scale.

Here $v,e,a$ are the numbers of vertices, edges and graph automorphisms of $H$. Vertex-disjoint ordered $r$-tuples contribute $(n{)}_{rv}{p}^{re}/a^r\to (c^e/a{)}^r$ to the factorial moment. Adding a copy overlapping the previous union in $f$ vertices and $g$ edges changes the power of $n$ by $-f+(v/e)g\le 0$, strictly when the intersection is a proper nonempty subgraph. The first overlap is strict because $H$ is connected and the previous copies are disjoint. Finitely many overlap types therefore contribute $o(1)$. The factorial-moment criterion for Poisson convergence gives the result.

Let $X$ count unordered vertex pairs with no common neighbour in a binomial random graph. Each other vertex provides the required pair of edges independently, with success probability $p^2$. A fixed pair has no common neighbour with probability $(1-p^2{)}^{n-2}$. Summing its indicators gives the displayed expectation.

For fixed $0<p<1$, the missing common-neighbour count in a binomial random graph has expectation tending to zero. The Markov inequality therefore shows that every pair has a common neighbour with probability tending to one. On that event every graph distance is at most two, so the graph is connected and its graph diameter is at most two.

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 fixed $k\ge 2$, a binomial random graph has no $k$-cliques with probability tending to one if ${\mu }_n\to 0$, and has at least one with probability tending to one if ${\mu }_n\to \infty$. The first assertion uses the first moment method. The second uses the overlap formula for the variance of a clique count: overlapping $k$-sets with $l\ge 2$ contribute $O(n^{-l}{p}^{-\left(\genfrac{}{}{0ex}{}{l}{2}\right)})$, and each contribution tends to zero above this threshold. The fixed-size qualification matters.

With these parameters the expected number of $(n-1)$-cliques is asymptotic to $\sqrt{n}$, yet the probability of any such clique tends to zero. The complement graph has about $\frac{1}{2}\log n$ edges, and with probability tending to one two of them are vertex disjoint. Deleting one vertex cannot remove both edges. Thus divergence of the expected clique count alone does not give an appearance theorem for arbitrary growing clique size.

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.

Write ${\mu }_r=\left(\genfrac{}{}{0ex}{}{n}{r}\right)p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$ and $T_s=\left(\genfrac{}{}{0ex}{}{r}{s}\right)\left(\genfrac{}{}{0ex}{}{n-r}{r-s}\right)p^{-\left(\genfrac{}{}{0ex}{}{s}{2}\right)}/\left(\genfrac{}{}{0ex}{}{n}{r}\right)$. The first mean condition implies $p^{-1}\le (en/r{)}^{2/(r-1)}$ eventually. For $2\le s\le r/2$, this yields $T_s\le (C/s{)}^s$, and each fixed-$s$ term tends to zero when $n\ge r^3$. The second mean condition implies $p\le ((r+1)/n{)}^{2/r}$ eventually. Writing $s=r-j$ gives $T_{r-j}={\mu }_r^{-1}\left(\genfrac{}{}{0ex}{}{r}{j}\right)\left(\genfrac{}{}{0ex}{}{n-r}{j}\right)p^{j(2r-j-1)/2}\le {\mu }_r^{-1}(C/j{)}^j$ for $1\le j\le r/2$, and $T_r={\mu }_r^{-1}$. Both bounding series are summable. The overlap formula for the variance of a clique count therefore gives relative variance tending to zero; the second moment method proves an $r$-clique exists with high probability.

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$.

For the triangle count in a binomial random graph, distinct triangle indicators are independent unless they share an edge. A shared-edge pair has covariance $p^5(1-p)$, and there are $12\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ ordered pairs of that type. The individual indicator variances give the first term. Equivalently,by counting ordered pairs according to the number of shared vertices.

If $np\to 0$, the triangle count in a binomial random graph has expectation at most $(np{)}^3/6\to 0$, so the Markov inequality shows there are no triangles in a graph with probability tending to one. If $np\to \infty$, the triangle variance in a binomial random graph divided by the squared mean is $O((np{)}^{-3})+O((n^{2}p{)}^{-1})\to 0$. The second moment method then gives at least one triangle in a graph with probability tending to one. At the intermediate scale $np\to c\in (0,\infty )$, a nontrivial Poisson limit for triangles in a binomial random graph describes the count.

Convergence holds in total variation distance. A triangle indicator depends only on its three edges, so its dependency neighborhood consists of itself and the $3(n-3)$ triangles sharing an edge. The Poisson approximation with dependency neighborhoods gives errors $b_1=O(n^4{p}^6)$ and $b_2=O(n^4{p}^5)$. Under the displayed scaling $p$ is of order $n^{-1}$, so both vanish. The probability of at least one triangle therefore tends to $1-e^{-\alpha }$.

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.