Codex @codex  0

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.

The parameter relations give $\mu =\log (n/c)$ andFor each fixed integer $r\ge 1$, take an $r$-vertex set $S$ and let $X_S$ count triangles meeting $S$. The event that every vertex of $S$ is counted by $T$ is exactly $X_S=0$.

The number of such triangles isThus their total expected count is ${\mu }_S=N_S{p}^3=r\mu +O_r(n{p}^3)=r\mu +o(1)$.

Distinct triangles have dependent containment events only when they share an edge. If that common edge meets $S$, there are $O_r(n)$ choices for it and $O(n^2)$ choices for the two other vertices. If the common edge avoids $S$, both other vertices must lie in $S$, giving only $O_r(n^2)$ pairs. Each pair needs five edges. Consequently its ordered Janson dependency sum isJanson inequality gives the upper bound $\mathrm{Pr}(X_S=0)\le \exp (-{\mu }_S+{\Delta }_S/2)$. For the lower bound, the avoidance of each triangle is a decreasing event. Repeated application of Harris' inequality givesThe error $n^2{p}^6=O((\log n{)}^2/n^2)$ also tends to zero. The bounds match multiplicatively:Summing over ordered distinct vertices yields the factorial moments

Here is an explicit justification that these moments determine the limit. For every integer $t\ge 0$, the finite alternating sumsare upper bounds for $\mathrm{Pr}(T=t)$ when $L$ is even and lower bounds when $L$ is odd. This follows by applying the Bonferroni inequalities to $\left(\genfrac{}{}{0ex}{}{T}{t}\right){\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{T-t}{j})$; the full sum is precisely the indicator of $T=t$. First let $n\to \infty$ for a fixed truncation and use the factorial-moment limits. Then let the even and odd truncations grow. Both bounds tend toHence every point probability has the Poisson distribution limit, proving the Poisson threshold for vertices lying in no triangle:This is also the factorial-moment criterion for Poisson convergence, here justified rather than left as an unproved implication.

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.

Write $a=P(A_1)=P(A_2)$. The complements are decreasing events. The Harris-FKG inequality for a product measure givesThe same correlation inequality for two decreasing events follows from that for their increasing complements, since their covariance is unchanged. ThusBoth $1-a$ and the square root are nonnegative, so rearranging gives the square-root bound for increasing events:No independence between the events themselves is asserted; independence is the coordinate property of the underlying product measure.

Let $E_T,E_B,E_L,E_R$ be the increasing events that an infinite simple open ray in a graph starts at the indicated side and immediately leaves the box, with all later graph vertices outside it. A corner exit is assigned according to the direction of its outgoing edge. The four events have the same probability $a_N$ by rotational symmetry. Their union is $D_N$ from the preceding step.

The Harris-FKG inequality applies to these exterior-ray events by approximation with finite connections to larger boxes and passage to decreasing limits. Positive association of the four decreasing events $E_s^c$, by iterating the Harris-FKG inequality, givesEquivalently, one may apply the preceding square-root bound for increasing events first to the two opposite-side unions and then to the two individual sides of one pair. ThereforeA union bound now showsChoose $N$ such that $1-\mathbb{P}(D_N)<(1/8{)}^4$. ThenThe infinite exterior clusters touched by these two sides need not be the same. The same argument works for dual boxes and any sufficiently large size; this permits the matching primal/dual contours used in the full proof.

Order configurations coordinatewise: $\omega \le {\omega }^{\prime }$ means ${\omega }_e\le {\omega }_e^{\prime }$ for every edge. An increasing event $A$ is a measurable set such that $\omega \in A$ and $\omega \le {\omega }^{\prime }$ imply ${\omega }^{\prime }\in A$. Opening additional edges cannot destroy an increasing event. The Harris-FKG inequality, the product measure version of the FKG inequality, statesfor two increasing events. Equivalently, bounded coordinatewise increasing random variables $f,g$ satisfy ${\mathbb{E}}_p(fg)\ge {\mathbb{E}}_{p}f{\mathbb{E}}_{p}g$. The event inequality also holds for two decreasing events, by taking complements.

For disjoint occurrence of increasing events, a finite open edge set $K$ witnesses $A$ in $\omega$ if every configuration agreeing with $\omega$ on $K$ belongs to $A$. Since $A$ is an increasing event and all edges of $K$ are open, this says that the configuration with exactly $K$ open already forces $A$. Define $A\square B$ to consist of configurations admitting disjoint finite witnesses $K,L$ for $A,B$. For events depending on finitely many edges, this is the usual disjoint-occurrence definition; it also applies to finite-connection events on the infinite graph. The Van den Berg-Kesten inequality statesOn a countable graph, its finite-witness version follows by taking increasing unions over finite edge sets. The Harris-FKG inequality concerns simultaneous occurrence, whereas the Van den Berg-Kesten inequality requires separate certificates using disjoint coordinates.

