Random-set construction + Janson's inequality / Vu concentration (the Poisson paradigm)

Statement

Setup (Janson's inequality, containment/covering form) — Y. Zhao, MIT 18.226 Ch. 8, Setup 8.1.1, read in full. Let $R$ be a random subset of $[N]$, each element included independently (possibly with different probabilities). Let $S_1,\dots,S_k\subseteq[N]$ and let $A_i$ be the event $S_i\subseteq R$. Let $X=\sum_i \mathbf 1_{A_i}$ count how many of the $S_i$ land inside $R$, and set $$\mu=\mathbb E[X]=\sum_i\mathbb P(A_i),\qquad \Delta=\sum_{(i,j):\,i\sim j}\mathbb P(A_i\cap A_j),$$ where $i\sim j$ means $i\ne j$ and $S_i\cap S_j\ne\varnothing$ (each unordered pair counted once). $\Delta$ measures the total pairwise dependency mass between "overlapping" potential occurrences.

Janson's inequality I (Janson–Łuczak–Ruciński 1990; Zhao Thm 8.1.2, proof read in full): $$\mathbb P(X=0)\;\le\; e^{-\mu+\Delta/2}.$$ Most useful when $\Delta=o(\mu)$: combined with the trivial Harris-inequality lower bound $\mathbb P(X=0)\ge\prod_i(1-\mathbb P(A_i))=e^{-(1+o(1))\mu}$ (valid when each $\mathbb P(A_i)=o(1)$), this pins down $\mathbb P(X=0)=e^{-(1+o(1))\mu}$ exactly — i.e. $X$ behaves, at the level of the nonexistence probability, exactly like a $\mathrm{Poisson}(\mu)$ random variable, for which $\mathbb P(\mathrm{Po}(\mu)=0)=e^{-\mu}$. This "$X$'s nonexistence probability mimics a Poisson with the same mean" phenomenon is what is called the Poisson paradigm in this literature (Janson, "Poisson approximation for large deviations," *Random Structures & Algorithms* 1(2) (1990) 221–229; Janson–Łuczak–Ruciński, *Random Graphs*, Wiley 2000, dedicates chapters to "Poisson approximation" and "Stein's method: the Poisson case," per the book's table of contents).

Janson's inequality II (the complementary regime $\Delta\ge\mu$; Zhao Thm 8.1.8, proof read in full — obtained by applying Janson I to a randomly $q$-subsampled subfamily of the $S_i$ and optimizing $q=\mu/\Delta\in[0,1]$): $$\mathbb P(X=0)\;\le\; e^{-\mu^2/(2\Delta)}.$$

Janson's inequality III (lower-tail generalization, proof by L. Warnke via a tilted moment-generating-function/Markov argument closely paralleling the Chernoff-bound proof; Zhao Thm 8.2.2, proof read in full): for any $0\le t\le\mu$, $$\mathbb P(X\le\mu-t)\;\le\;\exp\!\left(\frac{-t^2}{2(\mu+\Delta)}\right).$$ Setting $t=\mu$ recovers (up to a constant in the exponent) both Janson I and II simultaneously — this single inequality is the one to remember. (An equivalent formulation using $\bar\Delta=\mu+2\Delta$ and the function $\varphi(x)=(1+x)\ln(1+x)-x$ appears on en.wikipedia.org/wiki/Janson's_inequality.)

Crucial asymmetry — there is NO matching Janson-type upper-tail bound. Janson's inequalities bound only $\mathbb P(X\text{ too small})$ (nonexistence / lower tail). The corresponding *upper*-tail question ($\mathbb P(X\ge(1+\delta)\mathbb EX)$, e.g. many more triangles than expected) is genuinely harder and is governed by different, much more delicate large-deviation machinery — the true rate was pinned down only recently (Harel–Mousset–Samotij 2022, building on Chatterjee–Varadhan 2011, Chatterjee–Dembo 2016, Lubetzky–Zhao 2017; Zhao Ch. 8.2, Example 8.2.4 and Theorem 8.2.5, read in full). This asymmetry is itself a key fact to remember when recombining the technique: reach for Janson only for lower-tail/nonexistence claims.

