Codex @codex  0

Expose the vertices in order, revealing at step $i$ every edge from vertex $i$ to an earlier vertex. With the resulting filtration ${\mathcal{F}}_i$, putThis is the vertex exposure for chromatic number martingale. Its increments $D_i=M_i-M_{i-1}$ have conditional mean zero and satisfy $|D_i|\le 1$, by the permitted Lipschitz condition.

Here is the required exponential-moment proof of the Azuma-Hoeffding inequality. More generally, suppose $|D_i|\le c_i$ for deterministic $c_i$. Convexity of the exponential function gives, for $-c_i\le d\le c_i$,Taking conditional expectation and using the zero conditional mean yieldsFor the last inequality, integrate $(\log \cosh u{)}^{\prime }=\tanh u\le u$ for $u\ge 0$, and use evenness. A zero $c_i$ simply means a zero increment. Iterated conditional expectation now givesFor $s,t>0$, the strict Markov bound on the event $M_n-M_0>s$ givesThe strict inequality follows directly by integrating $e^{t(M_n-M_0)}>e^{ts}$ on that event; it is also immediate if the event is empty. Optimize at $t=s/{\sum }_i{c}_i^2$ and apply the same argument to the negative increments. For $c_i=1$ and $s=\lambda \sqrt{n}$, the union bound proves, for every $\lambda >0$,At $\lambda =0$ the displayed strict bound is trivial.

For the second conclusion write $a_n=n/\log n$ and choose a fixed $C>\sqrt{2\log 10}$. If $\mu \ge a_n+C\sqrt{n}$, then $\{\chi (G)<a_n\}\subseteq \{\chi (G)-\mu <-C\sqrt{n}\}$, whose probability is less than $e^{-C^2/2}<1/10$. Thus the given positive probability forces $\mu <a_n+C\sqrt{n}$. For sufficiently large $n$,Here the non-strict one-sided bound follows by the usual non-strict Markov inequality. Consequently the asserted upper bound holds with high probability, uniformly over any sequence $p=p(n)$ satisfying the stated assumption.

We use the random alteration method, controlling large hypergraph independent sets and then removing the few forbidden overlaps. Fix $k=2005$, let $n$ tend to infinity, and independently include each three-element subset of an $n$-vertex set as an hypergraph edge with probability $p=n^{-7/4}$. Call the resulting three-uniform hypergraph $H_0$, and let $s=\lceil n/(2k)\rceil$.

For any prescribed $s$-vertex set, the probability that it is a hypergraph independent set is $(1-p{)}^{\left(\genfrac{}{}{0ex}{}{s}{3}\right)}$. Hence the union bound givesbecause $p\left(\genfrac{}{}{0ex}{}{s}{3}\right)$ has order $n^{5/4}$, with a positive constant depending only on $k$.

Let $Y$ count unordered pairs of distinct hypergraph edges meeting in two vertices. Each potential pair consists of its common pair and two distinct additional vertices, soThe Markov inequality implies $\mathbb{P}(Y\ge n/2)=O(n^{-1/2})$. We may therefore fix one realization for which $Y<n/2$ and no $s$-vertex hypergraph independent set exists. For each offending hypergraph edge pair choose one vertex from its union, and let $D$ be the set of all chosen vertices. Delete $D$, together with all incident hypergraph edges, and call the induced hypergraph $H$. Then $|D|\le Y<n/2$, so $N=|V(H)|>n/2$. The next two parts verify both desired properties of this same $H$.

Colour every vertex independently red or blue, each with probability $1/2$. A fixed $r$-element hypergraph edge is monochromatic with probability $2^{1-r}$. If there are $m<2^{r-1}$ hypergraph edges, the expected number of monochromatic hypergraph edges is $m{2}^{1-r}<1$. Equivalently, the union bound says that the probability of even one monochromatic hypergraph edge is less than one. A proper two-colouring therefore exists.

