Codex @codex  0

The multiplicative factor $q$ assigned to each connected component of a graph in a finite random-cluster measure. At fixed edge probability, the weight of a configuration with $k$ components includes $q^k$. For $q=1$ this reduces to independent bond percolation; increasing $q$ at fixed $p$, for $q\ge 1$, suppresses increasing events by random-cluster weight monotonicity.

For increasing events $A,B$ under a finite Bernoulli distribution product measure, first assume all parameters are at most $1/2$. Write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for last-coordinate sections. The zero-section of their disjoint occurrence of increasing events is $A_0\square B_0$; its one-section is $(A_1\square B_0)\cup (A_0\square B_1)$. The intersection in this union contains $A_0\square B_0$. If $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$ and the last parameter is $p\le 1/2$, mathematical induction bounds disjoint occurrence by $(1-2p)a_0{b}_0+p{a}_1{b}_0+p{a}_0{b}_1$. The product of the two marginal probabilities exceeds this bound by $p^2(a_1-a_0)(b_1-b_0)\ge 0$. For a larger parameter $p_i<1$, replace that coordinate by the logical disjunction of $m_i$ independent bits with parameter $1-(1-p_i{)}^{1/m_i}\le 1/2$. Disjoint original witnesses lift to disjoint bit witnesses. Apply the small-parameter inequality and then pass to degenerate parameters by continuity.

An event is decreasing when closing additional edges cannot destroy it. Its complement is an increasing event.

A finite open coordinate set witnesses an increasing event when prescribing those coordinates open forces the event, regardless of the remaining configuration. The disjoint occurrence of increasing events $A\square B$ means that $A$ and $B$ have disjoint finite witnesses. For finite-coordinate events this is the usual disjoint-occurrence definition. The Van den Berg-Kesten inequality bounds its probability by $\mathbb{P}(A)\mathbb{P}(B)$ under an independent Bernoulli distribution product measure.

If an increasing event $A$ depends on $m$ sites or edges, the uniform-label monotone coupling of Bernoulli percolation and the union bound give $0\le {\mathbb{P}}_q(A)-{\mathbb{P}}_p(A)\le m(q-p)$ for $p\le q$. A change of the event requires a coordinate with label in $(p,q]$. For bond percolation from the origin to the boundary of $[-n,n{]}^2$, first-hit graph paths use the $4n(2n+1)$ internal edges, so the same count bounds the parameter sensitivity.

On a finite distributive configuration lattice, probability weights satisfying ${\mu }_1(\omega \vee \eta ){\mu }_2(\omega \wedge \eta )\ge {\mu }_1(\omega ){\mu }_2(\eta )$ for all pairs give stochastic domination ${\mu }_1\ge {\mu }_2$. The result holds for nonnegative weights as well: apply the four functions theorem to ${\mu }_1{1}_{A^c},{\mu }_2{1}_A,{\mu }_1{1}_A,{\mu }_2{1}_{A^c}$ for an increasing event $A$, obtaining ${\mu }_1(A^c){\mu }_2(A)\le {\mu }_1(A){\mu }_2(A^c)$.

A real-valued function on a partially ordered set is increasing when it preserves its order. Indicators of increasing events are examples. In spin or edge configuration spaces the order is coordinatewise, so increasing observables grow when a zero coordinate is replaced by one. Positive association of random variables concerns pairs of such observables, and stochastic domination compares their expectations.

Assign each edge $e$ an independent uniform distribution label $U_e$ on $[0,1]$. At parameter $p$, declare $e$ open exactly when $U_e\le p$. Each open/closed decision then has the required Bernoulli distribution, and different edge decisions are independent. The same construction applies to site percolation with labels on vertices.

Keep those labels fixed when increasing $p$. For $p\le q$, every $p$-open edge is also $q$-open, so every $p$-open graph path survives and each percolation cluster can only gain vertices. This coupling of probability distributions compares complete configurations on one probability space, rather than comparing two unrelated pictures. Any increasing event, such as an open path between specified vertices, consequently has a nondecreasing probability.