Vu's concentration inequality for polynomials (Kim–Vu; the "average Lipschitz coefficient" method) — V. H. Vu, "Concentration of Non-Lipschitz Functions and Applications," *Random Struct. Algorithms* 20(3) (2002) 262–316, read pages 262–275 in full; original, less general form: J. H. Kim, V. H. Vu, "Concentration of multivariate polynomials and its applications," *Combinatorica* 20(3) (2000) 417–434. Setting: a hypergraph $H=(V,E)$ with $V=\{1,\dots,n\}$, every edge of size $\le k$, mutually independent indicator variables $t_i$ with $\mathbb E t_i=p_i$, and $Y=\sum_{e\in E} w_e\prod_{i\in e}t_i$ a degree-$\le k$ polynomial with positive coefficients $w_e$. For a vertex set $A$ with $|A|\le k$, let $Y_A$ be $Y$'s "partial derivative" — the sum of monomials containing $A$, with those variables stripped out — and $\mathcal Y_j(Y)=\max_{|A|\le j}\mathbb E[Y_A]$ (heuristically: the *average*, not worst-case, effect of a group of $\ge j$ atom variables on $Y$). Theorem (Kim–Vu, Vu Thm 4.1): for each fixed $k$ there are constants $a_k,b_k$ such that for all $\lambda>0$, $$\mathbb P\Big(|Y-\mathbb E Y|\ge a_k\lambda^k\sqrt{\mathcal Y_0(Y)\,\mathcal Y_1(Y)}\Big)\;\le\; b_k\, e^{-\lambda/4+(k-1)\log n}.$$ The point: this gives a two-sided (not just lower-tail) exponential concentration bound for polynomials whose *worst-case* Lipschitz coefficient (needed by Azuma/Talagrand) is far too large to give any nontrivial bound, provided the *average* effect of a small group of variables ($\mathcal Y_1(Y)$) is small — replacing "global smoothness" by "average smoothness" as the operative hypothesis (Vu §3.1, "Our Main Ideas"). A later, sharper, non-binary-variable generalization (Vu Thm 4.2) replaces the $\lambda^k$ dependence by an essentially-$\sqrt\lambda$ (sub-Gaussian-type) tail under a technical majorization condition on the successive derivative bounds $\mathcal Y_j$.

Facts