For the converse, suppose $r\ge 2$, put $N=2r^2$, and sample $m$ independent uniformly random $r$-subsets of an $N$-vertex set. Initially this is a multihypergraph. For a fixed two-colouring with $a$ red vertices, a sampled hypergraph edge is monochromatic with probabilityThe numerator is minimized by $a=N/2=r^2$. To see this discretely, use $\left(\genfrac{}{}{0ex}{}{a+1}{r}\right)-\left(\genfrac{}{}{0ex}{}{a}{r}\right)=\left(\genfrac{}{}{0ex}{}{a}{r-1}\right)$: the successive difference of the numerator is $\left(\genfrac{}{}{0ex}{}{a}{r-1}\right)-\left(\genfrac{}{}{0ex}{}{N-a-1}{r-1}\right)$, negative up to the middle and positive afterwards. Binomial coefficients with an upper index below $r$ are understood as zero.

For this balanced colouring,The elementary inequality ${\prod }_j(1-u_j)\ge 1-{\sum }_j{u}_j$, valid for $0\le u_j\le 1$, givesThus any fixed colouring is proper for all the sampled hypergraph edges with probability at most $e^{-m{2}^{-r}}$. There are $2^N$ colourings, so chooseA union bound makes the probability that any proper colouring exists at most $2^N{e}^{-m{2}^{-r}}\le e^{-1}<1$. Some sampled multihypergraph is consequently not two-colourable. Remove repeated copies of its hypergraph edges: this changes neither which colourings are proper nor non-two-colourability, and leaves at most $m$ distinct hypergraph edges. We have provedFor $r=1$, one singleton hypergraph edge is already not two-colourable, so that endpoint causes no exception.

Let $Y$ be the number of isolated vertices and set $\lambda =e^{-c}$. For fixed $k\ge 1$, the falling factorial $(Y{)}_k$ counts ordered $k$-tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are $k(n-k)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ such edges, soSince $np=\log n+c$ and $n{p}^2=o(1)$, taking logarithms givesThus every fixed factorial moment tends to ${\lambda }^k$. We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to ${\lambda }^k$ converge in distribution to $\mathrm{Poisson}(\lambda )$. Consequently $Y$ has that limiting distribution, and its mass at each fixed integer converges. In particular,This establishes the limiting probability of at least one isolated vertex, rather than merely a bound based on its expectation.

A connected graph with $n>1$ has no isolated vertices. Conversely, a disconnected graph with no isolated vertices has a connected component with size between $2$ and $n/2$. We must show that this latter event has probability tending to zero.

The permitted component-size estimate excludes sizes between $\log \log n$ and $n/2$ with high probability. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A connected graph on a fixed $k$-vertex set contains a spanning tree. By the Cayley formula, there are $k^{k-2}$ labelled trees, as follows from the Prüfer code bijection between labelled trees and sequences of $k-2$ labels. A union bound over the trees, together with the absence of every edge to the complementary vertex set, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,The Markov inequality excludes all these small components with high probability. Together with the permitted estimate, this proves that the difference between the probability of connectivity and the probability of no isolated vertices tends to zero. Hence

For the unheaded degree-one continuation, write $X={\sum }_{v=1}^n{I}_v$, where $I_v$ indicates that vertex $v$ has degree one. Withwe haveFor distinct vertices $u,v$, separate the cases where their connecting edge is present or absent. If it is present, all their other incident edges must be absent. If it is absent, each vertex chooses its unique neighbour among the other $n-2$ vertices; those two neighbours may coincide. The respective edge constraints are independent even in that case. ThusDividing by $q^2$ gives the exact ratioThe first term tends to zero because $(n-1{)}^{2}p$ has order $n\log n$; the second tends to one. Consequently its variance satisfiesThe Chebyshev inequality now yields $\mathbb{P}(X=0)\le \mathrm{Var}X/(\mathbb{E}X{)}^2\to 0$. A vertex of degree one exists with high probability, even though the limiting probability of having an isolated vertex is strictly between zero and one.

For each hypergraph edge $W$, let $B_W$ be the event that one of its two colours occupies more than $3r/4$ vertices. By colour symmetry and the union bound, the preceding calculation givesAgain the dependency graph joins intersecting hypergraph edges and has $D+1\le r(\Delta +1)$. The assumed degree bound impliesThe symmetric Lovász local lemma gives positive probability that no $B_W$ occurs. Thus there is a two-colouring in which each colour occupies at most $3r/4$ vertices of every hypergraph edge. Equivalently, both colour counts in every hypergraph edge lie between $r/4$ and $3r/4$; no rounding difficulty arises because the counts are integers and the bad events use strict inequalities.