The three panels use one seeded collection of labels on a finite $17\times 17$ square lattice box. Colored edges and dots show the central root's percolation cluster; gray edges are open but disconnected from it. A percolation cluster can grow by many vertices when one newly opened edge joins it to another large percolation cluster. The panels illustrate a nested construction, not an estimate of $\theta (p)$ or a proof of the Harris-Kesten theorem.

Under a product measure on a finite Boolean lattice, an increasing event $E$ and a decreasing event $G$ obey the displayed inequality. The complement $G^c$ is an increasing event, so Harris' inequality gives $\mathbb{P}(E\cap G^c)\ge \mathbb{P}(E)\mathbb{P}(G^c)$. Subtract from $\mathbb{P}(E)$ to obtain the result. This implication includes degenerate Bernoulli distribution parameters $0$ and $1$.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

In bond percolation on the square lattice, every nearest-neighbour edge independently has state one, meaning open, with probability $p$, and state zero, meaning closed, with probability $1-p$. Thus the configuration law is the product measure ${\mathbb{P}}_p={⨂}_{e\in E}\mathrm{Bernoulli}(p)$. An open path in bond percolation uses only open edges. An increasing event $A$ satisfies $\omega \in A,{\omega }^{\prime }\ge \omega \Rightarrow {\omega }^{\prime }\in A$: opening further edges cannot destroy the event.

The Harris-FKG inequality for two increasing events isFor disjoint occurrence of increasing events, write $A\square B$ when disjoint sets of open edges separately witness $A$ and $B$, so each event is forced by its own witness regardless of the other edges. The Van den Berg-Kesten inequality statesFor events given by cylinder sets these are finite-coordinate assertions. Connection events have finite open-path witnesses; truncating to finite boxes and taking increasing limits gives the same disjoint-occurrence bound for them. Sharing a vertex between the two witness paths is permitted; sharing an edge is not.

For $1\le m<n$, take a simple open path from the origin to the radius-$n$ boundary and let $x$ be its first vertex on the radius-$m$ boundary. Its initial segment witnesses $0\leftrightarrow x$. If $z$ is its final vertex, then $\Vert z-x{\Vert }_{\infty }\ge n-m$. Consequently the remaining segment reaches $x+\partial {\Lambda }_{n-m}$, and its initial portion until that visit witnesses $x\leftrightarrow x+\partial {\Lambda }_{n-m}$. The two segments use disjoint edges. HenceThe union bound, Van den Berg-Kesten inequality and translation invariance of the product measure now give the weighted BK boundary-splitting estimateFor $m=n$ the same bound follows directly from the union bound, with $g_0=1$. With the conventional $\partial {\Lambda }_0=\{0\}$, $m=0$ gives equality.

Write $C(0)$ for the percolation cluster of the origin. By summing its membership indicators, the percolation susceptibility isIf it is finite, then $a_m\to 0$. For $0<p<1$, choose $m$ with $0<a_m=a<1$. Iterating the boundary-splitting estimate with this fixed $m$ givesFor $k\ge 2m$, $\lfloor k/m\rfloor \ge k/(2m)$, so $g_k\le \exp [-(-\log a)k/(2m)]$. To handle all smaller positive radii without an unspecified prefactor, observe that $g_k\le g_1=1-(1-p{)}^4<1$. ThereforeFor $1\le k<2m$, the second chosen rate gives $e^{-\gamma k}\ge g_1$, and for larger $k$ the first rate applies. At $k=0$ both sides equal one. The endpoint $p=0$ has $g_k=0$ for every $k\ge 1$, so any positive rate works; $p=1$ is excluded by finite susceptibility. This proves exponential one-arm decay from finite susceptibility with the required unit prefactor.

Order configurations coordinatewise: $\omega \le \eta$ when $\omega (e)\le \eta (e)$ for every coordinate. An increasing event $A$ is an upward-closed set: $\omega \in A$ and $\omega \le \eta$ imply $\eta \in A$.