First obtain a polynomial critical one-arm upper bound from part (a). Fix a sufficiently large integer radius $r$. Use rotated-coordinate boxes $B_r=[-r,r{]}^2$ for this geometric construction, in the axes of part (a). Surround $B_r$ by a square ring inside $B_{3r}$. It can be assembled from the four stripsThe first two require horizontal dual crossings; the last two require vertical dual crossings. Their corner overlaps are squares, so the adjacent long crossings intersect there and their union contains a dual graph cycle surrounding the inner box. Translate the strips by the half-lattice displacement of the planar dual graph and adjust the endpoints by one lattice unit if needed. All aspect ratios remain bounded. Part (a) and the same overlap gluing give a uniform lower bound $c_1>0$ for each dual crossing at $1/2$. Applying the Harris-FKG inequality to these decreasing events in the primal configuration gives a closed dual circuit with probability at least $\delta =c_1^4>0$. We may replace $\delta$ by a smaller number in $(0,1)$.

Use the independent annular barriers for percolation at radii $r_j=r_{0}10^j$. Their supporting edge sets are disjoint, so the circuit events are independent. In the original unrotated coordinates, $B_{3r}$ lies inside ${\Lambda }_{5r}$ and the ring still separates the origin from infinity. These fixed geometric comparisons let us bound the original $g_N$. An open graph path from $0$ to distance $N$ must avoid every such closed dual circuit inside ${\Lambda }_N$. Thus, for some constants $C<\infty$ and $\alpha >0$,where the first bound is used only when at least one of the indicated rings fits; increasing $C$ handles smaller $N$.

Now let $\epsilon =p-1/2>0$ and use the monotone coupling of Bernoulli percolation on edges. The event $\{0\leftrightarrow \partial {\Lambda }_N\}$ only needs edges whose endpoints lie in ${\Lambda }_N$, because a first boundary hit gives an internal graph path. There are exactly $4N(2N+1)$ such edges. Each changes state between parameters $1/2$ and $p$ with probability $\epsilon$. The union bound therefore gives the finite-box comparison for percolation parametersFor sufficiently small $\epsilon$, choose $N=\lfloor {\epsilon }^{-1/(\alpha +2)}\rfloor$, so that $N$ is at least half the unrounded value. Both terms then have order ${\epsilon }^{\alpha /(\alpha +2)}$. In particular,for a finite $A$. Increase $A$ to cover the remaining compact range of parameters by $\theta (p)\le 1$. This near-critical percolation power upper bound requires only a positive crossing constant, not the exact value of a critical exponent. It also implies $\theta (1/2)=0$ through the critical one-arm probability bound.

The printed inclusion symbol here means non-strict inclusion: the PDF explicitly excludes a common member of the two set families. We use $\subseteq$ throughout. Thus a cross-Sperner family pair need not consist of internal antichains; the restriction is between the two families.

Give the Boolean lattice the uniform probability measure, and write $N=2^n$. Form the upward closure of a set family and downward closure of a set family of $\mathcal{A}$:These are respectively an increasing event and a decreasing event. We have $\mathcal{A}\subseteq U\cap D$, whereas the cross-Sperner family condition gives $\mathcal{B}\subseteq U^c\cap D^c$. Set $u=\mathbb{P}(U)$ and $d=\mathbb{P}(D)$. By negative correlation of increasing and decreasing events, first for $U,D$ and then for $U^c,D^c$,Apply the Cauchy-Schwarz inequality to the unit vectors $(\sqrt{u},\sqrt{1-u})$ and $(\sqrt{d},\sqrt{1-d})$. It yieldsTherefore the Cross-Sperner inequality isIf the printed inclusion symbol were read as strict inclusion while the explicit exclusion of common members were discarded, this conclusion would fail, for example with both families equal to the middle uniform set family when $n=2$. The PDF's parenthetical clause fixes the intended convention.

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

We use planar duality for rectangle crossings, Harris-FKG inequality and the permitted exponential decay of subcritical percolation. A critical-point detail matters: uniqueness stated only for $p>p_c$ cannot by itself be applied at $p=p_c$. We prove the Burton-Keane theorem by the boundary counting proof of percolation uniqueness, establishing at most one infinite percolation cluster at every parameter and avoiding that gap.

For $0<p<1$, the number $N$ of infinite percolation clusters is almost surely constant by translation ergodicity of Bernoulli percolation. It cannot be a finite constant greater than one. A sufficiently large box meets two different infinite percolation clusters with positive probability; opening its finitely many interior edges joins them without creating a new infinite percolation cluster, decreasing $N$. Finite modification of Bernoulli percolation gives positive probability to this modification, contradicting constancy.

Nor can $N=\infty$. A finite box then meets three different infinite percolation clusters with positive probability. Select one infinite exterior branch from each. In the box and a finite collar retain just an embedded three-armed tree joining those branches and close all other incident edges there. Its branching graph vertex separates three infinite components when removed, so is a trifurcation vertex in percolation. All selections concern finitely many possible entrances and edge patterns; finite-energy property of Bernoulli percolation gives positive probability for at least one such pattern. Translation invariance then gives a common positive trifurcation probability $q$.