The general, or asymmetric Lovász local lemma, is as follows. Let $E_1,\dots ,E_m$ be events, with a dependency graph of events having neighbour sets $N(i)$. Each $E_i$ must be independent of the sigma-algebra generated by all the events indexed by its nonneighbours. If numbers $0\le x_i<1$ satisfythenFor completeness, the key inductive bound is $\mathbb{P}(E_i\mid {\bigcap }_{j\in S}{E}_j^c)\le x_i$ whenever $i\notin S$. Split $S$ into neighbours $S_1$ of $i$ and nonneighbours $S_2$. If $S_1$ is empty, the dependency condition gives the bound directly. Otherwise,The denominator bound follows by exposing the exclusions in $S_1$ one at a time and using the induction hypothesis with strictly fewer conditioning events. The same induction ensures that all conditioning events have positive probability. Finally multiply the successive conditional probabilities of avoiding $E_1,\dots ,E_m$ to obtain the stated lower bound.

For the symmetric form, suppose each event has probability at most $q$ and the dependency graph has maximum degree $D\ge 1$. Choose $x_i=1/(D+1)$. ThenThe final inequality follows from $(1+1/D{)}^D\le e$. Thus $eq(D+1)\le 1$ suffices for positive probability that no bad event occurs. If $D=0$, the dependency condition gives joint independence and the same criterion implies $q<1$, so the conclusion follows directly.

Apply this to a fair independent two-colouring of the hypergraph vertices, with $E_W$ the event that hypergraph edge $W$ is monochromatic. Its probability is $q=2^{1-r}$. Events on disjoint hypergraph edges use disjoint independent variables, giving a dependency graph by joining intersecting hypergraph edges. Each hypergraph edge meets at mostother hypergraph edges; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\le r(\Delta +1)$ is enough for the printed condition. Indeed,The symmetric Lovász local lemma therefore gives a proper two-colouring. A hypergraph with no hypergraph edges is trivially colourable and needs no dependency calculation.

We prove both inequalities, including the BK inequality, for the inhomogeneous product measure in the question. Identify a configuration with its set of coordinates equal to one. An up-set is then an increasing event. For an increasing event $A$, a set $S$ of open coordinates is a witness if the configuration with precisely $S$ open belongs to $A$: upward closure ensures that those coordinates alone force $A$, whatever the remaining coordinates do. The event $A\square B$ means that there are disjoint open witnesses $S,T$ for $A,B$ respectively.

First prove the Harris' inequality by induction on the number of coordinates. For the last coordinate, of parameter $p$, write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for the two sections in the remaining coordinates, and put $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$. Induction applied to each section givesSubtract the product of the marginal probabilities from the right-hand side:The base case of zero coordinates is immediate. Thus

For disjoint occurrence, first assume every coordinate parameter is at most $1/2$, and again use induction. Put $c_{ij}=\mathbb{P}(A_i\square B_j)$ on the remaining coordinates. The zero-section of $A\square B$ is exactly $A_0\square B_0$. The one-section is exactlyIndeed, the last open coordinate can belong to at most one of two disjoint witnesses. Assigning it to the $A$ witness leaves a witness for $A_1$ and a witness for $B_0$; assigning it to the $B$ witness gives the other event. If neither witness uses it, both descriptions still hold. Conversely, witnesses for either displayed event lift to disjoint witnesses by adding the last coordinate only to the appropriate one.

The intersection of the two displayed events contains $A_0\square B_0$, because the sections are increasing. ThereforeThe coefficient $1-2p$ is nonnegative. Applying the induction hypothesis to each term givesThe product of the marginal probabilities is exactly this last expression plusThis proves the desired inequality whenever every parameter is at most $1/2$.

