Chebyshev's inequality says that for a random variable $Z$ with finite mean and variance, and every $t>0$,

The general Lovász local lemma concerns events $A_1,\dots ,A_m$ with a dependency graph: each $A_i$ is independent of the sigma-algebra generated by all nonneighbouring events other than itself. If numbers $x_i\in [0,1)$ satisfythen $\mathbb{P}({\bigcap }_i{A}_i^c)\ge {\prod }_i(1-x_i)>0$.

Its symmetric form states that if $\mathbb{P}(A_i)\le q$, every dependency degree is at most $d$, and $eq(d+1)\le 1$, then there is positive probability that no event occurs. For $d\ge 1$, set all $x_i=1/(d+1)$. Sincewe have $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log (1+1/d)\le 1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.

Let $Z_r$ be the size of generation $r$, with $Z_0=1$. Its offspring mean is $2p$, so conditioning on the previous generation gives $\mathbb{E}{Z}_r=(2p{)}^r$. At $p=1/2$,The interchange uses Tonelli's theorem for nonnegative variables. Critical extinction is nevertheless almost sure: its probability is the smallest root in $[0,1]$ of $s=(1+s^2)/2$, whose only root is one. Hence $K$ is finite almost surely. If all its finite atoms had the exponential bound, then $\mathbb{E}K\le {\sum }_{k\ge 1}k{e}^{-ck}<\infty$, a contradiction.

For $p>1/2$ the extinction probability is $(1-p)/p<1$. There is positive mass at $K=\infty$, so the mean is infinite even if every finite atom decays exponentially. This is precisely why the critical contradiction does not extend to the supercritical case.

The event $K=k$ implies $S_k=0$. If $B_k$ counts the positive increments, then $B_k\sim \mathrm{Bin}(k,p)$ and $S_k=1+2B_k-k$. Let $\delta =|p-1/2|>0$.

For $p>1/2$, $S_k=0$ forces $B_k=(k-1)/2\le k/2$, so the lower-tail Hoeffding form of the Chernoff bound givesFor $p<1/2$ and $k\ge 1/\delta$, the required value is at least $kp+\delta k/2$. The upper-tail bound gives $\mathbb{P}(K=k)\le e^{-{\delta }^{2}k/2}$.

To include all smaller positive integers, note that each finite-time atom has probability strictly less than one: at $k=1$ its probability is $1-p<1$, while for $k>1$ immediate extinction already has positive probability and excludes $K=k$. Over the finitely many small $k$ with nonzero atom, take the minimum of $-k^{-1}\log \mathbb{P}(K=k)$ and the applicable tail constant. This minimum is positive, and zero atoms impose no restriction. Thus for both cases there is $c>0$ such thatIn the supercritical case this bounds the finite atoms, not the positive probability of $K=\infty$.

Explore the individuals one at a time, maintaining the number of discovered but unprocessed individuals. It starts at $S_0=1$. Processing one individual removes it and adds its offspring, soThe offspring choices make these increments independent. Exploration stops when the queue first becomes empty; every processed individual has then been counted exactly once. Hencewith $K=\infty$ if the walk never hits zero. The increment sequence can be extended independently beyond the stopping time for probability estimates.

Write $N=|G|$ and $D(U)=e(G[U])-p\left(\genfrac{}{}{0ex}{}{|U|}{2}\right)$. For disjoint sets $U,W$ of size at least ${ϵ}^{2}N$, the given identity and the corresponding binomial identity giveIn the nonvacuous regularity range $0<ϵ<1$, the original sets therefore satisfy $|d(X,Y)-p|<{ϵ}^3/3$. Their allowed subsets have size at least ${ϵ}^{2}N$, so $|d(X^{\prime },Y^{\prime })-p|<ϵ/3$. The triangle inequality givesThus the pair is uniform. For $ϵ\ge 1$, the definition is vacuous or immediate; the subsequent positive-integer condition $k<1/ϵ$ has no solutions.

For the partition deduction, choose $k$ equal classes of size $q=\lfloor N/k\rfloor$, putting the remainder into $V_0$. For fixed $k<1/ϵ$ and sufficiently large $N$, $q\ge ϵN$ and $|V_0|<k<ϵN$. Every class pair is uniform by what was just proved, which is stronger than the required condition. For example, it suffices thatA graph-size qualification is necessary if the printed deduction is read literally for every graph order. Under the standard nonempty-class definition, a one-vertex graph satisfies the discrepancy hypothesis for every $p$ and positive $ϵ$, but cannot be partitioned into two nonempty classes even when $2<1/ϵ$. The source omits this small-order qualification. If $k$ divides $N$, no rounding is needed and $N\ge k$ already suffices, since $N/k>ϵN$.

In the standard regularity-partition convention, the vertex sets form a disjoint partition, the nonexceptional sets $V_1,\dots ,V_k$ are nonempty and have a common size, $|V_0|<ϵ|V(G)|$, and at most $ϵk^2$ unordered nonexceptional pairs fail to be $ϵ$-uniform. One can instead use weak inequality for the exceptional-set bound without affecting the argument below once the size bound is strict. The exceptional set absorbs the rounding remainder when the graph order is not divisible by $k$.

For nonempty disjoint vertex sets, the edge density is $d(X,Y)=e(X,Y)/(|X||Y|)$. A pair is $ϵ$-uniform, also called $ϵ$-regular, if every $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge ϵ|X|$ and $|Y^{\prime }|\ge ϵ|Y|$ satisfiesIt says that restricting to reasonably large subsets does not noticeably change the edge density.

Assume the usual nontrivial case $\chi (G)\ge 2$ and $|H|\ge 2$. On $(\chi (G)-1)(|H|-1)$ vertices partition into $\chi (G)-1$ equal classes of size $|H|-1$. Color all edges between distinct classes red and all edges within a class blue. The red graph is $(\chi (G)-1)$-colorable, so it contains no copy of $G$. Every blue connected component has only $|H|-1$ vertices, so connectedness prevents a blue copy of $H$. Therefore one more vertex is necessary:If $G$ is edgeless or $H$ has one vertex, the displayed lower bound is just one and holds directly.

The graph Ramsey number $R(G,H)$ is the least $N$ such that every red-blue coloring of the edges of $K_N$ contains a red copy of $G$ or a blue copy of $H$. Copies are ordinary subgraphs, not necessarily induced. Equivalently every graph on $N$ vertices contains $G$ or its complement contains $H$.