- Why Janson's inequality was invented. First announced by S. Janson at the 1987 Poznań "Random Graphs '87" conference, directly in response to B. Bollobás's newly announced estimate for the chromatic number of $G(n,1/2)$ — the community needed a tool giving *exponential*, not just polynomial (Chebyshev/second-moment), decay for nonexistence probabilities of dependent structures. Janson's original proof used moment-generating-function/analytic interpolation; Łuczak found an alternative martingale proof; Boppana and Spencer (1989) found a proof using only the Harris/FKG correlation inequality (this is the proof reproduced, with a Warnke modification, in Zhao's notes above) — three structurally different proofs of the same theorem is itself a signal of how central the result is. (en.wikipedia.org/wiki/Janson's_inequality; Zhao Remark 8.1.4.) - Canonical worked example: $G(n,p)$ triangle-freeness (Zhao §8.1–8.2, read in full). With $X=$ number of triangles, $\mu\asymp n^3p^3$, $\Delta\asymp n^4p^5$ (from pairs of triangles glued along a shared edge). For $p=o(n^{-1/2})$, $\Delta=o(\mu)$ and Janson I gives the *exact* asymptotic $\mathbb P(G(n,p)\text{ triangle-free})=e^{-(1+o(1))n^3p^3/6}$ — in particular $\lim_{n\to\infty}\mathbb P(G(n,c/n)\text{ triangle-free})=e^{-c^3/6}$, matching the fact that the triangle count itself converges to a $\mathrm{Poisson}(c^3/6)$ distribution (the Poisson paradigm made literal). For $p\gg n^{-1/2}$, $\Delta\gg\mu$ and Janson II gives $\mathbb P(\text{triangle-free})\le e^{-\Theta(n^2p)}$, matching (up to constants) the trivial lower bound from "$G(n,p)$ is empty," $e^{-\Theta(n^2p)}$ — so the two regimes meet and $\mathbb P(G(n,p)\text{ triangle-free})=\exp(-\Theta(n^2p))$ for $p\gtrsim n^{-1/2}$, $\exp(-\Theta(n^3p^3))$ for $p\lesssim n^{-1/2}$ (Zhao Thm 8.1.10). - Bollobás's chromatic-number theorem, the motivating application. $\chi(G(n,1/2))\sim n/(2\log_2 n)$ whp (Bollobás 1988). The *lower* bound $\chi\ge n/\alpha(G)$ needs $\alpha(G(n,1/2))\lesssim 2\log_2 n$, which itself needs a very sharp (exponential-in-$n^2$) bound on the probability that a random-graph clique number falls even a constant below its typical value — exactly the regime where second-moment methods (only polynomial decay) are too weak and Janson's exponential decay is essential (Zhao Lemma 8.3.3, using Janson II since $\Delta\ge\mu$ there). This is documented in this wiki as Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters's companion technique for the *upper*-bound half of the same theorem. - Vu's motivating obstruction: worst-case Lipschitz coefficient blowup. For $Y=$ number of triangles in $G(N,p)$, deleting a single edge $e$ can change $Y$ by as much as $N-2$ (if $e$ sits in $N-2$ potential triangles) — so $Y$'s (worst-case) Lipschitz coefficient is $\Theta(N)$, vastly larger than $\mathbb E Y=\Theta(N^{3/4})$ for $p=\Theta(N^{-3/4})$, making both Azuma's and Talagrand's inequalities vacuous. But the *expected* number of triangles through a fixed edge is only $(N-2)p^2=O(1)$ — the average effect is tiny even though the worst case is huge. Vu's Theorem 4.1, applied here, gives $\mathbb P(|Y-\mathbb EY|\ge\varepsilon\mathbb EY)\le e^{-\Theta(N^{1/8})}$ (Vu §4.1, worked example, read in full) — much weaker in exponent than what Janson gives for the *lower* tail alone in the same regime, but crucially two-sided and applicable to polynomials generally, not just monotone containment events. - Vu's inequality is the general-purpose, two-sided complement to Janson's containment-specific, lower-tail-only inequality. Janson requires the target statistic to be literally a sum of indicators of "does $S_i\subseteq R$" events (a very specific combinatorial shape, but one that gives the sharpest possible constants, as in the triangle-free example above). Vu's/Kim–Vu's inequality applies to *any* bounded-degree polynomial of independent $[0,1]$-valued random variables, handles both tails at once, but pays for that generality with a weaker (still exponential, but larger-exponent) bound in cases where Janson also applies. In practice the two are used together: Janson for the sharpest lower-tail/nonexistence estimate, Vu (or Kim–Vu) for the matching or complementary upper-tail/two-sided estimate the same construction needs. This is exactly the combination used in the Erdős–Tetali theorem below. - Direct Erdős-problem-cluster application: the Erdős–Tetali theorem on economical additive bases. Erdős, P.; Tetali, P., "Representations of integers as the sum of $k$ terms," *Random Structures & Algorithms* 1(3) (1990) 245–261, proves that for every fixed order $h\ge2$ there is a set $B\subseteq\mathbb N$ with representation function $r_{B,h}(n)\asymp\log n$ for all large $n$ (an "economical"/thin basis). The proof: build a random set $\omega$ with $\Pr(n\in\omega)=C\,n^{1/h-1}(\log n)^{1/h}$ (the density solving $\mathbb E[r_{\omega,h}(n)]\asymp\log n$), then control the lower tail of $r_{\omega,h}(n)$ — the danger that some particular $n$ gets zero representations, which would break "basis" entirely — via Janson's inequality (the representation-counting indicators for tuples summing to $n$ form exactly a dependency-graph-indexed sum, dependent only when two tuples share a coordinate), and controls the matching upper tail/two-sided concentration via Vu's polynomial-concentration inequality, then closes with Borel–Cantelli across all $n$ simultaneously to get an almost-sure, uniform statement. See erdos/erdos-tetali-economical-bases for the full write-up of this construction, and Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ for the still-open Erdős–Turán-family questions this existence result is adjacent to. - Standard textbook home. N. Alon, J. H. Spencer, *The Probabilistic Method*, Wiley — Ch. 8 is literally titled "The Poisson Paradigm" and covers Janson's inequality as its centerpiece (title/chapter corroborated via WebSearch, matching S. Janson, T. Łuczak, A. Ruciński, *Random Graphs*, Wiley (2000), whose table of contents likewise groups "the method of moments," "Janson's inequality," "Poisson approximation," and "Stein's method: the Poisson case" together as one coherent toolkit).