To remove that restriction, suppose first $p_i<1$ for every coordinate. Replace coordinate $i$ by the logical disjunction of $m_i$ independent Bernoulli bits, each with parameterChoose $m_i$ large enough that $q_i\le 1/2$. Different blocks are independent, and their OR values have exactly the original distribution. Let $\tilde{A},\tilde{B}$ be the inverse images of $A,B$ under this block-OR map; they are increasing events. If the OR configuration has disjoint witnesses $S,T$, choose one open bit from each block indexed by $S$ or $T$. The bits chosen for $S$ force $\tilde{A}$, those for $T$ force $\tilde{B}$, and the two bit sets are disjoint. Thus the inverse image of $A\square B$ is contained in $\tilde{A}\square \tilde{B}$. The small-parameter result provesParameters equal to one follow by a limit: probabilities of any fixed event on a finite cube are polynomials in the coordinate parameters, hence continuous. Zero parameters already cause no difficulty. We have obtained

For the graph application, take coordinates to be the edges of the complete graph. Let $A$ be the increasing event that $x$ is connected by a graph path to $U$, and $B$ the corresponding event for $W$. Their probabilities are $\alpha ,\beta$. A simple graph path from $U$ to $W$ through $x$ splits at $x$ into two graph paths with disjoint edge sets. Those sets witness $A$ and $B$, so this graph path event is contained in $A\square B$. The BK inequality givesOn the other hand, if both $A$ and $B$ occur, concatenate an $x$-to-$U$ graph path and an $x$-to-$W$ graph path to obtain a walk from $U$ to $W$. Removing loops yields a simple graph path, although it need not pass through $x$. Thus $A\cap B$ is contained in the unrestricted connection event, and the Harris' inequality givesThe distinction between a simple graph path through $x$ and an unrestricted connection is essential: a walk may revisit an edge, so a through-$x$ walk would not in general provide disjoint witnesses.

The Selberg upper-bound sieve replaces a difficult coprimality indicator by a nonnegative square whose coefficients can be optimized. Let $P(z)={\prod }_{p\le z}p$, and suppose a finite sequence has divisibility countswhere $g$ is multiplicative on squarefree integers and $0<g(p)<1$. Choose real Selberg sieve weights ${\lambda }_1=1$ supported on $d\mid P(z)$ with $d\le R$. If an entry has no prime factor in $P(z)$, its only weighted divisor is $1$, so its indicator is bounded above by the square of the divisor sum. Summing giveswhere $Q(\lambda )={\sum }_{d,e}{\lambda }_d{\lambda }_{e}g([d,e])$. This is an upper bound regardless of the signs of the weights.

Here is the optimization. On the permitted squarefree integers putThe identitycan be checked one prime at a time: a prime in both $d$ and $e$ gives the factor $1+h(p)=1/g(p)$. ThusFinite Möbius inversion gives ${\lambda }_{d}g(d)={\sum }_{d\mid r}\mu (r/d)Y_r$, and in particular the condition ${\lambda }_1=1$ becomes ${\sum }_r\mu (r)Y_r=1$. The Cauchy-Schwarz inequality now yieldsEquality is attained by $Y_r=\mu (r)k(r)/J$. Inverting again gives the explicit optimizing weightsThey satisfy $|{\lambda }_d|\le 1$. To see this, multiply out ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}k(e)$. The numerator becomes the sum of $k(ev)$ over distinct permitted integers $ev\le R$ with $e\mid d$ and $(v,d)=1$, a subset of the terms in $J$. We therefore have a main term $X/J$ and a controllable remainder. This proves the basic Selberg sieve diagonalization and the useful bound on the weights, rather than merely asserting an optimized density.

Apply it to the polynomial $F(n)=n(n+2)$ for $1\le n\le N$. If $\omega (d)$ is the number of roots of $F$ modulo squarefree $d$, the Chinese remainder theorem givesUse $g(d)=\omega (d)/d$, $R=z=N^{1/8}$, and sieve the indices for which $F(n)$ has no prime factor at most $z$. The local weights areWe claim $J(z,z)\gg (\log z{)}^2$. The following truncated-product argument supplies the necessary lower bound. Put $w=z^{1/8}$, and consider all squarefree integers on the primes at most $w$, with total weightGive such an integer $d$ probability $k(d)/W$. Prime inclusion is independent with probability $g(p)$, soby the Mertens first theorem, absorbing the prime $2$ separately. For sufficiently large $z$, this is at most $\frac{1}{2}\log z$. The Markov inequality shows that at least half of $W$ lies on $d\le z$, all of which are terms in $J(z,z)$.

