Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation)

Statement

Let $\Omega = \prod_{i=1}^n \Omega_i$ be a finite product space (e.g. $\Omega_i=\{0,1\}$, one coordinate per potential edge of $K_n$, giving $\Omega=\{0,1\}^{\binom n2}$, the edge-set space of $G(n,p)$), equipped with a product probability measure $\mu = \prod_i \mu_i$ (e.g. each coordinate independently $1$ with probability $p$). Partially order $\Omega$ coordinatewise. A function $f:\Omega\to\mathbb R$ is increasing if $\omega\le\omega'$ implies $f(\omega)\le f(\omega')$ (decreasing if the reverse); an event $A\subseteq\Omega$ is increasing/decreasing if its indicator $\mathbb 1_A$ is.

Harris's inequality (product-measure case): for any two increasing events $A,B$ (or any two decreasing events), $$\mathbb P(A\cap B) \;\ge\; \mathbb P(A)\,\mathbb P(B).$$ Equivalently, for increasing $f,g:\Omega\to\mathbb R$ with $\mathbb E f^2,\mathbb E g^2<\infty$: $\mathrm{Cov}(f,g)=\mathbb E[fg]-\mathbb E[f]\mathbb E[g]\ge 0$. If instead $A$ is increasing and $B$ decreasing (or $f$ increasing, $g$ decreasing), the inequality reverses: $\mathbb P(A\cap B)\le \mathbb P(A)\mathbb P(B)$, i.e. negative correlation. (Wikipedia, en.wikipedia.org/wiki/FKG_inequality; Yufei Zhao, yufeizhao.com/pm/7.pdf, Lecture 7.)

