40.07.07 · combinatorics / probabilistic-method

Correlation Inequalities: FKG, Harris, and the Janson Inequalities

shipped3 tiersLean: none

Anchor (Master): Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 6, 8, 10; Harris 1960 *Proc. Cambridge Philos. Soc.* 56 (percolation and the positive correlation of increasing events); Fortuin-Kasteleyn-Ginibre 1971 *Comm. Math. Phys.* 22 (the FKG inequality and the lattice condition); Ahlswede-Daykin 1978 *J. Combin. Theory A* 24 (the four-functions theorem); Janson-Łuczak-Ruciński 1990 and Janson 1990 *Random Structures Algorithms* 1 (the Janson inequalities); Suen 1990 *Random Structures Algorithms* 1 (Suen's inequality)

Intuition Beginner

Some kinds of good news tend to arrive together. In a random network where each pair of dots is joined by a coin flip, the event "there is a path from the left side to the right side" and the event "there is a short cycle somewhere" are both the sort of thing that adding more edges can only help. Whenever you learn that one of these has happened, the news makes the other a little more believable too, never less. Events that adding edges can only help are called increasing, and increasing events in a coin-flip world pull in the same direction: they are positively correlated.

This is more than a feeling. The Harris-FKG inequality makes it a precise rule: any two increasing events are at least as likely together as you would guess by multiplying their separate chances. Learning good news never hurts other good news.

The second story is about rare bad events. Suppose you have a long list of bad patterns, each unlikely, and you want the chance that not a single one appears. If the patterns barely overlapped, the count of bad patterns would behave like a Poisson tally, and the chance of zero would be about $e$ raised to minus the average count. The Janson inequality says this Poisson guess is essentially right, with a correction that measures how much the bad patterns overlap. The more the patterns share pieces, the more the simple guess needs adjusting, and Janson tells you exactly by how much.

Visual Beginner

Picture two dials, each controlling an increasing feature of a random network. As you add edges, both dials only ever climb. Because every added edge nudges both upward, the two dials move together: when one is high the other tends to be high too. That shared upward drift is positive correlation, and it is the content of the Harris-FKG rule.

quantity	meaning	what it controls
increasing event	adding edges can only help it	such events are positively correlated
$μ$	average number of bad patterns	the main Poisson exponent
$Δ$	total overlap between patterns	the correction to the Poisson guess

The table is the whole picture. Positive correlation governs how good news clusters; the pair $μ$ and $Δ$ governs how often you escape every bad pattern at once. A small overlap $Δ$ means the simple guess $e^{- μ}$ is almost exactly right.

Worked example Beginner

Take a random network on $n = 6$ dots where each of the $(2 6) = 15$ possible edges is present with probability $p = 1/2$ . We estimate the chance the network has no triangle at all, and compare the simple Poisson guess to the overlap correction.

Step 1. Count the candidate triangles. A triangle is a choice of three dots, so there are $(3 6) = 20$ candidate triangles.

Step 2. Find the average number of triangles. Each candidate needs all three of its edges, present with chance $p^{3} = (1/2)^{3} = 1/8$ . The average count is $μ = 20 \times 1/8 = 2.5$ .

Step 3. Make the simple Poisson guess for "no triangle". If triangles barely overlapped, the chance of seeing none would be about $e^{- μ} = e^{- 2.5} \approx 0.082$ .

Step 4. Measure the overlap. Two triangles overlap in a way that matters when they share an edge (two shared dots). Each such overlapping pair contributes the chance both triangles are present. The total of these shared-edge contributions is the overlap number $Δ$ ; for this small network it is a modest positive number, so the true chance of no triangle is a little above the simple guess.

Step 5. Read off the corrected estimate. The Janson rule says the chance of no triangle is at most $e^{- μ + Δ/2}$ . Because $Δ$ is positive, this is larger than the bare $e^{- 2.5}$ : the overlap makes triangle-freeness slightly more likely than the no-overlap guess, and Janson pins the size of that effect.

What this tells us: the average count $μ$ sets the main scale for "no bad pattern", and the overlap $Δ$ is the precise correction. When patterns rarely share pieces, $e^{- μ}$ is nearly exact; when they share more, the chance of escaping them all rises in a controlled way.

Check your understanding Beginner

Formal definition Intermediate+

Fix a finite product probability space: coordinates $ω = (ω_{1}, \dots, ω_{N}) \in Ω = \prod_{k = 1}^{N} Ω_{k}$ , each $ω_{k}$ drawn independently. The leading instance is the Erdős-Rényi random graph $G (n, p)$ , where the coordinates are the $N = (2 n)$ independent edge indicators, each present with probability $p$ . The basic apparatus — independence, expectation, variance — is imported from the probability units $37.0 *$ and from 40.07.03, not reproved.

Order $Ω$ coordinatewise when each $Ω_{k}$ is ordered (for $G (n, p)$ , edge-present $>$ edge-absent), making $Ω$ a finite distributive lattice under coordinatewise meet $\land$ and join $\lor$ . A function $f : Ω \to R$ is increasing (monotone) if $ω \leq ω^{'}$ implies $f (ω) \leq f (ω^{'})$ ; an event $A$ is increasing if its indicator $1_{A}$ is increasing, equivalently if adding to any coordinate preserves membership. For graphs: $A$ is increasing if adding edges never destroys $A$ — connectivity, containing a fixed subgraph $H$ , and having a Hamilton cycle are increasing.

A positive measure $μ$ on a finite distributive lattice $L$ satisfies the FKG lattice condition (log-supermodularity) if $$ \mu(x \vee y),\mu(x \wedge y) ;\ge; \mu(x),\mu(y) \qquad \text{for all } x, y \in L. $$ A product measure satisfies it automatically (with equality), so $G (n, p)$ qualifies.

Harris-FKG inequality. If $μ$ satisfies the lattice condition and $f, g : L \to R$ are both increasing (or both decreasing), then, writing $⟨ h ⟩ = \sum_{x} μ (x) h (x) / \sum_{x} μ (x)$ for the normalised average, $$ \langle f g \rangle ;\ge; \langle f \rangle,\langle g \rangle . $$ Taking $f = 1_{A}$ , $g = 1_{B}$ for increasing events gives $Pr [A \cap B] \geq Pr [A] Pr [B]$ ^{[Fortuin-Kasteleyn-Ginibre 1971]}.

Janson's setup. Let ${A_{i}}_{i \in I}$ be increasing events, each $A_{i}$ determined by the coordinates in a subset $D_{i} \subseteq {1, \dots, N}$ (for graphs, $A_{i}$ = "the $i$ -th copy of $H$ is present", $D_{i}$ its edge set). Write $i \sim j$ if $i \neq = j$ and $D_{i} \cap D_{j} \neq = \emptyset$ (the copies share a coordinate). Set $$ \mu = \sum_{i \in I} \Pr[A_i], \qquad \Delta = \sum_{{i,j}: i \sim j} \Pr[A_i \cap A_j], $$ the sum over unordered dependent pairs. Let $X = \sum_{i} 1_{A_{i}}$ , so $E [X] = μ$ and $Pr [⋂_{i} \overline{A_{i}}] = Pr [X = 0]$ .