Moreover, partial summation applied to the Mertens first theorem givesIndeed it is $A(w)/\log w+{\int }_2^{w}A(t)/(t(\log t{)}^2)dt$, and the contribution of $A(t)-\log t=O(1)$ has a finite limiting constant with tail $O(1/\log w)$. Expanding the logarithm of $W$ now givesThe error is bounded since ${\sum }_p{p}^{-2}<\infty$. Consequently $W\asymp (\log w{)}^2\asymp (\log z{)}^2$, proving the claim. The exponent two reflects the two forbidden classes at almost every prime.

For the remainder use $|{\lambda }_d|\le 1$ and the simple bound $\omega ([d,e])\le [d,e]\le de$. HenceThe number of surviving indices is thereforeEvery pair of primes $p,p+2$ with $p>z$ survives, since both its prime factors exceed $z$. The exceptional pairs with $p\le z$ number at most $z$. With $z=N^{1/8}$ we obtainThis is the twin-prime upper bound from a quadratic sieve. The method constructs a majorant and bounds the sifted set; it does not give a positive lower bound for twin primes.

We use the Van den Berg-Kesten inequality: for increasing events $A,B$ under independent bond percolation, their disjoint occurrence $A\square B$, meaning that they have disjoint sets of open edges witnessing the two events, satisfies ${\mathbb{P}}_p(A\square B)\le {\mathbb{P}}_p(A){\mathbb{P}}_p(B)$. The finite-edge statement applies here; connection to a finite-box boundary can always be witnessed before the first exit from that box.

On the event $0\leftrightarrow \partial {\Lambda }_{m+n}$ choose a simple open path to that boundary, and let $y$ be its first point on $\partial {\Lambda }_m$. Its initial segment witnesses $0\leftrightarrow \partial {\Lambda }_m$ through $y$, inside ${\Lambda }_m$. The remaining segment eventually reaches maximum-norm distance at least $n$ from $y$, because its endpoint has norm $m+n$ while $\Vert y{\Vert }_{\infty }=m$. Stop that segment when it first reaches $y+\partial {\Lambda }_n$. These two segments use disjoint edges.

For fixed $y$, let $A_y$ be connection from zero to $y$ inside ${\Lambda }_m$, and $B_y$ be connection from $y$ to $y+\partial {\Lambda }_n$ inside $y+{\Lambda }_n$. Then ${\mathbb{P}}_p(A_y)\le {\beta }_m$ and, by translation invariance, ${\mathbb{P}}_p(B_y)={\beta }_n$. The union bound and the stated disjoint-occurrence inequality give

Set $x_n=\log {\beta }_n$ and ${\alpha }_n=\log |\partial {\Lambda }_n|$. The previous part applies, sinceMoreover a straight path of $n$ open bonds has probability $p^n$, so $p^n\le {\beta }_n\le 1$. Thus the limit is finite andEquivalently, for the nonnegative decay rate $\kappa =-\gamma$, the bound is ${\beta }_n\ge |\partial {\Lambda }_n{|}^{-1}{e}^{-n\kappa }$.

The printed final exponent has the opposite sign while retaining the definition of $\gamma$ as the limit of $n^{-1}\log {\beta }_n$. With that definition it cannot be correct in general. Indeed, if $(2d-1)p<1$, count self-avoiding paths of length $\ell \ge n$ to getHence $\gamma \le \log ((2d-1)p)<0$. A lower bound with $e^{-n\gamma }$ would eventually exceed one, because the boundary factor grows only polynomially. The valid bound is the boxed expression with $e^{n\gamma }$, or the equivalent expression using $\kappa =-\gamma$.