FKG inequality (Fortuin–Kasteleyn–Ginibre, 1971 — the general lattice version, of which Harris's product-measure statement is the special case where the lattice is a product of chains): let $L$ be a finite distributive lattice and $\mu:L\to\mathbb R_{\ge0}$ satisfy the lattice condition (log-supermodularity) $$\mu(x\wedge y)\,\mu(x\vee y) \;\ge\; \mu(x)\,\mu(y)\qquad\text{for all }x,y\in L.$$ Then for all increasing $f,g:L\to\mathbb R$, $$\Big(\sum_{x} f(x)g(x)\mu(x)\Big)\Big(\sum_x \mu(x)\Big) \;\ge\; \Big(\sum_x f(x)\mu(x)\Big)\Big(\sum_x g(x)\mu(x)\Big),$$ i.e. $\mathbb E_\mu[fg]\ge \mathbb E_\mu[f]\,\mathbb E_\mu[g]$ under the probability measure $\mu/\sum\mu$. A product measure on $\{0,1\}^n$ trivially satisfies the lattice condition with equality on each coordinate, recovering Harris's statement as the special case. (Fortuin–Kasteleyn–Ginibre, "Correlation inequalities on some partially ordered sets," *Comm. Math. Phys.* 22 (1971) 89–103; Wikipedia summary confirms lattice-condition statement.)

Corollary (square-root trick): if $A_1,\dots,A_k$ are increasing events, each with $\mathbb P(A_i)$ possibly different, then applying the "both-decreasing" case of the inequality to the complements $A_i^c$ (also monotone: decreasing) gives $\mathbb P\big(\bigcap_i A_i^c\big)\ge \prod_i \mathbb P(A_i^c)$, hence $$\mathbb P\Big(\bigcup_i A_i\Big) \;\le\; 1-\prod_i\big(1-\mathbb P(A_i)\big).$$ When the $A_i$ are symmetric copies of the same event (e.g. by a vertex/edge symmetry of $G(n,p)$) with common probability $q=\mathbb P(A_1)$ and $\mathbb P(\bigcup A_i)=\alpha$ is known, this rearranges to $q\ge 1-(1-\alpha)^{1/k}$ — turning a union bound into a single-event lower bound without needing independence. (Standard corollary of the FKG inequality, cross-checked via multiple secondary expositions, e.g. eventuallyalmosteverywhere.wordpress.com tag page and MIT 18.226 course material.)

Facts

- Origin: T.E. Harris, "A lower bound for the critical probability in a certain percolation process," *Proc. Cambridge Philos. Soc.* 56 (1960) 13–20, DOI 10.1017/S0305004100034241 — proved for i.i.d. Bernoulli site-percolation on $\mathbb Z^2$ to show two increasing events (existence of a left–right and of a top–bottom open crossing of a rectangle) are positively correlated, en route to a lower bound $p_c(\mathbb Z^2)\ge 1/2$ (later shown sharp: $p_c=1/2$, Kesten 1980). (ui.adsabs.harvard.edu/abs/1960PCPS...56...13H.) - Generalization: C.M. Fortuin, P.W. Kasteleyn, J. Ginibre, "Correlation inequalities on some partially ordered sets," *Comm. Math. Phys.* 22 (1971) 89–103 — extended Harris's product-measure result to arbitrary measures on finite distributive lattices satisfying the log-supermodular lattice condition; motivated by and applied to the Ising model (arbitrary external field) and the random-cluster (Fortuin–Kasteleyn) model of statistical mechanics. (link.springer.com/article/10.1007/BF01651330.) - Further generalization: R. Holley, "Remarks on the FKG inequalities," *Comm. Math. Phys.* 36 (1974) 227–231 — the Holley inequality: if two measures $\mu_1,\mu_2$ on a distributive lattice satisfy $\mu_1(x\vee y)\mu_2(x\wedge y)\ge \mu_1(x)\mu_2(y)$ for all $x,y$, then $\mu_1$ stochastically dominates $\mu_2$ on increasing sets; the FKG inequality follows by taking $\mu_1=\mu_2$. Holley's proof introduces a coupling/monotone-Markov-chain argument that is itself a reusable technique. (Wikipedia, en.wikipedia.org/wiki/FKG_inequality, attribution.) - Boolean-lattice special case, independently found: D. Kleitman (1966) proved the $\{0,1\}^n$-with-uniform-measure case (any two "up-sets"/monotone increasing families of subsets of $[n]$ are positively correlated under the uniform measure) — this special case is sometimes called the Harris–Kleitman inequality in combinatorics texts, distinct from but implied by the general FKG statement. - "When it applies" boundary: the lattice condition can fail for non-product measures that are not log-supermodular, in which case increasing events need not be positively correlated — the hypothesis is doing real work, not a technicality. Conditioning on a *fixed number* of successes (e.g. $G(n,m)$, the uniform random graph with exactly $m$ edges, rather than $G(n,p)$) is a classic case where naive product-measure Harris does not directly apply because the coordinates are no longer independent; a version still holds in many such "exchangeable" settings via the general FKG lattice-condition machinery, but this must be checked, not assumed. - Confirmed live use in this wiki's Erdős-problem corpus: Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? (open, Erdős–Gimbel \$1000 problem, whether $\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ a.s.) and Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) (disproved by Steiner) — both resolved/attacked in R. Steiner, "On the difference between the chromatic and cochromatic number," arXiv:2408.02400 (2024), and A. Heckel, "On a question of Erdős and Gimbel on the cochromatic number," arXiv:2408.13839, *Electron. J. Combin.* 31:P4.72 (2024), by the trick: $\zeta(\bar G)=\zeta(G)$ (cochromatic number is complement-invariant) but $\chi(G)$ and $\chi(\bar G)$ are chromatic numbers of *oppositely monotone* copies of the same $G(n,1/2)$ distribution (edge set and its complement), so the Harris/FKG inequality directly controls how far apart $\chi(G)$ and $\chi(\bar G)$ (equivalently $\chi-\zeta$ for $G$ vs. $\bar G$) can be forced to be — a concrete 2024 instance of the inequality driving a genuinely new Erdős-problem result, not just textbook percolation.

Technique

When it applies: any question of the form "are two monotone (up-closed / down-closed) properties of a random product structure — random graph $G(n,p)$, random hypergraph, i.i.d. percolation configuration, product of independent coin flips generally — positively or negatively correlated," *without* needing to compute or estimate the joint probability directly. Typical monotone-event examples on $G(n,p)$: "contains a Hamilton cycle," "contains a fixed subgraph $H$," "is connected," "has $\chi(G)\ge k$," "min degree $\ge d$" are all increasing; "is planar," "is $k$-colorable," "is triangle-free," "has an isolated vertex" are decreasing. The tool needs (a) a product/independent-coordinate structure (or more generally a distributive-lattice-structured probability space satisfying the log-supermodular lattice condition) and (b) both events monotone in the *same* direction (for positive correlation) or *opposite* directions (for negative correlation) with respect to a common partial order.

Why it works (the mechanism): in the product-measure (Harris) case the clean proof is induction on the number of coordinates $n$. Base case $n=1$: increasing $f,g$ on a totally ordered one-coordinate space satisfy $\mathbb E[fg]\ge \mathbb E[f]\mathbb E[g]$ by the elementary rearrangement/Chebyshev sum inequality (two increasing sequences are "sorted the same way," so pairing them up correlates positively — this is literally Chebyshev's sum inequality in probabilistic dress). Inductive step: condition on the last coordinate $\omega_n$; the conditional expectations $F(\omega_n):=\mathbb E[f\mid \omega_n]$ and $G(\omega_n):=\mathbb E[g\mid\omega_n]$ are each increasing functions of $\omega_n$ (since $f,g$ are increasing in *all* coordinates including the ones being averaged out, by the induction hypothesis applied to the remaining $n-1$ coordinates), so the $n=1$ case applies again to $F,G$ over the single remaining coordinate $\omega_n$, closing the induction. (Yufei Zhao, yufeizhao.com/pm/7.pdf, Lecture 7 — proof sketch confirmed at this level of detail; this is also the proof given in Grimmett's *Percolation* textbook and Alon–Spencer's *The Probabilistic Method*, standard references not independently re-fetched here.) The general distributive-lattice (FKG) version does not reduce as directly to a coordinatewise induction and instead uses either the original FKG combinatorial argument or Holley's coupling/Markov-chain proof — reported here at exposition level only (not independently re-derived).

How to use it to prove something (the reusable recipe): 1. Identify the ambient randomness as a product of independent coordinates (or a distributive-lattice-structured measure satisfying the lattice condition) — e.g. the $\binom n2$ i.i.d. edge-indicators of $G(n,p)$. 2. Check that each event/property of interest is monotone (increasing or decreasing) in those coordinates — usually immediate from the definition (adding an edge can only help "contains $H$," can only hurt "is planar," etc.). 3. If two events are monotone in the *same* direction, conclude $\mathbb P(A\cap B)\ge\mathbb P(A)\mathbb P(B)$ for free — no need to control the dependence between $A$ and $B$ directly, which is often the hard part of a naive argument. This routinely replaces what would otherwise require a bespoke correlation/coupling computation. 4. If monotone in *opposite* directions, conclude $\mathbb P(A\cap B)\le \mathbb P(A)\mathbb P(B)$ — used to show two "competing" monotone structures (e.g. $\chi(G)$ large vs. $\zeta(G)$ small, or Hamiltonicity vs. sparse-colorability) cannot both be too likely simultaneously; this is exactly the lever Heckel/Steiner pull on Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? / Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) via the complement-graph trick. 5. Use the square-root-trick corollary when you can bound the probability of a *union* of several symmetric increasing events (often an easier first-moment/union-bound computation) but actually want a lower bound on a *single* one of them — converts $\mathbb P(\bigcup A_i)$ into a per-event bound without assuming independence between the $A_i$. 6. Caveat: the inequality gives only the *sign* and a specific product-form bound of the correlation, never its magnitude beyond that bound — it does not by itself produce concentration, threshold width, or sharp-threshold results (those need separate tools, e.g. Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) machinery, second-moment methods, or hypercontractivity/Fourier arguments layered on top). And it strictly requires monotonicity in a consistent partial order matching the product structure — mis-specifying the order (e.g. treating a property as increasing in the wrong coordinate direction) silently invalidates the whole argument.

Related

- Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — open Erdős–Gimbel \$1000 problem ($\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ a.s.?); Heckel's and Steiner's 2024 attacks both route through the Harris/FKG inequality applied to $G$ vs. its complement. - Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) — sibling Erdős–Gimbel–Straight 1988 problem, disproved by Steiner (arXiv:2408.02400) in the same paper that develops the Harris–FKG complement-graph argument used on #625. - Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) — threshold-location theory for increasing properties of $G(n,p)$-type product spaces; a structurally distinct but frequently-co-occurring tool (correlation sign vs. threshold *location*) for the same class of monotone-property questions. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — another general-purpose probabilistic/information-theoretic proof engine for extremal and threshold-type combinatorics questions, often used alongside or as an alternative to correlation inequalities. - R-spread set families (ALWZ/Rao's central reduction device) — the spread-measure machinery underlying modern threshold proofs (Park–Pham), a different mechanism than FKG for controlling the same kind of monotone random-structure questions.