Janson Inequalities

The Janson inequalities provide precise estimates for the probability that none of a collection of "bad" events occurs in a product probability space. They are particularly effective for subgraph containment problems in random graphs.

Setup and Statement

Theorem7.3Janson's Inequality

Let $\Omega = \prod_{i \in I} \Omega_i$ be a product probability space. For each $\alpha \in \mathcal{A}$ (a finite index set), let $A_\alpha$ be an event determined by coordinates in $S_\alpha \subseteq I$ . Write $\alpha \sim \beta$ if $S_\alpha \cap S_\beta \neq \emptyset$ and $\alpha \neq \beta$ . Define: $\mu = \sum_{\alpha} \Pr[A_\alpha], \quad \Delta = \sum_{\alpha \sim \beta} \Pr[A_\alpha \cap A_\beta].$ Then: $\Pr\left[\bigcap_\alpha \overline{A_\alpha}\right] \leq \exp\left(-\mu + \frac{\Delta}{2}\right).$ If additionally $\Delta \leq \mu$ , then: $\Pr\left[\bigcap_\alpha \overline{A_\alpha}\right] \geq \exp\left(-\mu - \Delta\right).$

Extended Janson Inequality

Theorem7.4Extended Janson (Kim-Vu)

Under the same setup, if $\Pr[A_\alpha] \leq \varepsilon$ for all $\alpha$ and $\Delta \leq \delta \mu$ , then: $\Pr\left[\bigcap_\alpha \overline{A_\alpha}\right] = \exp(-\mu(1 + O(\delta + \varepsilon))).$ This provides a near-exact estimate when individual event probabilities are small and the total correlation $\Delta$ is small relative to $\mu$ .

ExampleTriangle-Free Random Graphs

Let $X$ count triangles in $G(n, p)$ . Then $\mu = \binom{n}{3} p^3$ and $\Delta = \Theta(n^4 p^5)$ (pairs of triangles sharing an edge). When $p = o(n^{-1/2})$ , $\Delta = o(\mu)$ , and Janson's inequality gives: $\Pr[X = 0] = \exp(-\mu(1 + o(1))) = \exp\left(-\Theta(n^3 p^3)\right).$

RemarkComparison with LLL

Janson's inequality and the Lovász Local Lemma address similar problems (avoiding bad events) but with different strengths. The LLL gives a positive probability under weaker conditions but provides no quantitative bound, while Janson's inequality requires a product space but gives precise exponential estimates. For random graph applications, Janson is typically preferred.

ExampleSmall Subgraph Containment

For a fixed graph $H$ with $v$ vertices and $e$ edges, the number of copies of $H$ in $G(n, p)$ has expectation $\mu \asymp n^v p^e$ . When $p \ll n^{-v/e}$ (below the threshold), Janson's inequality shows $\Pr[\text{no copy of } H] = \exp(-\Theta(\mu))$ , confirming Poisson-like behavior.