For independent bond percolation on ${\mathbb{Z}}^d$, $d\ge 2$, there is almost surely at most one infinite percolation cluster at every parameter. This is the Burton-Keane theorem. It does not require an assumption about the behavior at the critical probability. If the probability that the origin lies in an infinite percolation cluster is positive, translation ergodicity of Bernoulli percolation also gives almost-sure existence and hence exactly one.

The two structural ingredients are translation invariance and finite-energy property of Bernoulli percolation. For $0<p<1$, every prescribed configuration of finitely many bonds has positive conditional probability given all the other bonds. In particular, opening or closing a fixed finite set of bonds transforms events of positive probability into events of positive probability. The product measure is ergodic under translations. One way to see this is to approximate a translation-invariant event by a finite-cylinder event, translate the cylinder sufficiently far to make its coordinates disjoint, and use independence. Sending the approximation error to zero gives $\mathbb{P}(A)=\mathbb{P}(A{)}^2$.

Let $K$ be the number of infinite percolation clusters. It is translation-invariant, so it is a fixed value in $\{0,1,2,\dots ,\infty \}$ almost surely. First exclude a finite value $k\ge 2$. Some finite box meets at least two infinite percolation clusters with positive probability. Force every internal bond in that box to be open. This joins those clusters and can only merge other clusters; it cannot split an infinite percolation cluster. It also cannot create a new infinite percolation cluster out of finite ones, since only finitely many clusters touch the modified region. Thus the number of infinite percolation clusters decreases. finite-energy property of Bernoulli percolation makes the modified event have positive probability, contradicting its almost-sure value $k$.

Suppose next that $K=\infty$. Some finite box meets three different infinite percolation clusters with positive probability. Each such cluster has an infinite component outside the box: deletion of a finite set in a locally finite graph leaves only finitely many components adjacent to that set, so an infinite percolation cluster cannot have all of them finite. Choose one infinite exterior component from each of the three clusters, and one bond connecting it to the box.

Inside the box, connect the three selected exterior endpoints by a finite tree, preserving just their three selected entrance bonds. Take the minimal subtree connecting these endpoints; they are leaves, since their only retained connection into the box is their chosen entrance bond. This tree has a branch graph vertex of degree three. Close every other internal or boundary bond of the box. Its three exterior components remain distinct outside, since they belonged to different original clusters. The branch graph vertex now has exactly three open incident bonds, and deleting it separates its cluster into three infinite components. Such a graph vertex is a trifurcation vertex in percolation. There are finitely many choices for the endpoints and tree within the chosen region, so at least one fixed finite modification of Bernoulli percolation has positive probability. finite-energy property of Bernoulli percolation consequently gives positive probability of a trifurcation at some fixed graph vertex. Translation invariance makes this probability the same number $q>0$ at every graph vertex.

The decisive fact is that a finite box cannot contain a positive-volume density of these branching points. Here is the boundary count, including its combinatorial justification. For a finite graph vertex set $W$, let ${\partial }^{+}W$ be the exterior graph vertices adjacent to it. In each infinite percolation cluster meeting $W$, contract each of its components outside $W$ that is adjacent to $W$ to a terminal graph vertex. The quotient graph consisting of the cluster's graph vertices in $W$ and these terminals is finite and connected. A trifurcation graph vertex in $W$ separates its terminals into at least three nonempty groups, since each of its infinite branches must leave $W$.

Take a minimal subtree of the quotient graph connecting all the terminals. Every such trifurcation graph vertex must belong to that subtree and have degree at least three: otherwise the terminals in one of its separated groups could not connect to the other groups. All leaves of the minimal subtree are terminals. A cluster with only one terminal has no counted trifurcation. For a finite tree with at least two graph vertices and $L$ leaves,implies that the number of graph vertices of degree at least three is at most $L-2$, and therefore at most its number of terminals. Distinct exterior components can be assigned distinct graph vertices of ${\partial }^{+}W$. Terminals from different clusters are disjoint as well. Summing over clusters proves the trifurcation boundary-counting lemma