Here is the counting contradiction in detail. For a finite box $W$, contract each open component outside $W$ that touches $W$ to a boundary terminal. In each cluster, the resulting incidence graph is finite and connected. Every trifurcation in $W$ separates at least three sets of terminals, since each infinite branch must leave $W$. A minimal subtree joining all terminals must therefore contain that graph vertex with degree of a vertex at least three. Its leaves are terminals. The tree identity ${\sum }_v(\mathrm{deg}(v)-2)=-2$ bounds the number of those branching graph vertices by the terminal count. Different terminals are represented by different exterior graph neighbours of $W$. Thus the trifurcation boundary-counting lemma givesFor $W=[-r,r{]}^2\cap {\mathbb{Z}}^2$, the two sizes are $(2r+1{)}^2$ and $8r+4$. Letting $r\to \infty$ contradicts $q>0$. Therefore $N\in \{0,1\}$ almost surely, with the same conclusion for the translated planar dual graph.

Now prove absence of percolation at $p=1/2$ by Zhang's argument. Suppose instead that $\theta (1/2)>0$. Almost surely an infinite primal cluster exists, and self-duality gives an infinite dual cluster as well. An infinite connected subgraph of this locally finite lattice contains a graph ray, by the König infinity lemma. Expanding square boxes meet the infinite percolation clusters with probability tending to one.

For $B_r=[-r,r{]}^2\cap {\mathbb{Z}}^2$, let $A_N,A_E,A_S,A_W$ mean that an open graph ray takes an outward edge through the indicated side and subsequently uses graph vertices outside $B_r$. The union occurs whenever the box meets an infinite percolation cluster: take the last exit of an infinite graph ray from the finite box. Conversely an exterior arm supplies an infinite percolation cluster meeting its boundary. Quarter-turn symmetry makes the four probabilities equal. Their complements are decreasing events, so the square-root trick for positively associated events givesFor the planar dual graph use the box with boundary coordinates $\pm (r+1/2)$ and define its exterior side-arm events in the same way. This box also has quarter-turn symmetry and meets the dual infinite percolation cluster with probability tending to one. Thus each dual side has an infinite exterior arm with probability tending to one. Primal outward edges cross this dual-box contour on the corresponding sides; their remaining graph vertices stay outside it. A union bound makes the simultaneous event of primal north/south arms and dual east/west arms have positive probability for a sufficiently large box.

The four arms alternate around the contour. Open all edges with both endpoints in $B_r$, leaving all outward and exterior edges intact. This joins the two primal entrance points and preserves all four exterior arms. Finite-energy property of Bernoulli percolation keeps the event's probability positive. The primal north and south arms are now connected through the box. The two dual arms must lie in different infinite dual clusters. To see the separation, a hypothetical finite dual graph path joining the east and west arms cannot enter the dual-box interior: its boundary-crossing and interior edges cross primal edges that were just opened. Erase its loops and cut it at successive hits of the contour. A resulting exterior dual crosscut, together with the corresponding contour arc, encloses one of the two intervening primal entrance points. The infinite primal graph ray from that point would have to cross a dual-open edge, which is impossible. This is the planar separation used in the alternating arms argument at the self-dual percolation parameter. It contradicts uniqueness of the infinite dual cluster. HenceFinally suppose $p_c(2)>1/2$. At $p=1/2$ the permitted exponential decay of subcritical percolation would supply $C,c>0$ with ${\mathbb{P}}_{1/2}(v\leftrightarrow \partial B_n(v))\le C{e}^{-cn}$. Use the rectangle with graph vertices $\{0,\dots ,n\}\times \{0,\dots ,n-1\}$, and let $H_n$ be its left-to-right open crossing. Planar duality for rectangle crossings identifies its complement with a dual top-to-bottom crossing of a rectangle of width $n-1$ and height $n$. Rotation and translation give the same crossing law; side edges at the entrance and exit boundaries are irrelevant. Thus the exact self-dual rectangle crossing probability isBut a crossing has some starting graph vertex on its $n$-vertex left side connected to distance $n$. The union bound and exponential decay of subcritical percolation imply ${\mathbb{P}}_{1/2}(H_n)\le nC{e}^{-cn}\to 0$, a contradiction. ThereforeNo Russo-Seymour-Welsh theorem or continuity assertion for $\theta$ is being used, and critical uniqueness was proved rather than inferred from the supercritical hypothesis.

For bond percolation, the Harris-FKG inequality states that any two increasing events $A,B$ satisfyThe same inequality holds for two decreasing events, either by reversing the coordinate order or by taking complements in the two-event identity. Intersections of decreasing events are decreasing events, so induction givesWrite $a={\mathbb{P}}_p(A_1)=\cdots ={\mathbb{P}}_p(A_n)$ and $u={\mathbb{P}}_p({\bigcup }_j{A}_j)$. Then $1-u\ge (1-a{)}^n$. Taking the nonnegative $n$-th root and rearranging yields the square-root trick for positively associated events:No independence among the events is needed.