The finite-lattice FKG inequality states that a probability mass function satisfying the FKG lattice conditionis positively associated. Here meet in a lattice and join in a lattice are coordinatewise minimum and maximum. Thus for increasing observables $f,g$,Taking indicator functions gives $\mu (A\cap B)\ge \mu (A)\mu (B)$ for all increasing events. The strictly positive version suffices for the Ising weights here; the theorem also holds for nonnegative log-supermodular weights of positive total mass.

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.

We first derive the reflected attachment estimate for percolation. Put $R=[0,m]\times [0,2n]$, $m\ge n$, and $S=[0,n{]}^2$. Let $X(R)$ require an open vertical crossing of $S$ together with an open path in $R$ attaching it to the right side of $R$. ThenTo prove this, explore the leftmost vertical open crossing $P$ of $S$, revealing bonds on $P$ and to its left, but none strictly to its right. One can implement this exploration by following the boundary of the set accessible from the left using closed dual bonds; its right boundary is the extremal open crossing when that crossing exists. Thus fixing its outcome leaves right-side bonds in their original independent distribution.

For each possible explored $P$, reflect its geometry in $y=n$ and join it to its reflection to obtain a bottom-to-top separator $L$ of $R$. This reflected portion is only a geometrical separator and is not presumed open. Let $Y_{-}$ and $Y_{+}$ mean that an open path from the right boundary reaches, respectively, the lower or upper half of $L$, staying to its right until its endpoint. Any horizontal open crossing of $R$, followed from right to left until its first meeting with $L$, witnesses at least one of these events. Reflection in $y=n$ swaps $Y_{-}$ and $Y_{+}$ and preserves the independent measure. HenceThe bonds tested by $Y_{-}$ remain unexposed after specifying $P$; conditional on that exploration its probability is still the unconditional one for this deterministic separator. Its occurrence attaches the genuinely open lower crossing $P$ to the right side. Average over $P$ to obtain the attachment estimate.

Now take $R=[0,2n]\times [0,2n]$ and $R^{\prime }=[-n,n]\times [0,2n]$, with common corner square $S=[0,n{]}^2$. Use $X(R)$, its horizontal reflection in $R^{\prime }$, and a horizontal open crossing of $S$. The last crossing meets the vertical crossings of $S$ in both attachment events, so these three events give a horizontal crossing of $R\cup R^{\prime }$. All three events are increasing events, so the Harris lemma gives

For all aspect ratios, glue a width-$m_1$, height-$2s$ rectangle to a width-$m_2$, height-$2s$ rectangle with an overlap square of side $2s$. Their horizontal crossings and an overlap vertical crossing imply a crossing of their union. Again the Harris lemma givesAdding a $3s$-wide rectangle therefore yieldsFor height $n\ge 2$, let $s=\lfloor n/2\rfloor$, so $2s\le n$ and $s\ge n/3$. Choose an integer $k\ge \max (3,3\lambda )$. For $m\le \lambda n$, we have $m\le ks$; restricting to height $2s$ and extracting a shorter horizontal crossing givesFor $n=1$, the horizontal bottom-row path gives $h_{1/2}(m,1)\ge 2^{-\lceil \lambda \rceil }$ whenever the allowed integer $m\ge 1$ exists. Thus one may take $c_{\lambda }=\min (2^{17-8k},2^{-\lceil \lambda \rceil })>0$. This proves the requested uniform rectangle crossing in bond percolation bound, rather than assuming the Russo-Seymour-Welsh theorem.

The Harris lemma says that, in any finite product of independent Bernoulli coordinates, two increasing events satisfyThe coordinates need not have the same parameter. For completeness, the same statement for increasing functions follows by induction on the number of coordinates. Conditional on the last bit, induction makes the conditional covariance nonnegative; the covariance of the two conditional means is $p(1-p)(a_1-a_0)(b_1-b_0)\ge 0$. The covariance decomposition proves the induction step. Complementing both events gives the inequality for decreasing events too. Finite-cylinder approximation extends it to the countable product setting when needed.

For increasing events $A_1,\dots ,A_r$ of a common probability $a$, their decreasing complements giveTherefore the nth root trick isThis is a lower bound for an individual success probability when a symmetric union is very likely. Without equality of the individual probabilities, the conclusion applies to their maximum. Independence among the $A_j$ is not required.