Take $W=[-n,n{]}^d\cap {\mathbb{Z}}^d$. The expected left side is $q|W|$, of order $q{n}^d$, while the right side is $O_d(n^{d-1})$. Division by $|W|$ and passage to infinity force $q=0$, contradicting the positive probability obtained by finite modification of Bernoulli percolation. Thus infinitely many infinite percolation clusters are impossible. The surface-to-volume comparison is the geometric reason for uniqueness on the lattice; the same argument is tied to amenability on more general graphs.

At $p=0$ there is no infinite percolation cluster, and at $p=1$ the whole lattice is the unique infinite percolation cluster. This completes all parameter cases. Finally, if the origin's infinite-cluster probability is zero, the countable union over all graph vertices shows there are no infinite percolation clusters almost surely. If it is positive, the translation-invariant existence event has positive probability and hence probability one. Together with uniqueness this distinguishes absence from the case of a single infinite percolation cluster, without making an unsupported assertion that every graph vertex belongs to it.

Use recovery rate one and infection rate $\lambda$ along each directed nearest-neighbour edge. The graphical representation of the contact process places independent rate-one recovery marks at graph vertices and rate-$\lambda$ arrows on directed edges. Infection travels along time-directed paths following arrows and avoiding recovery marks. The same clocks couple all initial configurations and preserve coordinatewise order. Denote its semigroup by $P_t$.

The empty configuration is absorbing, so the lower invariant measure is $\underline{\nu }={\delta }_0$. To construct the upper one, put ${\mu }_t={\delta }_1{P}_t$, where $1$ is the all-infected configuration. Since ${\delta }_1{P}_s{\le }_{\mathrm{st}}{\delta }_1$, order preservation and the semigroup property implyThus these laws decrease in stochastic order. More concretely, use clocks on the entire time axis and start from all infected at time $-t$, looking at the configuration at time zero. These configurations decrease pointwise as $t$ increases: an infection arriving from an earlier start is also obtainable from the all-infected later start. Each coordinate therefore has a limit. Their joint law $\overline{\nu }$ satisfies ${\mu }_t\to \overline{\nu }$ in weak convergence of probability measures on the compact product space.

This limit is invariant. The graphical construction is Feller: for finitely many sites and a bounded time interval, the backward ancestor exploration is almost surely finite, since its size is dominated by a finite-rate branching process. Hence a cylinder function evolved for a fixed time is continuous in the initial configuration, by approximation with finite ancestor sets. Cylinder functions uniformly approximate continuous functions on the product space. We may therefore pass to the limit into get $\overline{\nu }{P}_s=\overline{\nu }$. These are indeed the extremal invariant measures of the contact process: if $\nu$ is any invariant probability law of a Markov process, apply $P_t$ to ${\delta }_0{\le }_{\mathrm{st}}\nu {\le }_{\mathrm{st}}{\delta }_1$ and take limits to obtain $\underline{\nu }{\le }_{\mathrm{st}}\nu {\le }_{\mathrm{st}}\overline{\nu }$.

For the relation with survival, reverse the graphical paths in the interval $[0,t]$, also reversing arrows. The law is unchanged because the rates are symmetric between neighbours. The set of ancestors of a site $x$ has the law of the contact process started from $\{x\}$. ConsequentlyThis is duality of the contact process. The events on the right decrease with time because the empty state is absorbing, and their limiting probability is $\theta (\lambda )$. It follows thatIf $\theta (\lambda )=0$, every coordinate is zero almost surely under $\overline{\nu }$; a countable union over the sites gives $\overline{\nu }={\delta }_0=\underline{\nu }$. Conversely, if the two invariant measures coincide, this one-site marginal is zero, so $\theta (\lambda )=0$. HenceA convention that divides the infection rate by the degree only rescales the parameter; the argument and equivalence are unchanged.

View the oriented square lattice as $(x,n)$ with $x+n$ even, and arrows $(x,n)\to (x\pm 1,n+1)$. Each graph vertex has two incoming bonds. Start with independent oriented bond percolation of parameter $p$, and declare a site open when at least one of its incoming bonds is open. Its probability of being open isIncoming bond sets for different heads are disjoint, so these site indicators are independent: they are precisely an oriented site percolation configuration with parameter $r$.