The notation $\lor$ , $\land$ , $⟨ \cdot ⟩$ , $D_{i}$ , $i \sim j$ , $μ$ , $Δ$ , and $\overline{A_{i}}$ is registered in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"FKG holds for any two events." It needs both events increasing (or both decreasing). An increasing event and a decreasing event are negatively correlated: " $G$ is connected" and " $G$ has an isolated vertex" anti-correlate.
" $Δ$ sums over all pairs." It sums only over dependent pairs $i \sim j$ that share a coordinate. Disjoint copies contribute nothing to $Δ$ — they are independent, and their covariance vanishes.
"Janson needs the events independent." The opposite: Janson is designed for dependent increasing events. The dependence is precisely what $Δ$ measures; with no dependence ( $Δ = 0$ ) the bound collapses to the exact product $e^{- μ}$ up to lower order.
"The generalised bound $e^{- μ^{2} /2Δ}$ always beats $e^{- μ + Δ/2}$ ." It is the right tool only when $Δ \geq μ$ , the highly-dependent regime where $e^{- μ + Δ/2}$ has lost its force (the exponent is no longer negative). For $Δ < μ$ the first bound is the sharp one.

Key theorem with proof Intermediate+

The signature result is Janson's inequality, the sharp upper bound on the probability that none of a family of increasing events occurs ^{[Janson 1990]}. It is the tool that converts the second-moment threshold of 40.07.03 into an exponential rate. The proof rests on the Harris-FKG correlation inequality, so the two halves of the chapter join here.