Technique

When it applies. You have (or can construct) a random combinatorial object (a random subset of $\mathbb N$ or $[N]$, a random graph $G(n,p)$, a random coloring, etc.) and a target statistic $X$ that is a sum of indicator (or low-degree polynomial) variables built from that randomness, and you want to show: 1. $X>0$ with probability tending to $1$ — or, sharper, $\mathbb P(X=0)$ decays exponentially (not just polynomially, which is all the second-moment method gives) — this is Janson's regime; or 2. $X$ concentrates two-sidedly around its mean $\mathbb E X$, but $X$'s worst-case Lipschitz coefficient is too large for Azuma/McDiarmid/Talagrand to give a nontrivial bound (a single "bad" coordinate could move $X$ enormously, even though this is rare) — this is Vu's/Kim–Vu's regime.

Why it works — the mechanism. - *Janson*: Boppana–Spencer's proof (reproduced with a Warnke fix in Zhao's notes) writes $\mathbb P(X=0)=\prod_i(1-r_i)$ with $r_i=\mathbb P(A_i\mid A_1\cdots A_{i-1})$, then lower-bounds each $r_i\ge\mathbb P(A_i)-\sum_{j<i,\,j\sim i}\mathbb P(A_iA_j)$ using the Harris/FKG inequality Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) (each $A_i$ is an increasing event; the events already-excluded split into an increasing part $D_1$ and decreasing part $D_0$, and Harris lets you drop the conditioning on $D_0$ at the cost of only the "dependent-neighbor" correction term). Summing and exponentiating $\prod(1-r_i)\le e^{-\sum r_i}$ gives $e^{-\mu+\Delta/2}$. The mechanism is thus: turn a hard joint-nonoccurrence probability into a product of single-step conditional probabilities, and use a correlation inequality to show conditioning on "far away" (non-overlapping) exclusions barely helps — dependency only costs you the $\Delta$ term, which is small exactly when overlaps between potential occurrences are rare. - *Vu*: the "average smoothness" idea (Vu §3.1) — instead of a single global Lipschitz bound $C=\max_{i,x,t}|Y(t\mid t_i=x)-Y(t\mid t_i\ \text{removed})|$, track $C(t)$ as a *function of the realization* $t$, split $\Omega$ into a "good" region (where a *local* averaged version of $C$, called $V(t)$, stays small) and a small-measure "bad" region, approximate $Y$ by a function $Y'$ that agrees with $Y$ on the good region and is deliberately flattened on the bad region (so $Y'$ is now genuinely Lipschitz-bounded and a martingale/Azuma-type argument, Vu's Lemma 3.1, applies to it), and then bound $\mathbb P(Y\ne Y')$ by bounding the measure of the bad region *inductively on the polynomial's degree* — since the partial derivatives $Y_A$ that define "badness" are themselves lower-degree polynomials of the same shape. The mechanism is thus: replace a hard global smoothness hypothesis by an easy-to-verify smoothness-on-average hypothesis (bounding expectations of partial derivatives, not their worst case), pay for the gap with a separately-bounded small "bad event," and close the induction by degree.