Every graph vertex after the first on an open oriented bond path is open as a site, because its incoming path bond is open. The root's two incoming bonds belong to earlier time layers and are independent of all bonds used by a forward path from the root. Thus the event that the root site is open, of probability $r$, is independent of bond survival from that root. On their intersection the entire infinite bond path is also an infinite open site path. Hence, writing ${\theta }_b,{\theta }_s$ for the two survival probabilities,This is the incoming-edge coupling of site and bond percolation. If site survival is defined conditional on an open root, the extra factor is omitted; the critical probability is the same. If the model is drawn only in a time half-plane, one can independently sample the root's incoming bonds as auxiliary variables.

For every $p>p_c(\mathrm{bond})$, bond survival is positive by monotonicity and the definition of the critical probability. Therefore $p_c(\mathrm{site})\le 1-(1-p{)}^2$. Let $p$ decrease to the bond critical probability and use continuity of this polynomial, obtainingIf the bond critical probability equals one, the inequality is trivial; no assertion about survival exactly at criticality is used.

The previous part and the permitted assumption $p_c(\mathrm{bond})<1$ imply $p_c(\mathrm{site})<1$. We build an independent oriented site percolation process whose open paths carry contact-process infections, and whose site probability tends to one as $\lambda$ increases.

Use the graphical representation of the contact process with recovery rate one and per-neighbour arrow rate $\lambda$. Fix $\delta >0$. On the parity lattice $(x,n)$ with $n\ge 0$ and $x+n$ even, declare $(x,n)$ good if there is no recovery mark at $x$ during $[(n-1)\delta ,(n+1)\delta ]$, and there is at least one arrow from $x$ to each of $x-1,x+1$ during $[n\delta ,(n+1)\delta ]$. Extend the Poisson clocks to negative times solely to define the root event; the process itself still starts at time zero. Goodness has probability

The independence here is important. At a fixed spatial site $x$, the allowed time indices differ by two. Its two-unit recovery intervals therefore have disjoint interiors, and its outgoing-arrow intervals are disjoint. At different spatial sites, recovery clocks are different and outgoing arrows have different tails, hence use different directed-edge clocks. Every defining random input belongs to just one parity site's event, up to deterministic interval endpoints at which a Poisson mark has probability zero. Thus the good-site indicators really are independent, with common probability $q$; no theorem about dependent percolation is needed.

Suppose $(x,n)$ and $(x\pm 1,n+1)$ are both good and $x$ is infected at time $n\delta$. The source has no recovery before $(n+1)\delta$, and it sends an arrow to the chosen neighbour during that interval. The target's good event excludes recovery throughout $[n\delta ,(n+2)\delta ]$, so the target is infected at time $(n+1)\delta$. Induction shows that any infinite oriented path of good sites starting at $(0,0)$ sustains infection at every time layer. Along each transmitting interval there is always an infected site, so the contact process never reaches its empty absorbing state.

Take $\delta ={\lambda }^{-1/2}$. ThenFor some finite $\lambda$ it exceeds $p_c(\mathrm{site})$, and the good-site process has positive survival probability. The contact process begun from the origin therefore also survives with positive probability. HenceThis is the independent oriented-percolation comparison for the contact process. If the infection convention assigns total rate $\lambda$ rather than rate $\lambda$ to each of the two neighbours, replace the arrow rate by $\lambda /2$; the same limit proves the same finiteness conclusion.

For finite $A\subset \mathbb{Z}$, define the occupation-product functionwith empty product one. Use the stirring representation of symmetric exclusion on the time interval $[0,t]$. Trace the labels at the sites of $A$ backwards to time zero, and call their set of ancestors $B_t$. Labels remain distinct under swaps, so $|B_t|=|A|$. Pathwise,Reverse time in the Poisson clocks. Their joint law is unchanged, and each interchange is its own inverse. Thus the backward set $B_t$ has the same law as the finite-particle symmetric exclusion set $A_t$ started from $A$. Taking expectations gives the product self-duality of symmetric exclusionThe argument holds for every deterministic initial configuration $\eta$ and every finite set $A$, including the empty set, and makes no stationarity assumption.