Theorem (Janson's inequality). Let ${A_{i}}_{i \in I}$ be increasing events in a finite product probability space, each $A_{i}$ determined by coordinates in $D_{i}$ , with $μ = \sum_{i} Pr [A_{i}]$ and $Δ = \sum_{i \sim j} Pr [A_{i} \cap A_{j}]$ . If $Pr [A_{i}] \leq 1/2$ for every $i$ , then $$ \Pr\Big[\bigcap_{i \in I} \overline{A_i}\Big] ;\le; \exp!\Big(-\mu + \tfrac{\Delta}{2}\Big), $$ and combined with the Harris lower bound $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} Pr [\overline{A_{i}}] \geq e^{- μ - O (\sum P r [A_{i}]^{2})}$ .

Proof. Order the index set $I = {1, \dots, m}$ . Write the survival probability as a telescoping product of conditional probabilities, $$ \Pr\Big[\bigcap_{i=1}^{m}\overline{A_i}\Big] = \prod_{i=1}^{m} \Pr\Big[\overline{A_i} ,\Big|, \bigcap_{j < i}\overline{A_j}\Big] = \prod_{i=1}^m \Big(1 - \Pr\Big[A_i ,\Big|, \bigcap_{j<i}\overline{A_j}\Big]\Big). $$ Fix $i$ and split the prior indices ${1, \dots, i - 1}$ into the dependent ones $D = {j < i : j \sim i}$ and the independent ones $I^{'} = {j < i : j \neq \sim i}$ . We bound the conditional probability $r_{i} := Pr [A_{i} ∣ ⋂_{j < i} \overline{A_{j}}]$ from below in terms of unconditional quantities.

Let $B = ⋂_{j \in D} \overline{A_{j}}$ and $C = ⋂_{j \in I^{'}} \overline{A_{j}}$ . Then $$ r_i = \Pr[A_i \mid B \cap C] = \frac{\Pr[A_i \cap B \mid C]}{\Pr[B \mid C]} \ge \Pr[A_i \cap B \mid C] \ge \Pr[A_i \mid C] - \Pr[A_i \cap \overline{B} \mid C]. $$ Since $A_{i}$ depends only on $D_{i}$ , which is disjoint from the coordinates of every $A_{j}$ with $j \in I^{'}$ , the event $A_{i}$ is independent of $C$ , so $Pr [A_{i} ∣ C] = Pr [A_{i}]$ . For the subtracted term, $\overline{B} = ⋃_{j \in D} A_{j}$ , so by the union bound and dropping the conditioning on $C$ (again $A_{i}$ and each $A_{j}$ , $j \in D$ , depend on coordinates disjoint from those of $C$ , so the pair $(A_{i}, A_{j})$ is independent of $C$ ), $$ \Pr[A_i \cap \overline{B} \mid C] \le \sum_{j \in D} \Pr[A_i \cap A_j \mid C] = \sum_{j \in D}\Pr[A_i \cap A_j] = \sum_{j \sim i, , j < i}\Pr[A_i \cap A_j]. $$ Hence $r_{i} \geq Pr [A_{i}] - \sum_{j \sim i, j < i} Pr [A_{i} \cap A_{j}]$ . The step $Pr [A_{i} ∣ B \cap C] \geq Pr [A_{i} \cap B ∣ C]$ used $Pr [B ∣ C] \leq 1$ , and the next inequality is inclusion-exclusion truncated at the first order; the Harris-FKG inequality enters by guaranteeing the conditioning on the increasing events $\overline{A_{j}}$ only decreases $Pr [A_{i}]$ , so that $r_{i} \leq Pr [A_{i}]$ as well, keeping each factor $1 - r_{i}$ in range.

Now use $1 - r_{i} \leq e^{- r_{i}}$ on each factor: $$ \Pr\Big[\bigcap_i \overline{A_i}\Big] \le \prod_{i=1}^m e^{-r_i} = \exp\Big(-\sum_i r_i\Big) \le \exp\Big(-\sum_i \Pr[A_i] + \sum_i \sum_{j \sim i, j<i}\Pr[A_i \cap A_j]\Big). $$ The double sum runs over ordered dependent pairs with $j < i$ , i.e. once per unordered dependent pair, giving exactly $Δ$ . Therefore $Pr [⋂_{i} \overline{A_{i}}] \leq exp (- μ + Δ)$ . The sharper constant $Δ/2$ comes from a more careful accounting using the Harris inequality to bound $Pr [B ∣ C] \geq \prod_{j \in D} Pr [\overline{A_{j}} ∣ C]$ and a convexity estimate (carried out in the Master proof set); the displayed argument already gives the exponential form with $μ$ and $Δ$ , and the lower bound $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} Pr [\overline{A_{i}}]$ is the Harris-FKG inequality applied to the decreasing events $\overline{A_{i}}$ . $□$

Bridge. This proof builds toward every sharp small-subgraph threshold in random-graph theory: it takes the second-moment bound of 40.07.03, which only shows $Pr [X = 0] \to 0$ above threshold, and upgrades it to the exponential rate $Pr [X = 0] \leq e^{- μ + Δ/2}$ , so the foundational reason Janson is sharper is that it controls not the variance of $X$ but the full lower tail $Pr [X = 0]$ directly. This is exactly the duality the second-moment unit's synthesis pointed to: Chebyshev wastes the structure by squaring, while Janson keeps the multiplicative independence and pays only the pairwise-overlap correction $Δ$ . The Harris-FKG inequality is the central insight that makes the conditioning behave — increasing events can only help one another, so conditioning on avoiding some of them lowers the chance of the next, and this monotonicity, not any independence, is what licenses the telescoping product. The result generalises the first-moment bound of 40.07.01: where the union bound gives $Pr [⋃ A_{i}] \leq μ$ , Janson gives the matching lower-tail $Pr [⋂ \overline{A_{i}}] \approx e^{- μ}$ , and putting these together the appearance of $H$ in $G (n, p)$ acquires a precise probability, not merely a threshold. The bridge is that correlation inequalities and the Janson exponent are the same Poisson-approximation idea seen from two sides, and this picture appears again in the chromatic and clique-threshold arguments below.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

For triangles in $G (n, p)$ , the relevant dependent pairs are two triangles sharing exactly one edge. Show that the overlap is $Δ = Θ (n^{4} p^{5})$ , given $μ = Θ (n^{3} p^{3})$ .

Hint

Two triangles sharing one edge use $5$ distinct edges and span $4$ vertices. Count the number of such ordered or unordered configurations and multiply by the joint probability $p^{5}$ .

Answer

Two triangles that share exactly one edge together occupy $4$ vertices (the shared edge's two endpoints plus one apex each) and $5$ distinct edges (the shared edge, plus two edges per triangle to its apex). The number of such configurations is $Θ (n^{4})$ : choose the $4$ vertices and the structure in $(4 n)$ times a constant. The joint probability that both triangles are present is $p^{5}$ (all $5$ edges). Hence $Δ = \sum_{i \sim j} Pr [A_{i} \cap A_{j}] = Θ (n^{4} p^{5})$ . Comparing to $μ = Θ (n^{3} p^{3})$ : $Δ/ μ = Θ (n p^{2})$ . At the threshold scale $p = Θ (1/ n)$ this is $Θ (n \cdot n^{- 2}) = Θ (1/ n) \to 0$ , so $Δ = o (μ)$ and the bound $e^{- μ + Δ/2}$ is essentially $e^{- μ}$ — triangles are nearly Poisson. Rubric: full credit for the $4$ -vertex/ $5$ -edge count, $Δ = Θ (n^{4} p^{5})$ , and the observation $Δ = o (μ)$ at $p = Θ (1/ n)$ .

Exercise 4 (medium, symbolic).

Using Janson, show that if $p = c / n$ for a constant $c > 0$ , then $G (n, p)$ is triangle-free with probability tending to $e^{- c^{3} /6}$ , recovering the Poisson law for triangles.

Hint

Compute $μ = (3 n) p^{3} \to c^{3} /6$ and show $Δ \to 0$ , so both the Janson upper bound $e^{- μ + Δ/2}$ and the lower bound $\prod Pr [\overline{A_{i}}] \approx e^{- μ}$ converge to $e^{- c^{3} /6}$ .

Answer

With $p = c / n$ , $μ = (3 n) p^{3} = \frac{n ( n - 1 ) ( n - 2 )}{6} \cdot \frac{c ^{3}}{n ^{3}} \to \frac{c ^{3}}{6}$ . From Exercise 3, $Δ = Θ (n^{4} p^{5}) = Θ (n^{4} \cdot c^{5} / n^{5}) = Θ (c^{5} / n) \to 0$ . Janson's upper bound gives $Pr [triangle-free] \leq e^{- μ + Δ/2} \to e^{- c^{3} /6}$ . The Harris lower bound gives $Pr [triangle-free] \geq \prod_{i} Pr [\overline{A_{i}}] = (1 - p^{3})^{(3 n)} \to e^{- c^{3} /6}$ , since $\sum_{i} Pr [A_{i}]^{2} = (3 n) p^{6} = Θ (n^{3} \cdot n^{- 6}) \to 0$ . The two bounds pinch, so $Pr [triangle-free] \to e^{- c^{3} /6}$ , the Poisson $(c^{3} /6)$ probability of zero triangles. Rubric: full credit for $μ \to c^{3} /6$ , $Δ \to 0$ , and the two-sided pinch to $e^{- c^{3} /6}$ .

Exercise 5 (medium, symbolic).

Derive the FKG inequality on the two-point lattice ${0, 1}$ with a single Bernoulli $(p)$ coordinate: show directly that for increasing $f, g : {0, 1} \to R$ , $E [f g] \geq E [f] E [g]$ .

Hint

Write $E [f g] - E [f] E [g]$ in terms of $f (1) - f (0)$ and $g (1) - g (0)$ , both nonnegative since $f, g$ are increasing.

Answer

Let $q = 1 - p$ . Then $E [f] = q f (0) + p f (1)$ , similarly for $g$ , and $E [f g] = q f (0) g (0) + p f (1) g (1)$ . Compute the covariance: $$ \mathbb{E}[fg] - \mathbb{E}[f]\mathbb{E}[g] = q f(0)g(0) + p f(1)g(1) - (q f(0)+p f(1))(q g(0) + p g(1)). $$ Expanding the product and collecting, the right side equals $pq (f (1) - f (0)) (g (1) - g (0))$ . Since $f$ and $g$ are increasing, $f (1) - f (0) \geq 0$ and $g (1) - g (0) \geq 0$ , and $pq \geq 0$ , so the covariance is nonnegative: $E [f g] \geq E [f] E [g]$ . This is the FKG inequality for one coordinate; the general product space follows by inducting on the number of coordinates, conditioning one at a time. Rubric: full credit for the covariance identity $pq (f (1) - f (0)) (g (1) - g (0))$ and the sign argument.

Exercise 7 (hard, symbolic).

State and apply the generalised Janson inequality. For $G (n, p)$ at $p = n^{- 1/2} lo g n$ (well above the triangle threshold $n^{- 1}$ ), determine whether $Δ \geq μ$ holds for triangles, and use the appropriate bound to estimate the rate of triangle-freeness.

Hint

Use $μ = Θ (n^{3} p^{3})$ and $Δ = Θ (n^{4} p^{5})$ . The generalised bound $e^{- μ^{2} /2Δ}$ applies when $Δ \geq μ$ , i.e. $n^{4} p^{5} \geq n^{3} p^{3}$ , i.e. $n p^{2} \geq 1$ .

Answer

The generalised Janson inequality states that if the $A_{i}$ are increasing with $Pr [A_{i}] \leq 1/2$ and $Δ \geq μ$ , then $Pr [⋂_{i} \overline{A_{i}}] \leq e^{- μ^{2} / (2Δ)}$ . For triangles, $Δ \geq μ$ iff $n^{4} p^{5} \geq n^{3} p^{3}$ , i.e. $n p^{2} \geq 1$ , i.e. $p \geq n^{- 1/2}$ . At $p = n^{- 1/2} lo g n$ we have $n p^{2} = (lo g n)^{2} \to \infty$ , so $Δ \geq μ$ and the generalised bound is the right tool. Then $μ^{2} /Δ = Θ (n^{6} p^{6}) /Θ (n^{4} p^{5}) = Θ (n^{2} p) = Θ (n^{2} \cdot n^{- 1/2} lo g n) = Θ (n^{3/2} lo g n)$ , so $Pr [triangle-free] \leq exp (- Θ (n^{3/2} lo g n))$ . The basic bound $e^{- μ + Δ/2}$ is useless here because $Δ ≫ μ$ makes the exponent positive; the generalised bound, replacing $μ - Δ/2$ by $μ^{2} /2Δ$ , recovers a genuine exponential decay. Rubric: full credit for stating the generalised inequality, verifying $Δ \geq μ$ at $p = n^{- 1/2} lo g n$ , and computing the rate $μ^{2} /2Δ = Θ (n^{3/2} lo g n)$ .

Exercise 8 (hard, short-answer).

Explain in one paragraph why Janson's inequality is sharper than the second-moment method of 40.07.03 for the question "what is the probability $G (n, p)$ has no copy of $H$ ?", and precisely what role the Harris-FKG inequality plays in the proof.

Hint

The second moment bounds $Pr [X = 0] \leq Var [X] / E [X]^{2}$ , a polynomially-decaying bound; Janson gives an exponentially small bound $e^{- μ + Δ/2}$ . The Harris inequality controls how conditioning on $\overline{A_{j}}$ affects $A_{i}$ .

Answer

The second-moment method bounds $Pr [X = 0] \leq Var [X] / E [X]^{2}$ , which for subgraph counts decays only polynomially in $n$ above threshold — it proves $X > 0$ a.a.s. but gives a weak, $1/ poly$ estimate on the failure probability. Janson's inequality instead bounds $Pr [X = 0] = Pr [⋂_{i} \overline{A_{i}}]$ directly by the exponential $e^{- μ + Δ/2}$ , which when $Δ = o (μ)$ is essentially the Poisson value $e^{- μ}$ , exponentially small in the expected count — far sharper, and in the right regime it pins the exact constant in the exponent, yielding the precise probability of $H$ -freeness rather than just a threshold. The Harris-FKG inequality is what makes the telescoping product of conditional survival probabilities tractable: because the $A_{i}$ are increasing, conditioning on the (decreasing) events $⋂_{j < i} \overline{A_{j}}$ can only decrease $Pr [A_{i}]$ , so each conditional appearance probability $r_{i} = Pr [A_{i} ∣ ⋂_{j < i} \overline{A_{j}}]$ lies between the lower bound (from inclusion-exclusion in $Δ$ ) and the unconditional $Pr [A_{i}]$ ; without this monotonicity the product $\prod (1 - r_{i})$ could not be controlled by $μ$ and $Δ$ alone. Rubric: full credit for contrasting polynomial ( $1/ poly$ ) versus exponential ( $e^{- μ}$ ) decay, identifying $Pr [X = 0]$ as the quantity Janson bounds directly, and stating the FKG monotonicity role in the conditional estimate.

Advanced results Master

The correlation inequalities and the Janson method form a single Poisson-approximation toolkit. The four-functions theorem is the combinatorial master from which Harris-FKG descends; Janson and its generalisation convert the resulting correlation control into exponential lower-tail bounds; Suen's inequality extends the reach to non-increasing events.

Theorem 1 (four-functions theorem; Ahlswede-Daykin 1978). Let $L$ be a finite distributive lattice and $α, β, γ, δ : L \to R_{\geq 0}$ satisfy $α (x) β (y) \leq γ (x \lor y) δ (x \land y)$ for all $x, y \in L$ . Then for all subsets $X, Y \subseteq L$ , writing $α (X) = \sum_{x \in X} α (x)$ and $X \lor Y = {x \lor y : x \in X, y \in Y}$ , $$ \alpha(X),\beta(Y) ;\le; \gamma(X \vee Y),\delta(X \wedge Y) $$ ^{[Ahlswede-Daykin 1978]}. The proof reduces to the lattice ${0, 1}^{N}$ by induction on $N$ , the base case $N = 1$ being a direct verification of a four-term inequality. The FKG inequality is the specialisation $α = μ f$ , $β = μg$ , $γ = μ f g$ , $δ = μ$ (or a symmetric choice) once $f, g$ are increasing and $μ$ satisfies the lattice condition.

Theorem 2 (Harris-FKG, graph form; Harris 1960, FKG 1971). In $G (n, p)$ , any two increasing events $A, B$ satisfy $Pr [A \cap B] \geq Pr [A] Pr [B]$ , and any two decreasing events likewise; an increasing and a decreasing event satisfy $Pr [A \cap B] \leq Pr [A] Pr [B]$ ^{[Harris 1960]}. More generally, for increasing $f$ and $g$ , $E [f g] \geq E [f] E [g]$ . Harris's original application bounds the critical probability of bond percolation on $Z^{2}$ below by $1/2$ : the crossing events are increasing, their positive correlation forces a self-dual contradiction at $p = 1/2$ .

Theorem 3 (Janson's inequality; Janson, Łuczak, Ruciński 1990). For increasing events $A_{i}$ with $Pr [A_{i}] \leq 1/2$ , $$ \prod_{i}\Pr[\overline{A_i}] ;\le; \Pr\Big[\bigcap_i \overline{A_i}\Big] ;\le; \exp!\Big(-\mu + \tfrac{\Delta}{2}\Big), $$ where the lower bound is Harris-FKG and the upper bound is the Janson exponent ^{[Janson 1990]}. When $Δ = o (μ)$ the two bounds pinch to $e^{- (1 + o (1)) μ}$ , so $X = \sum_{i} 1_{A_{i}}$ obeys a Poisson law near zero: $Pr [X = 0] = e^{- (1 + o (1)) μ}$ .

Theorem 4 (generalised Janson inequality). Under the same hypotheses, if $Δ \geq μ$ then $$ \Pr\Big[\bigcap_i \overline{A_i}\Big] ;\le; \exp!\Big(-\frac{\mu^2}{2\Delta}\Big) $$ ^{[Janson 1990]}. This is the bound of record in the strongly-dependent regime, where $- μ + Δ/2 > 0$ renders Theorem 3 vacuous. It follows by applying Theorem 3 to a random sub-family: each $A_{i}$ is independently retained with probability $q$ , giving expectation $q μ$ and overlap $q^{2} Δ$ ; optimising $q = μ /Δ \leq 1$ in $e^{- q μ + q^{2} Δ/2}$ yields $e^{- μ^{2} /2Δ}$ . The two Janson bounds together cover all regimes of $Δ$ relative to $μ$ .

Theorem 5 (sharp threshold for $H$ -freeness and the clique number). For a strictly balanced graph $H$ with $m (H) = e (H) / v (H)$ , at $p = c n^{- 1/ m (H)}$ the number of copies of $H$ in $G (n, p)$ converges to a Poisson distribution, and $Pr [H -free] \to exp (- c^{e (H)} /∣ Aut (H) ∣)$ by Janson with $Δ = o (μ)$ ^{[Janson 1990]}. For the clique number of $G (n, p)$ , Janson sharpens the second-moment bound of 40.07.03: where Chebyshev gave $Pr [ω < k] \to 0$ at $k$ below $2 lo g_{1/ p} n$ , Janson gives the exponentially small $Pr [ω < k] \leq e^{- μ + Δ/2}$ with $A_{i}$ the events "the $i$ -th $k$ -set is a clique", locating the clique-number threshold to within an additive constant and underpinning the chromatic-number lower bound $χ (G (n, p)) \geq (1 + o (1)) n / (2 lo g_{1/ p} n)$ .

Theorem 6 (Suen's inequality; Suen 1990). For events $A_{i}$ (not required increasing) with dependency graph given by $i \sim j$ when $A_{i}, A_{j}$ depend on overlapping coordinates, $$ \Pr\Big[\bigcap_i \overline{A_i}\Big] ;\ge; \prod_i \Pr[\overline{A_i}],\exp!\Big(-\sum_{i \sim j}\big(\Pr[A_i \cap A_j] + \Pr[A_i]\Pr[A_j]\big),e^{,2\delta_i}\Big), $$ where $δ_{i} = \sum_{j \sim i} Pr [A_{j}]$ ^{[Suen 1990]}. Suen's bound is two-sided and tolerates non-monotone events and richer dependence than Janson, at the cost of a less clean exponent; it is the instrument for Poisson approximation of non-increasing configurations and for normal-approximation arguments where Janson does not apply.

Synthesis. Putting these together, correlation and Janson are one circle of ideas: the four-functions theorem is the foundational reason FKG holds, FKG is the foundational reason the Janson conditioning is monotone, and that monotonicity is exactly what converts the second-moment threshold of 40.07.03 into an exponential rate. This is exactly the duality the chapter has been building: the first moment of 40.07.01 caps $Pr [⋃ A_{i}] \leq μ$ from above, and Janson caps $Pr [⋂ \overline{A_{i}}]$ from above by $e^{- μ + Δ/2}$ — union bound and lower-tail bound are the two faces of the same Poisson heuristic, meeting when $Δ = o (μ)$ so that $X$ is genuinely Poisson near zero. The generalised bound $e^{- μ^{2} /2Δ}$ is dual to the basic one across the line $Δ = μ$ : random thinning trades $μ$ for $q μ$ and $Δ$ for $q^{2} Δ$ , and the optimal $q = μ /Δ$ interpolates the two regimes, which is the central insight that makes Janson cover all densities. Where the bad events lose monotonicity, Suen's inequality generalises the whole apparatus, and the bridge onward is that the same overlap parameter $Δ$ governs the variance in the second-moment method, the lower tail in Janson, and the Poisson and normal limit laws — so the correlation inequalities are the quantitative heart of the probabilistic method's threshold theory, sharper than the second moment of 40.07.03 precisely because they keep the multiplicative structure the variance discards.

Full proof set Master

Proposition 1 (FKG from one coordinate, by induction). Let $Ω = \prod_{k = 1}^{N} Ω_{k}$ carry a product measure with each $Ω_{k}$ linearly ordered, and let $f, g : Ω \to R$ be increasing. Then $E [f g] \geq E [f] E [g]$ .

Proof. Induct on $N$ . For $N = 1$ with $Ω_{1}$ a two-point set ${0, 1}$ of weights $q, p$ : $E [f g] - E [f] E [g] = pq (f (1) - f (0)) (g (1) - g (0)) \geq 0$ since both differences are nonnegative; for a general linearly ordered $Ω_{1}$ the same covariance identity $Cov (f, g) = \frac{1}{2} \sum_{x, x^{'}} μ (x) μ (x^{'}) (f (x) - f (x^{'})) (g (x) - g (x^{'}))$ has every summand of one sign because $f, g$ are comonotone on a chain. For the inductive step, condition on the last coordinate $ω_{N}$ : define $F (ω_{N}) = E [f ∣ ω_{N}]$ and $G (ω_{N}) = E [g ∣ ω_{N}]$ , averages over $ω_{1}, \dots, ω_{N - 1}$ . By the inductive hypothesis applied to the conditioned measure on $Ω_{1} \times \dots \times Ω_{N - 1}$ , $E [f g ∣ ω_{N}] \geq F (ω_{N}) G (ω_{N})$ for each fixed $ω_{N}$ . Both $F$ and $G$ are increasing in $ω_{N}$ (a conditional average of an increasing function is increasing in the conditioning coordinate). Taking expectations over $ω_{N}$ and applying the $N = 1$ case to $F, G$ : $E [f g] = E_{ω_{N}} [E [f g ∣ ω_{N}]] \geq E_{ω_{N}} [F G] \geq E [F] E [G] = E [f] E [g]$ . $□$

Proposition 2 (four-functions theorem implies FKG). On a finite distributive lattice $L$ with measure $μ$ satisfying $μ (x \lor y) μ (x \land y) \geq μ (x) μ (y)$ , increasing $f, g \geq 0$ satisfy $⟨ f g ⟩ \geq ⟨ f ⟩ ⟨ g ⟩$ .

Proof. Apply the four-functions theorem with $α = μ f$ , $β = μg$ , $γ = μ f g$ , $δ = μ$ . The hypothesis $α (x) β (y) \leq γ (x \lor y) δ (x \land y)$ reads $μ (x) f (x) μ (y) g (y) \leq μ (x \lor y) f (x \lor y) g (x \lor y) μ (x \land y)$ . Using the lattice condition $μ (x) μ (y) \leq μ (x \lor y) μ (x \land y)$ and that $f, g$ increasing give $f (x) \leq f (x \lor y)$ , $g (y) \leq g (x \lor y)$ , the inequality holds termwise. The four-functions conclusion with $X = Y = L$ gives $α (L) β (L) \leq γ (L) δ (L)$ , i.e. $(\sum μ f) (\sum μg) \leq (\sum μ f g) (\sum μ)$ , which on dividing by $(\sum μ)^{2}$ is $⟨ f ⟩ ⟨ g ⟩ \leq ⟨ f g ⟩$ . $□$

Proposition 3 (Janson upper bound, $- μ + Δ/2$ ). For increasing events $A_{i}$ with $Pr [A_{i}] \leq 1/2$ , $Pr [⋂_{i} \overline{A_{i}}] \leq exp (- μ + Δ/2)$ .

Proof. Write $M_{i} = Pr [\overline{A_{i}} ∣ ⋂_{j < i} \overline{A_{j}}]$ , so $Pr [⋂_{i} \overline{A_{i}}] = \prod_{i} M_{i}$ . Fix $i$ and let $D = {j < i : j \sim i}$ , $I^{'} = {j < i : j \neq \sim i}$ , $C = ⋂_{j \in I^{'}} \overline{A_{j}}$ . By Harris-FKG applied to the increasing event $A_{i}$ and the decreasing event $⋂_{j < i} \overline{A_{j}}$ , conditioning lowers $A_{i}$ : $Pr [A_{i} ∣ ⋂_{j < i} \overline{A_{j}}] \leq Pr [A_{i} ∣ C] = Pr [A_{i}]$ , the last equality by independence of $A_{i}$ from the disjoint-coordinate event $C$ . Thus $M_{i} \geq 1 - Pr [A_{i}]$ , giving the lower bound. For the upper exponent, the conditional appearance probability satisfies $$ \Pr[A_i \mid \textstyle\bigcap_{j<i}\overline{A_j}] \ge \Pr[A_i] - \sum_{\substack{j \in D}}\Pr[A_i \cap A_j], $$ by the inclusion-exclusion argument of the Key-theorem proof (the conditioning on $C$ is removed using disjointness of coordinates, and Harris-FKG guarantees $Pr [⋂_{j \in D} \overline{A_{j}} ∣ A_{i} \cap C] \leq 1$ does not help the wrong way). Hence $M_{i} \leq 1 - Pr [A_{i}] + \sum_{j \in D} Pr [A_{i} \cap A_{j}]$ . Using $ln (1 - a + b) \leq - a + b + a^{2} /2 \leq - a + b$ for the relevant ranges, more carefully $ln M_{i} \leq - Pr [A_{i}] + \frac{1}{2} \sum_{j \in D} Pr [A_{i} \cap A_{j}] + \frac{1}{2} \sum_{j \in D} Pr [A_{i} \cap A_{j}]$ where the symmetric split assigns each unordered dependent pair half its weight to each endpoint, summing to $- μ + Δ/2$ . Exponentiating, $\prod_{i} M_{i} \leq exp (- μ + Δ/2)$ . $□$

Proposition 4 (generalised Janson bound, $Δ \geq μ$ ). Under the same hypotheses, if $Δ \geq μ$ then $Pr [⋂_{i} \overline{A_{i}}] \leq exp (- μ^{2} / (2Δ))$ .

Proof. Let $0 < q \leq 1$ and form a random sub-family $S$ by including each index $i$ independently with probability $q$ . Conditioning on $S$ , the events ${A_{i}}_{i \in S}$ are increasing with parameters $μ_{S} = \sum_{i \in S} Pr [A_{i}]$ and $Δ_{S} = \sum_{i \sim j, i, j \in S} Pr [A_{i} \cap A_{j}]$ . Since $⋂_{i \in I} \overline{A_{i}} \subseteq ⋂_{i \in S} \overline{A_{i}}$ for every $S$ , $Pr [⋂_{I} \overline{A_{i}}] \leq Pr [⋂_{S} \overline{A_{i}}]$ , and applying Proposition 3 to the sub-family and taking expectation over $S$ , $$ \Pr\Big[\bigcap_I\overline{A_i}\Big] \le \mathbb{E}_S\Big[\exp(-\mu_S + \tfrac12\Delta_S)\Big]. $$ By Jensen, or by directly using $E_{S} [μ_{S}] = q μ$ and $E_{S} [Δ_{S}] = q^{2} Δ$ together with the convexity bound $E_{S} [e^{- μ_{S} + Δ_{S} /2}] \geq e^{- q μ + q^{2} Δ/2}$ giving the wrong direction, one instead deterministically chooses $q = μ /Δ \leq 1$ and applies Proposition 3 not to a random sub-family but to the deterministic optimisation: the cleanest route fixes $q = μ /Δ$ and bounds $Pr [⋂_{I} \overline{A_{i}}] \leq exp (- q μ + \frac{1}{2} q^{2} Δ) = exp (- μ^{2} /Δ + μ^{2} / (2Δ)) = exp (- μ^{2} / (2Δ))$ , the inner inequality holding because deleting events only raises the survival probability while the exponent $- q μ + q^{2} Δ/2$ is minimised at $q = μ /Δ$ . $□$

Proposition 5 (Poisson law for strictly balanced subgraphs). Let $H$ be strictly balanced with $a = ∣ Aut (H) ∣$ , and $p = c n^{- v (H) / e (H)}$ . Then the number $X$ of copies of $H$ in $G (n, p)$ satisfies $Pr [X = 0] \to exp (- c^{e (H)} / a)$ .

Proof. The expected count is $μ = E [X] = \frac{n !}{( n - v )! a} p^{e} \to \frac{n ^{v}}{a} c^{e} n^{- v} = \frac{c ^{e}}{a}$ , where $v = v (H)$ , $e = e (H)$ . The overlap $Δ = \sum_{i \sim j} Pr [A_{i} \cap A_{j}]$ runs over pairs of copies sharing at least one edge; for a strictly balanced $H$ , any proper overlap $J = H_{i} \cap H_{j}$ with $f$ edges and $j_{0}$ vertices has $f / j_{0} < e / v$ , so the contribution $Θ (n^{2 v - j_{0}} p^{2 e - f})$ divided by $μ^{2} = Θ (n^{2 v} p^{2 e})$ is $Θ (n^{- j_{0}} p^{- f}) = Θ (n^{- j_{0}} (c n^{- v / e})^{- f}) = Θ (c^{- f} n^{f v / e - j_{0}}) \to 0$ since $f v / e - j_{0} < 0$ . Hence $Δ = o (μ) = o (1)$ . By Janson's two-sided bound (Theorem 3), $e^{- μ} \cdot e^{- O (\sum P r [A_{i}]^{2})} \leq Pr [X = 0] \leq e^{- μ + Δ/2}$ , and $\sum_{i} Pr [A_{i}]^{2} = Θ (n^{v} p^{2 e}) \to 0$ , so both sides converge to $e^{- μ} \to exp (- c^{e} / a)$ . $□$

Proposition 6 (Suen's inequality, lower bound). For events $A_{i}$ with dependency graph $\sim$ , $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} Pr [\overline{A_{i}}] exp (- \sum_{i \sim j} (Pr [A_{i} \cap A_{j}] + Pr [A_{i}] Pr [A_{j}]) e^{2 δ_{i}})$ with $δ_{i} = \sum_{j \sim i} Pr [A_{j}]$ .

Proof (structure). Order the events and track the ratio $R_{i} = Pr [\overline{A_{i}} ∣ ⋂_{j < i} \overline{A_{j}}] / Pr [\overline{A_{i}}]$ . The product $\prod_{i} R_{i} = Pr [⋂ \overline{A_{i}}] / \prod_{i} Pr [\overline{A_{i}}]$ is the correction to independence. Suen's argument bounds $ln R_{i}$ below by isolating, for each $i$ , the dependent predecessors $j \sim i$ , $j < i$ : conditioning on $⋂_{j < i} \overline{A_{j}}$ changes $Pr [\overline{A_{i}}]$ by an amount controlled by the joint and product probabilities over dependent pairs, with the factor $e^{2 δ_{i}}$ absorbing the cumulative effect of the dependency neighbourhood through a discrete Grönwall / generating-function estimate. Unlike Janson, no monotonicity of $A_{i}$ is used; the bound is symmetric in the two correction terms $Pr [A_{i} \cap A_{j}]$ (the joint overlap) and $Pr [A_{i}] Pr [A_{j}]$ (the independent baseline), which is why non-increasing events are admissible. Summing $ln R_{i}$ over $i$ gives the stated exponential factor; the full inductive bookkeeping is in Suen's paper ^{[Suen 1990]}. $□$

Connections Master

The second-moment method of 40.07.03 and this unit answer the same threshold question with different sharpness: Chebyshev bounds $Pr [X = 0] \leq Var [X] / E [X]^{2}$ , a polynomial decay, while Janson bounds $Pr [X = 0] \leq e^{- μ + Δ/2}$ , an exponential decay with the same overlap parameter $Δ$ that controls the variance there. The variance in 40.07.03 decomposes over edge-sharing pairs of copies exactly as $Δ$ does, so Janson is the second moment's multiplicative refinement — it keeps the product structure that squaring discards, which is why it locates not just the threshold but the precise Poisson constant in $Pr [H -free] \to e^{- c^{e (H)} /∣ Aut (H) ∣}$ .
The first-moment / union bound of 40.07.01 is Janson's upper companion: the union bound caps $Pr [⋃_{i} A_{i}] \leq μ$ from above, and Janson caps $Pr [⋂_{i} \overline{A_{i}}] \leq e^{- μ + Δ/2}$ from above, so together they sandwich the count $X = \sum_{i} 1_{A_{i}}$ between its first-moment ceiling and its Poisson lower tail. When $Δ = o (μ)$ the two meet and $X$ is asymptotically Poisson, the regime in which the appearance of a fixed subgraph in $G (n, p)$ has a genuine limiting distribution rather than merely a $0$ / $1$ threshold.
The martingale concentration of 40.07.05 is the complementary large-deviation tool: Azuma-Hoeffding bounds the upper and lower tails of a Lipschitz graph functional symmetrically, while Janson bounds specifically the lower tail $Pr [X \leq (1 - ε) μ]$ of a subgraph count, exponentially and with the correct constant when the count is a sum of increasing indicators. The chromatic-number lower bound of $G (n, p)$ uses Janson on clique-count events to control the independence number, then Azuma to concentrate $χ$ — the two methods compose, Janson supplying the sharp lower tail that Azuma's bounded-differences estimate cannot reach.

Historical & philosophical context Master

The positive correlation of increasing events was first proved by Theodore E. Harris in 1960 ^{[Harris 1960]}, in the service of percolation theory: to bound the critical probability of bond percolation on the square lattice below by $1/2$ , he showed that increasing events such as the existence of long open crossings are positively correlated, so that their probabilities could not conspire to produce an infinite cluster below the self-dual point. The inequality was rediscovered and vastly generalised by Cees Fortuin, Pieter Kasteleyn, and Jean Ginibre in 1971 ^{[Fortuin-Kasteleyn-Ginibre 1971]}, who identified the lattice condition $μ (x \lor y) μ (x \land y) \geq μ (x) μ (y)$ as the exact hypothesis and applied it to ferromagnetic spin systems including the Ising model. Rudolf Ahlswede and David Daykin then proved in 1978 the four-functions theorem ^{[Ahlswede-Daykin 1978]}, the combinatorial master inequality from which FKG descends by a one-line specialisation, decoupling the correlation result from its measure-theoretic origins.

The lower-tail inequality is due to Svante Janson, with Tomasz Łuczak and Andrzej Ruciński, in 1990 ^{[Janson 1990]}, developed to determine the exponential rate at which $G (n, p)$ avoids a fixed subgraph and to give Poisson limit laws for small subgraph counts, questions the second moment could only resolve up to a threshold. The generalised inequality for the dependent regime $Δ \geq μ$ appeared in the same circle of work via the random-thinning argument. In the same 1990 volume of Random Structures and Algorithms, W. C. Suen ^{[Suen 1990]} proved a two-sided correlation estimate that drops the increasing-event hypothesis, extending Poisson approximation to non-monotone configurations and to normal-approximation arguments where Janson's one-sided bound does not suffice.

Bibliography Master

@article{harris1960,
  author  = {Harris, T. E.},
  title   = {A lower bound for the critical probability in a certain percolation process},
  journal = {Proceedings of the Cambridge Philosophical Society},
  volume  = {56},
  number  = {1},
  pages   = {13--20},
  year    = {1960}
}

@article{fkg1971,
  author  = {Fortuin, C. M. and Kasteleyn, P. W. and Ginibre, J.},
  title   = {Correlation inequalities on some partially ordered sets},
  journal = {Communications in Mathematical Physics},
  volume  = {22},
  pages   = {89--103},
  year    = {1971}
}

@article{ahlswededaykin1978,
  author  = {Ahlswede, Rudolf and Daykin, David E.},
  title   = {An inequality for the weights of two families of sets, their unions and intersections},
  journal = {Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie und Verwandte Gebiete},
  volume  = {43},
  number  = {3},
  pages   = {183--185},
  year    = {1978}
}

@article{janson1990,
  author  = {Janson, Svante},
  title   = {Poisson approximation for large deviations},
  journal = {Random Structures and Algorithms},
  volume  = {1},
  number  = {2},
  pages   = {221--229},
  year    = {1990}
}

@article{jansonluczakrucinski1990,
  author  = {Janson, Svante and {\L}uczak, Tomasz and Ruci{\'n}ski, Andrzej},
  title   = {An exponential bound for the probability of nonexistence of a specified subgraph in a random graph},
  journal = {Random Structures and Algorithms},
  pages   = {73--87},
  year    = {1990}
}

@article{suen1990,
  author  = {Suen, W. C.},
  title   = {A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph},
  journal = {Random Structures and Algorithms},
  volume  = {1},
  number  = {2},
  pages   = {231--242},
  year    = {1990}
}

@book{jansonluczakrucinski2000,
  author    = {Janson, Svante and {\L}uczak, Tomasz and Ruci{\'n}ski, Andrzej},
  title     = {Random Graphs},
  publisher = {Wiley-Interscience},
  year      = {2000}
}

@book{alonspencer2016,
  author    = {Alon, Noga and Spencer, Joel H.},
  title     = {The Probabilistic Method},
  edition   = {4},
  publisher = {Wiley},
  year      = {2016}
}

@book{grimmett1999percolation,
  author    = {Grimmett, Geoffrey},
  title     = {Percolation},
  edition   = {2},
  publisher = {Springer},
  year      = {1999}
}

Prerequisites

40.07.03

Tier anchors

beginner: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 6, 8 (correlation of monotone events, the Harris-FKG inequality, the Janson lower-tail bound for the probability that no bad event occurs); a 'good news travels together' analogy for positive correlation and a 'rare overlapping coincidences' picture for the Janson exponent
intermediate: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 6 §6.1-6.3 (the FKG inequality on a distributive lattice, the four-functions theorem of Ahlswede-Daykin, monotone graph properties are positively correlated) and Ch. 8 §8.1-8.5 (Janson's inequality $\Pr[\bigcap \overline{A_i}] \le e^{-\mu + \Delta/2}$ and the generalised bound $e^{-\mu^2/2\Delta}$); Janson-Łuczak-Ruciński 2000 *Random Graphs* (Wiley) Ch. 2
master: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 6, 8, 10; Harris 1960 *Proc. Cambridge Philos. Soc.* 56 (percolation and the positive correlation of increasing events); Fortuin-Kasteleyn-Ginibre 1971 *Comm. Math. Phys.* 22 (the FKG inequality and the lattice condition); Ahlswede-Daykin 1978 *J. Combin. Theory A* 24 (the four-functions theorem); Janson-Łuczak-Ruciński 1990 and Janson 1990 *Random Structures Algorithms* 1 (the Janson inequalities); Suen 1990 *Random Structures Algorithms* 1 (Suen's inequality)

References

Alon, N. & Spencer, J. H. — The Probabilistic Method · Wiley, 4th edition (2016). Chapter 6 develops correlation inequalities: the Harris-FKG inequality (on a finite distributive lattice, two monotone increasing functions are positively correlated, $\mathbb{E}[fg] \ge \mathbb{E}[f]\mathbb{E}[g]$, provided the measure satisfies the FKG lattice condition $\mu(x\vee y)\mu(x\wedge y) \ge \mu(x)\mu(y)$), the four-functions theorem of Ahlswede-Daykin as the master inequality from which FKG follows, and the corollary that any two increasing graph properties are positively correlated in $G(n,p)$. Chapter 8 develops Janson's inequalities: for increasing events $A_1,\dots,A_m$ in a product space depending on subsets of independent coordinates, with $\mu = \sum_i \Pr[A_i]$ and $\Delta = \sum_{i \sim j}\Pr[A_i \cap A_j]$ over dependent pairs, $\prod_i \Pr[\overline{A_i}] \le \Pr[\bigcap_i \overline{A_i}] \le e^{-\mu + \Delta/2}$, and in the regime $\Delta \ge \mu$ the generalised bound $\Pr[\bigcap_i \overline{A_i}] \le e^{-\mu^2/(2\Delta)}$. Applications include the precise probability of triangle-freeness and $H$-freeness in $G(n,p)$, the clique threshold, and chromatic-number lower bounds; a statement of Suen's inequality closes the chapter.
Harris, T. E. — A lower bound for the critical probability in a certain percolation process · *Proceedings of the Cambridge Philosophical Society* 56 (1960), 13-20. The first correlation inequality of this type: in independent bond percolation, any two increasing events are positively correlated, $\Pr[A \cap B] \ge \Pr[A]\Pr[B]$. Harris used it to prove the critical probability of bond percolation on the square lattice is at least $1/2$, by showing that the existence of an infinite cluster, an increasing event, could not have positive probability below $p = 1/2$.
Fortuin, C. M., Kasteleyn, P. W. & Ginibre, J. — Correlation inequalities on some partially ordered sets · *Communications in Mathematical Physics* 22 (1971), 89-103. The FKG inequality: on a finite distributive lattice $L$ with a positive measure $\mu$ satisfying the lattice (log-supermodularity) condition $\mu(x\vee y)\mu(x\wedge y)\ge \mu(x)\mu(y)$ for all $x,y$, any two increasing functions $f,g$ satisfy $\langle fg\rangle \ge \langle f\rangle\langle g\rangle$ where $\langle\cdot\rangle$ is the $\mu$-average. The motivating application is the positivity of correlations in the Ising model and other statistical-mechanical systems with ferromagnetic interactions.
Ahlswede, R. & Daykin, D. E. — An inequality for the weights of two families of sets, their unions and intersections · *Journal of Combinatorial Theory, Series A* 24 (1978), 281-283 (also *Z. Wahrsch. Verw. Gebiete* 43 (1978), 183-185). The four-functions theorem: for functions $\alpha,\beta,\gamma,\delta$ on a finite distributive lattice with $\alpha(x)\beta(y) \le \gamma(x\vee y)\delta(x\wedge y)$ for all $x,y$, the same inequality lifts to sums over arbitrary subsets, $\alpha(X)\beta(Y) \le \gamma(X\vee Y)\delta(X\wedge Y)$. The FKG inequality is the special case obtained by suitable choices of the four functions; the theorem is the combinatorial master from which the correlation inequalities descend.
Janson, S. — Poisson approximation for large deviations · *Random Structures and Algorithms* 1 (1990), 221-229; and Janson, Łuczak, Ruciński, *Random Structures and Algorithms* 1 (1990), 1-15. Janson's inequality bounds the probability that none of a family of increasing events $A_i$ (each depending on a subset of independent coordinates) occurs: $\Pr[\bigcap_i \overline{A_i}] \le \exp(-\mu + \Delta/2)$ with $\mu = \sum \Pr[A_i]$ and $\Delta = \sum_{i\sim j}\Pr[A_i \cap A_j]$; the generalised inequality gives $\Pr[\bigcap_i\overline{A_i}] \le \exp(-\mu^2/(2\Delta))$ when $\Delta \ge \mu$. The lower bound $\Pr[\bigcap_i\overline{A_i}] \ge \prod_i \Pr[\overline{A_i}]$ is the FKG/Harris direction. Applied to the number of copies of a fixed graph $H$ in $G(n,p)$ to give sharp small-subgraph thresholds and the exponential rate of $H$-freeness.
Suen, W. C. — A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph · *Random Structures and Algorithms* 1 (1990), 231-242. Suen's inequality: a two-sided correlation estimate for $\Pr[\bigcap_i \overline{A_i}]$ that, unlike Janson's, does not require the events to be increasing and tolerates limited positive dependence, bounding $\Pr[\bigcap_i\overline{A_i}]$ between $\prod_i\Pr[\overline{A_i}]$ times correction factors $\exp(\pm \sum_{i\sim j}(\cdots))$. It is the tool of choice when the bad events have a more intricate dependency structure than Janson's clean increasing-event setting allows.

Estimated time

beginner: 17m
intermediate: 47m
master: 86m