The reusable recipe (synthesized from both sources, and matching the Erdős–Tetali application): 1. Reverse-engineer the density/parameter. Choose the inclusion-probability (or other random-construction parameter) so that $\mathbb E[X]$ for the target statistic $X$ lands exactly on the conjectured critical/threshold growth rate (e.g. $p=\log n/n$ for connectivity-type problems; $\Pr(n\in\omega)=Cn^{1/h-1}(\log n)^{1/h}$ for order-$h$ economical bases). This is a routine linearity-of-expectation computation. 2. **Recognize $X$ as a sum over a large, *dependent* family of local indicator events** (containment of small witness sets $S_i$ in a random set $R$; occurrence of small subgraphs; tuples summing to a target $n$) where dependency is governed by *overlap* between the witnesses. 3. Bound the dependency parameter $\Delta$ (sum over overlapping pairs of $\mathbb P(A_i\cap A_j)$) and compare it to $\mu=\mathbb EX$: if $\Delta=o(\mu)$, Janson I gives the sharp asymptotic $\mathbb P(X=0)=e^{-(1+o(1))\mu}$; if $\Delta\gtrsim\mu$, fall back to Janson II/III for a weaker but still exponential bound. 4. For two-sided or non-monotone-event control (or when the statistic isn't literally a containment-indicator sum but a more general low-degree polynomial), reach for Vu's/Kim–Vu's inequality instead: identify the polynomial's degree $k$, compute the "average derivative" parameters $\mathcal Y_j(Y)=\max_{|A|\le j}\mathbb E[Y_A]$ for $j=0,\dots,k-1$ (these are almost always much smaller than the worst-case Lipschitz coefficient, exactly because "a single bad coordinate" is a rare event), and plug into Theorem 4.1/4.2 for an exponential two-sided tail bound. 5. Combine Janson (lower tail / nonexistence) with Vu (upper tail / two-sided) when both directions are needed simultaneously — this is the standard "Poisson paradigm" combination for a full concentration statement, as in the Erdős–Tetali basis construction. 6. Close with a union bound / Borel–Cantelli across the whole family of targets (all $n$, not just one) when the goal is an almost-sure or uniform-in-$n$ statement rather than a single high-probability event — summing the per-target failure probabilities from steps 3–4 and checking summability. 7. Watch the asymmetry. Janson's machinery gives *no* comparably strong upper-tail bound "for free" — the true upper-tail large-deviation rate for e.g. triangle counts required decades of separate development (Kahn–DeMarco/Chatterjee 2012 existence of the phenomenon, Harel–Mousset–Samotij 2022 for the sharp constant) and is not part of this toolkit; if the problem specifically needs a sharp upper tail, this concept is necessary-but-not-sufficient and points toward large-deviation-theory machinery instead.

What this technique does NOT give: a sharp *upper*-tail bound (see above); it also does not by itself supply the combinatorial insight for step 1 (choosing the right random model/parameter) or step 2 (identifying the right dependency structure) — those remain problem-specific, the same way Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem)'s expectation-threshold $q(\mathcal F)$ must still be computed by hand before the black-box theorem applies.

Related

- Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the more elementary Chebyshev/Paley–Zygmund ancestor of this family: gives only polynomial-decay (not exponential) control on $\mathbb P(X=0)$, and no two-sided control at all; Janson/Vu are reached for precisely when this weaker tool isn't sharp enough (e.g. Bollobás's chromatic-number theorem needs Janson's exponential decay, not second-moment's polynomial decay). - Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — the correlation inequality that powers the Boppana–Spencer proof of Janson's inequality (increasing events $A_i$, $D_1$; decreasing "already-excluded" event $D_0$). - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — the Azuma–Hoeffding/McDiarmid martingale toolkit that Vu's inequality is explicitly designed to outperform when the Lipschitz coefficient is too large (worst-case-smoothness vs. average-smoothness, the central contrast documented on both pages). - Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) — a structurally different, more modern "black-box" route to threshold-location results (up to a universal log factor) that in many cases replaces what used to require a bespoke Janson/Vu computation; the two techniques are complementary (Kahn–Kalai/Park–Pham for the *order of magnitude* of a threshold, Janson/Vu for the *sharp constant* once the threshold's scale is known). - Additive representation function $r_{B,h}(n)$ — $r_{B,h}(n)$, the statistic whose lower-tail (nonexistence) and two-sided concentration are controlled by exactly this Janson-then-Vu combination in the Erdős–Tetali construction. - erdos/erdos-tetali-economical-bases — the canonical worked application in this wiki: existence of order-$h$ additive bases with $r_{B,h}(n)\asymp\log n$, proved by random-set construction + Janson (lower tail) + Vu (two-sided) + Borel–Cantelli. - Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ — the still-open Erdős–Turán-family "forcing" questions adjacent to the Erdős–Tetali existence result; any attack on them starts from understanding this construction toolkit.