================================================================================ THE SECOND KAHN-KALAI CONJECTURE An honest, complete, and friendly proof tour (improved v2: plainer English, all the hard steps kept, no hand-waving) ================================================================================ AUTHORS: OpenAI DATE: 2026-09-24 THIS FILE: second_kahn_kalai_v2.txt ORIGINAL: second_kahn_kalai_original.txt -------------------------------------------------------------------------------- WHO IS THIS FOR? -------------------------------------------------------------------------------- This paper has one clear idea and a lot of technical machinery around it. This version keeps every hard step of the proof, but says each step in plain English first, then does the algebra. A reader who knows: * what a graph is (vertices, edges, subgraphs), * what probability means (a coin flip, an expectation), * basic binomial coefficients like C(n, k) = "n choose k", * the fact that sum_{m>=1} e^{-7m} is tiny, can follow the whole thing. Nothing about random graphs, threshold theory, or the earlier Kahn-Kalai conjectures is assumed; we build it from scratch. If you are pressed for time on a first pass, you can read Parts 1, 2, 3, 4, 9, and 10 and skip the proof of Parts 5, 6, 7, 8. But the whole point of this version is that the proof parts are readable, so come back. -------------------------------------------------------------------------------- THE BIG IDEA IN ONE SENTENCE -------------------------------------------------------------------------------- A graph H shows up in a random graph about as soon as every subgraph of H has a decent expected number of copies, up to a factor of one logarithm of the number of edges of H. That is the second Kahn-Kalai conjecture, and we prove it with an explicit constant. -------------------------------------------------------------------------------- A HEALTHY EXAMPLE BEFORE ANY DEFINITIONS -------------------------------------------------------------------------------- Take a coin, flip it for every possible edge on 100 labelled points, and keep only the edges where the coin says heads. Each edge independently survives with probability p. The result is the "random graph G(n, p)" with n = 100. If p is very small almost no edges survive; if p is very close to one almost every edge survives. At some middle probability a given shape (a triangle, a cycle, anything) starts appearing with probability half. Theorem (very informal, stated properly below): if at level p every subgraph of the target graph has at least a 50% chance in expectation of appearing, then H already appears with probability at least 1/2 at a value of p that is at most a constant times p times (1 plus log base 2 of the number of edges of H). That constant is 2048 e^50, absurdly large by design, but finite and explicit. The whole paper is a proof of that sentence. ================================================================================ PART 1. RANDOM GRAPHS AND THE TWO THRESHOLDS ================================================================================ 1.1. Random graphs. ------------------------------------------------------------ Fix a positive integer n >= 2. Think of the n points {1, 2, ..., n} as "vertices". Every unordered pair of distinct vertices is a possible "edge"; there are C(n, 2) = n(n-1)/2 such pairs. Choose a number p with 0 <= p <= 1. Independently for each pair, keep the edge with probability p and throw it away with probability 1-p. The set of kept edges is called G(n, p), the Erdos-Renyi random graph. Every question about random graphs has the shape "what is the chance of event E as a function of n and p?". We will care about the event that H shows up. 1.2. Copies of a target graph. ------------------------------------------------------------ Let H be a fixed finite graph without loops (it may be drawn with repeated edges in the original source, but here we forbid that; the paper only ever uses simple graphs anyway). For a host graph G and a finite simple graph F, write N(G, F) = the number of subgraphs of G that are isomorphic to F. Two words need care. * "subgraph" (the one used here) means: pick a set of vertices, pick a set of edges, all from G, and look at the resulting small graph. Extra edges between the chosen vertices are allowed to exist in G; they are just not part of the chosen subgraph. Sometimes people write this as "not necessarily induced", and the word "ordinary copy" means the same thing. If instead you insist on all possible edges, it is "induced"; we never need that. * "isomorphic" means "same shape up to relabelling vertices". For instance a triangle and any other triangle of three points are the same shape, so they count once each as a copy. A useful formula: for a fixed edge-free graph F with v vertices and e edges, the number of copies inside the complete graph K_n is N(K_n, F) = (n)_v / |Aut(F)|, where (n)_v = n(n-1)...(n-v+1), and |Aut(F)| is the number of vertex permutations that preserve F's adjacency. The reason (n)_v counts injective maps {vertices of F} -> {1..n}, and the quotient collapses maps that only relabel an automorphism; the quotient is exact because F has no possible extra edges to worry about. When we multiply by p^e we get the expected number of copies in G(n, p): E N(G(n, p), F) = N(K_n, F) * p^{e(F)}. 1.3. The two "thresholds". ------------------------------------------------------------ Two numbers competes for the reader's attention. p_c(n, H), the containment threshold: p_c(n, H) = inf{ p in [0, 1] : P( N(G(n, p), H) > 0 ) >= 1/2 }. This is the smallest p at which G(n, p) contains at least one copy of H with probability at least 1/2. It is what a "when does H appear?" question really asks. p_E(n, H), the (graph) expectation threshold: p_E(n, H) = inf{ p in [0, 1] : E N(G(n, p), F) >= 1/2 for every subgraph F of H }. Here "subgraph F of H" means: an edge subset of H on a subset of V(H). We require this for every such F, including H itself. Both infima are attained. For p_c: P(N(G(n,p),H) > 0) is a continuous function of p on [0,1], equals 0 at p = 0, equals 1 at p = 1. For p_E: only finitely many constraints matter and each is continuous. In both cases a linear-in-p^e form of the constraint means we can solve the threshold by hand, but we do not need the formula. The basic inequality is one line: p_E(n, H) <= p_c(n, H). If P(N(G(n,p),H) > 0) >= 1/2, then with that same p every subgraph F of H also appears with probability >= 1/2 (because F sits inside H). On the event of appearing, the number of copies of F is at least 1, so E N(G(n,p), F) >= P(N(G(n,p), F) > 0) >= 1/2. Hence p satisfies the constraint for p_E, and every p that works for p_c is a legal candidate for p_E, so p_E <= p_c. That inequality is easy and trivially true. The opposite inequality (up to a factor) is the deep thing. This paper proves it. -------------------------------------------------------------------------------- PART 1.5. WHY THE CONVENTION "ONE HALF" DOES NOT MATTER -------------------------------------------------------------------------------- Kahn and Kalai used expected count 1 instead of 1/2, giving a number q(n, H) instead of p_E(n, H). For every subgraph with r >= 1 edges the expected count scales as p^r, so changing the requirement from 1 to 1/2 is the same as replacing p by p * 2^{-1/r}, which is between 1/2 and 1 times the original p. Thus the two thresholds are within a factor of 2 of each other. Our proof would work with either, up to a small change of constant. We stick with 1/2 because the proof uses it cleanly. ================================================================================ PART 2. THE MAIN THEOREM ================================================================================ 2.1. Statement. ------------------------------------------------------------ THEOREM (Second Kahn-Kalai, main result of this paper). For every n >= 2 and every finite simple graph H with an edge count h = e(H) >= 1 and at most n vertices: p_c(n, H) <= min{ 1, 2048 * e^50 * p_E(n, H) * (1 + log_2 h) }. Here e is the base of natural logarithms, log_2 is base-2 logarithm. In particular, using log_2 h <= log_2 C(n, 2) <= log_2 (n^2) <= 2 log_2 n and 1 <= log_2 n for n >= 2: p_c(n, H) <= 6144 * e^50 * p_E(n, H) * log_2 n. The constants 2048 e^50 and 6144 e^50 are absurdly large. They are explicit and universal. The "second Kahn-Kalai conjecture" is exactly the claim that such a bound holds with a logarithm in h alone (rather than, say, log^2 n or log^3 n). This theorem settles that. 2.2. Two sanity checks. ------------------------------------------------------------ Check 1. The right-hand side is never above 1 because of the min{1, .}. Check 2. If H is connected, e(H) is at most C(v(H), 2) = v(H)(v(H)-1)/2, so the log is bounded by 2 log_2 v(H) <= 2 log_2 n. So the theorem says nothing strange: p_c and p_E really are within a logarithmic factor of each other even when H itself grows with n. 2.3. Some small examples. ------------------------------------------------------------ Example (a single edge). Let H = K_2, one edge. Then any subgraph F of H is either empty (that constraint is trivially satisfied) or a single edge. E N(G(n, p), K_2) = C(n, 2) * p. So p_E(n, K_2) = (1/2) / C(n, 2), give or take. Meanwhile a single edge appears with probability at least 1/2 when 1 - (1-p)^{C(n,2)} >= 1/2, so 1 - e^{-p C(n,2)} >= 1/2, so p >= ln 2 / C(n, 2) roughly. Thus p_c(n, K_2) = Theta(1 / n^2) matching p_E(n, K_2) = Theta(1 / n^2) up to a universal constant. The log_factor is trivially 1 (since h = 1, 1 + log_2 h = 1). Example (a triangle). Let H = K_3, three vertices, three edges. Then the edge subgraphs of K_3 are: single edge, path of length 2 (2 edges), and K_3 (3 edges). E N(G(n, p), K_3) = C(n,3) * p^3, E N(G(n, p), P_3) = number of length 2 paths * p^2 = 3 C(n,3) p^2, E N(G(n, p), K_2) = C(n,2) p. The p_E threshold is the *largest* of the three, because the constraints must all be satisfied simultaneously: * single edge: p * C(n,2) >= 1/2 so p >= 1/(2 C(n,2)) = Theta(n^-2) * path P_3: p^2 * 3 C(n,3) >= 1/2 so p >= Theta(n^{-3/2}) * triangle K_3: p^3 * C(n,3) >= 1/2 so p >= Theta(n^{-1}) The largest lower bound is Theta(n^{-1}), forced by the triangle constraint itself. So p_E(n, K_3) = Theta(n^{-1}). What about p_c(n, K_3)? Classic Erdos-Renyi, via a union bound plus a second-moment calculation, gives p_c(n, K_3) = Theta(n^{-1}). So for the triangle p_c and p_E agree up to a constant. The factor 1 + log_2 3 ~ 2.6 is tiny, as expected. More generally, for a target that is NOT "spanning" -- whose edges can be placed on n points without any need for every point to appear -- the relationship p_c ~ p_E up to a constant is very common. The logarithm is really needed for the SPANNING targets, which is what Part 2.5 is about. (Constants 2048 e^50 are enormous but universal; the example above is about orders of magnitude n^k, not about the exact constants.) ================================================================================ PART 2.5. WHY A LOGARITHM REALLY IS NECESSARY ================================================================================ The factor (1 + log_2 h) is not a byproduct of laziness. Here is why even the very best exponent of the log cannot be a constant. Example (perfect matching). Let n be even, and let H be a perfect matching on n vertices (so n/2 disjoint edges). This H has e(H) = n/2 edges and v(H) = n vertices. What is p_E(n, H)? E N(G(n, p), H) = (1 * 3 * 5 * ... * (n-1)) * p^{n/2}, because a perfect matching on labelled vertices can be built by choosing the partner of vertex 1 (n-1 choices), then partner of the smallest unmatched vertex (n-3 choices), and so on, giving (n-1)(n-3)...1. You need this >= 1/2, so p_E(n, H) = Theta( n^{-1} * ( 1 / (1 * 3 * 5 * ... * (n-1)) )^{2/n} ) = Theta(1/n). Actually computing it cleanly: (n-1)!! is about sqrt(2) (n/e)^{n/2}, so (n-1)!! p^{n/2} >= 1/2 forces p = Theta(1/n). What is p_c(n, H)? For G(n, p) to contain a perfect matching, every vertex must have at least one incident edge. This needs p >= (log n + omega(1)) / n: each vertex is isolated with probability (1-p)^{n-1}, and by union bound the number of isolated vertices is roughly n e^{-pn}; making this zero requires pn = log n + omega(1). Conversely a matching exists when the minimum degree is at least 1 (actually at least 2, by a two-line argument that forbids a Hall violator); so p_c(n, H) = Theta(log n / n). So: p_c(n, H) / p_E(n, H) = Theta( log n ). Here e(H) = n/2, so 1 + log_2 h = Theta(log n). The theorem's logarithm factor is at the right order of magnitude for this example. No constant factor could ever suffice. The same gap appears for Hamilton cycles, and more generally for "spanning targets" (targets whose vertex set can be forced to hit every host vertex). That "one missing vertex is enough to break the target" phenomenon is exactly what p_E cannot see and what the log pays for. ================================================================================ PART 3. HOW WE GOT HERE: THE KAHN-KALAI HISTORY TOLD QUICKLY ================================================================================ We only need the history to explain what is new in this paper. Skip if you just want the theorem. 3.1. Abstract setting: increasing families. ------------------------------------------------------------ Let X be a finite set (think of X as all possible edges of a large graph). A family F of subsets of X is "increasing" if S in F and S subset T implies T in F. Think: "contains at least one triangle of edges", "contains a perfect matching", and so on. An independent random p-subset of X, written X_p, picks each element of X with probability p independently. The containment probability is P(X_p in F). Define three kinds of threshold for an increasing family F. * p_c(F) = inf{ p : P(X_p in F) >= 1/2 }. The true threshold. * q(F) = sup{ p : there is a cover G of F by small subsets with cost sum_{S in G} p^{|S|} <= 1/2 }. The integral expectation threshold. "Cover" means every member of F contains some S in G. Cost = sum of p^{|S|}, i.e. the expected number of cover sets inside X_p. If the cost is <= 1/2, union bound says P(F) is at most 1/2, so p_c >= p. * q_f(F) = same as q but with a fractional cover: weights w_S >= 0 with sum_{S subset A, S in support} w_S >= 1 for every A in F, and cost sum_S w_S p^{|S|} <= 1/2. Allowing fractional weight only enlarges the set of covers, so q_f(F) >= q(F). Then q(F) <= q_f(F) <= p_c(F). The question is: is this reversed, up to a logarithm of the size of the largest minimal member of F? Kahn and Kalai (2007) conjectured p_c(F) <= C q_f(F) * log(|X|). That is the FIRST Kahn-Kalai conjecture, the "fractional" version. Frankston-Kahn-Narayanan-Park (2021) proved a strong bound p_c(F) <= C q_f(F) * log(|largest minimal member of F|). Alweiss-Lovett- Wu-Zhang (2021), building on Lovett-Solomon-Zhang (2019), gave the fragment method that underlies it. Park-Pham (2024) resolved the integral version p_c(F) <= C q(F) * log(...) with a "minimum fragmentation" argument. OpenAI (2026) proved integral and fractional thresholds are within a universal factor of each other at the common one-half budget, and Dubroff- Kahn-Park (2025) re-examined the puzzle for the specific graph setting of this paper. But all these are ABSTRACT results. They only get p_c(F) <= C q(F) log, and q(F) <= q_f(F) <= p_c(F), so p_c(F) is squeezed between q(F) and C q(F) log. In the graph case, q(F_H) is not p_E(n, H): it has extra copy-count weights N(H, F) baked in, and relating q(F_H) to p_E(n, H) is a separate problem that we now explain. 3.2. The graph-specific gap. ------------------------------------------------------------ Let F_H = { E subset of the edges of K_n : E contains a copy of H }. A "cover" of F_H by small subsets can be generated from copies of any one subgraph F of H: every graph containing H also contains every subgraph F, so the collection of copies of F covers F_H. Cost of that natural cover is roughly E N(G(n, p), F). Therefore q(F_H) <= p_E(n, H), and since q_f(F_H) >= q(F_H), we know q_f(F_H) is somewhere in [p_E(n, H), p_c(n, H)] and the abstract theorem does not by itself say that q_f(F_H) <= C p_E(n, H) * log. Mossel-Niles-Weed-Sun-Zadik (2022) found that q_f(F_H) is actually ***equal to*** the "modified" threshold widetilde p_E(n, H) = min{ p : E N(G(n, p), F) >= N(H, F) / 2 for every F subset H }. The factor N(H, F) is the number of copies of F inside H itself: containing H "supplies" all those copies at once. Then they proved (via spread arguments, see below) that p_c(n, H) <= C widetilde p_E(n, H) * log n = C q_f(F_H) * log n. That was the first proof of a single logarithm in the graph setting, but it was in terms of widetilde p_E rather than the honest p_E. Comparing the two is the extra work. Dubroff-Kahn-Park (2025) then proved q_f(F_H) = O(p_E(n, H) * log^2 n) and p_c = O(p_E * log^3 n), using a "rooted-extension" decomposition. They also proved the desired single-log bound p_c = O(p_E * log) when p_E is smaller than 1/(3n). Tran (2026) improved the comparison: q_f(F_H) = O(p_E * log(2 e(H))) and p_c = O(p_E * log^2(2 e(H))). He also removed one of the log factor for trees and for graphs whose average degree is at least the logarithm of the maximum degree. His ratio-maximizing-core construction is used below with explicit constants. 3.3. What is new here: the single-log factor, uniformly. ------------------------------------------------------------ This paper removes the extra log. It proves p_c(n, H) <= 2048 e^50 p_E(n, H) (1 + log_2 h) directly. The main new idea: do all the per-level work on a fixed tree of possibilities, with a single product-sample W, so that one "spread" of W handles every level at once. The price is a factor of 16 e^50 per level, which compounds to a factor of (16 e^50)^{log_2 h} = h^{log_2(16 e^50)} per level, but because the levels are exponentially growing in size, this geometric sum collapses to a single logarithm of h -- not of n -- and matches the perfect-matching gap. Fine print: we prove p_c <= 2048 e^50 p_E (1 + log_2 h). Since 1 + log_2 h <= 3 log_2 n for n >= 2 and h <= C(n,2) <= n^2, the constant 6144 e^50 follows. ================================================================================ PART 4. THE PLAN, IN ONE PARAGRAPH ================================================================================ We prove the theorem by proving three separate lemmas, each of which we can state, prove, and sanity check on its own. Module A (Part 5, "resampling"). Suppose you have a family of small sets A_b, each with a spread distribution nu. Plant a random source A_c inside a product sample W of density rho, then resample a target A_b "close to W" according to the posterior. On most draws the leftover T = A_b \ W is at most half the size of the labels A_b, and the distribution of T is still spread (with a slightly worse constant). Also, if you look only at coordinates OUTSIDE a specific target A_b, then conditioning on T uses a bounded fraction of the mass. This is the MNSZ posterior-resampling step, with the "outside" bound made explicit because we will reuse it. Module B (Part 6, "cover a tree"). Suppose you have a probability tree whose edge labels are disjoint along every path, whose size grows by at least a factor 16 every level, and whose every level is spread with parameter sigma. Then a single independent random subset W of X of density r = 16 e^50 sigma (1 + log_2 ell_k) contains ALL the labels of some full path, with probability at least 2/3. The proof runs Module A simultaneously at every node of the tree using the same W, with a bookkeeping potential that controls the global effect. Module C (Part 7, "graph hierarchy"). Suppose H has at most n vertices and e(H) = h edges. Then there is a probability tree as in Module B, with sigma = 128 p_E(n, H) and label sizes 1 <= ell_1, ell_{i+1} >= 16 ell_i, ell_k <= h, whose paths' unions are exactly the copies of H on [n]. The construction repeatedly picks, for each current edge set I, a maximizing edge subset S subset I by maximizing sigma^{-|S|} P(S_0 subset I). The first-moment constraints force S to be at most 1/17 of I. The maximality itself then gives the spread parameter for the child distribution. In Part 8 we glue: apply Module B to the tree from Module C with sigma = 128 p_E to get a value p, then compare p to the theorem's stated r = min{1, 2048 e^50 p_E (1 + log_2 h)}, and note that a Bernoulli-p set with p >= r contains a copy of H with probability at least 2/3 >= 1/2. This architecture is what makes the proof complete. Each module is a self-contained lemma. All the numeric slack is in the statement of A and B, and there is a fair bit of it. ================================================================================ PART 5. MODULE A: THE RESAMPLING LEMMA ================================================================================ 5.0. A picture before the algebra. ------------------------------------------------------------ Imagine you have a family of small "labels" A_b. Each label A_b is a subset of X (think of X as all possible edges of a large complete graph). Some possible labels may be empty; some may repeat. You also have a probability distribution nu over the index set B, so sum_{b in B} nu_b = 1. When you say "sample b ~ nu" you mean "sample an index b with probability nu_b". Now measure "how big" a distribution is by how likely it is to cover specific coordinates. DISTRIBUTION NU IS a-SPREAD IF, FOR EVERY NON-EMPTY J SUBSET X, P_{b~nu}( J subset A_b ) <= a^{|J|}. In words: for any specific J of size j, the chance that a random label already covers all of J is at most a^j. If a < 1, this says labels are quite "spread out"; they rarely contain any given specific set. If a near 1, labels are "dense"; a itself is basically the density. We allow the distribution to be carried by an indexed family (A_b)_{b in B}: different indices b may have identical labels A_b, and labels may be empty. If a label is empty, that index contributes nothing to any P(J subset A_b) with |J| >= 1, which is fine. Now here is the operation we want to perform repeatedly. * Fix a density rho in (0, 1). * Fix a random subset W of X of the form: each coordinate is in W with probability rho independently. We write W ~ mu_rho. * Plant a "source" label: sample a source index c ~ nu, and take the union Y = W UNION A_c. So Y is a "random superset" of W. * Resample a "target" label: given Y, choose a target index b ~ nu conditioned on Y, weighted by rho^{-|A_b|} and supported only on indices b with A_b SUBSET Y. That is, P(target = b | Y) = nu_b * rho^{-|A_b|} * 1_{A_b subset Y} / Z(Y), Z(Y) = sum_{d in B} nu_d * rho^{-|A_d|} * 1_{A_d subset Y}. The denominator Z(Y) > 0 because A_c is one of the labels, so the sum contains at least the term nu_c * rho^{-|A_c|} > 0. * Retain the "fragment": T = A_b \ W. This is the Mossel-Niles-Weed-Sun-Zadik posterior-resampling step. If you think of W as "the current set of coordinates we have already placed", the source is one *potential* answer A_c, and the target is a *new* answer A_b that is compatible with W plus A_c. Only the part of A_b that is not already in W needs to be "placed". Two facts are immediate, for every transition with positive probability: (i) T subset A_c INTERSECTION A_b. Reason: T = A_b \ W, and A_b subset Y = W UNION A_c, so every element of A_b not in W must come from A_c. So T subset A_c. And of course T subset A_b. (ii) A_b subset W UNION T. Reason: T = A_b \ W, so A_b = (A_b INTERSECTION W) UNION T subset W UNION T. This says "to reconstruct A_b, all you need is W together with the fragment T". The first inclusion will preserve the spread: since T is a subset of the source label A_c, and A_c has law nu (spread), T is a sub-random-subset of a spread set, so it is still spread with no worse constant. The second inclusion lets the algorithm recover A_b from W and T. In the tree application (Part 6), that A_b will tell us which child of a node we are committing to. 5.1. Why those posterior probabilities are posterior probabilities. ------------------------------------------------------------ Some readers will ask: why is that P(target = b | Y) formula the "right" thing? The lemma works regardless, but the reason for the formula is that it makes an alternative description of the joint law of (Y, target) come out nicely. Fix a source index c. If we sample W ~ mu_rho and put Y = W UNION A_c, then the distribution of Y is absolutely continuous with respect to mu_rho with Radon-Nikodym "density" rho^{-|A_c|} on the event A_c subset Y: P(W UNION A_c = Y) = mu_rho(Y) * rho^{-|A_c|} * 1_{A_c subset Y}. Explanation: since Y = W UNION A_c, every element of A_c must be in W (contributing a factor rho^{|A_c|} to the mu_rho mass that we "un-divide"), and every element of Y \ A_c must be in W (contributing rho^{|Y \ A_c|}) and nothing outside Y is in W (contributing (1-rho)^{...}). Multiplying both sides by mu_rho(Y) makes it a change of measure. Averaging over the source c (with probability nu_c), the density of Y relative to mu_rho becomes exactly Z(Y) as above. Bayes' rule turns this into our P(target = b | Y) formula. So the transition is a well-defined "posterior resampling": sample a source, plant it in a product set, then sample a target according to the residual posterior. At a *fixed* W, however, only the source is guaranteed to be distributed as nu. The target law can be different -- so all the guarantees below are weaker statements about the target. That is why the lemma says "with high labelled probability, non-failure" for BOTH quantities below (the failure event, and the distortion bound for f). 5.2. What can go wrong? ------------------------------------------------------------ Almost everything is going to be fine. But there is one obvious failure mode: the denominator Z(Y) might be extremely small. That means the "posterior mass" is concentrated on a very unlikely label, and P(target = b) could be much larger than nu_b. If that happens, the "resampled" target is not behaving like a random draw from nu -- it is systematically larger. Similarly, the fragment T might be much larger than expected. If T is already, say, 3/4 of A_b, then reusing W (which supposedly replaced T) gave us very little savings. The lemma controls both. Despite the label "failure", a failure is not fatal. It is a measurable event whose probability is at most e^{-9m} for the given capacity m. In the tree application, we will simply skip the failed draws. 5.3. The lemma, stated exactly. ------------------------------------------------------------ LEMMA A (Local resampling; the MNSZ lemma with an "outside" bound). Let X be a finite set. Let B be a finite index set. For each b in B let A_b subset X, and let nu be a probability distribution on B with weights nu_b > 0. Suppose: * |A_b| <= m for all b, where m is a positive integer; * nu is a-spread; * 0 < rho < 1; * a / rho <= e^{-50}. Let W ~ mu_rho be an independent sample, and perform the transition as in 5.0. Call the transition a LOCAL FAILURE if Z(Y) < e^{-10 m} OR |T| > m/2. Then the following two statements hold. (i) Probability of local failure: P(local failure) <= e^{-9 m}. (ii) Distortion bound. For every fixed target b and every nonnegative function f depending only on W INTERSECTION (X \ A_b): E[ 1_{target = b} * 1_{Z(Y) >= e^{-10 m}} * f(W) ] <= e^{11 m} * nu_b * E f(W). The expectation on the right is over W ~ mu_rho. Part (i) says: on most draws, the denominator is not tiny AND the fragment is at most half the capacity. Part (ii) says: if you only look at coordinates outside a fixed target label A_b, then "being a target" only costs you a factor of e^{11 m} in probability mass, relative to an independent W. That factor is going to be paid once per level of our tree in Part 6; the "cost of one level" is exactly e^{11 m}. 5.4. What is the role of the a/rho <= e^{-50} hypothesis? ------------------------------------------------------------ Both the intersection size bound and the distortion bound involve a geometric factor (a/rho)^|J|, and we want the sum over J to collapse. The hypothesis a/rho <= e^{-50} makes each such factor smaller than e^{-50 |J|}, which is tiny. The exponent 50 is arbitrary; any moderate constant would work, at the cost of a worse exponent in e^{11 m}. In the graph application (Part 7) we will set a = 128 p_E(n, H) and rho large enough that a/rho <= e^{-50}. Concretely, if sigma denotes the spread parameter of the tree in Part 6, we will run the tree with a = 4 sigma and rho = 4 sigma e^{50}. That gives a/rho = e^{-50}, the critical value. 5.5. Proof of the lemma, part (i): small denominator. ------------------------------------------------------------ First, compute P(Z(Y) < e^{-10 m}). The key identity: for Y ~ mu_rho, E Z(Y) = 1. Here is why. E_{W ~ mu_rho} [ sum_b nu_b rho^{-|A_b|} 1_{A_b subset W} ] = sum_b nu_b rho^{-|A_b|} P_{W ~ mu_rho}(A_b subset W) = sum_b nu_b rho^{-|A_b|} rho^{|A_b|} = sum_b nu_b = 1. So Z(Y) is a nonnegative random variable with mean 1. Now, the key change-of-measure identity. Recall: Y = W UNION A_c has density Z(Y) with respect to mu_rho. So for any nonnegative measurable g(Y): E_{Y ~ mu_rho}[ Z(Y) g(Y) ] = E_{Y}[ g(Y) ], (*) where the right-hand expectation is over the actual distribution of Y. Reason for (*): if mu_rho is a reference measure and a random variable Y has density Z with respect to mu_rho, then for any nonnegative g, E_Y[ g(Y) ] = integral g(Y) * Z(Y) d mu_rho (Y) = E_{Y ~ mu_rho}[ Z(Y) g(Y) ]. (Intuition: mu_rho-mass at Y gets "re-weighted" by Z(Y) to become the Y-law of Y. The two measures agree on event-probabilities once we correct this way.) Now, take g = 1_{Z < e^{-10 m}}. This is a function of Y, so it is legal: P( Z(Y) < e^{-10 m} ) = E_Y[ 1_{Z(Y) < e^{-10 m}} ] (definition) = E_{Y ~ mu_rho}[ Z(Y) * 1_{Z(Y) < e^{-10 m}} ] (by (*)) <= e^{-10 m} * E_{Y ~ mu_rho}[ 1_{Z(Y) < e^{-10 m}} ] (because on the indicator set, Z < e^{-10 m}; Z >= 0 always) <= e^{-10 m}. (inner E of an indicator is <= 1) That gives P( Z(Y) < e^{-10 m} ) <= e^{-10 m}. The small-denominator part of part (i) is done. The fragment-size part is 5.6. 5.6. Proof of the lemma, part (i): size of the fragment. ------------------------------------------------------------ Now, the event {|T| > m/2} on the draw of (W, c, b). Since T subset A_c INTERSECTION A_b (by inclusion (i) above), the event |T| > m/2 implies |A_c INTERSECTION A_b| > m/2. Fix a pair (c, b). Bound P( {A_b subset W UNION A_c} ) as follows. The condition A_b subset W UNION A_c is equivalent to A_b \ A_c subset W. The set A_b \ A_c has size |A_b| - |A_c INTERSECTION A_b|. By independence of W ~ mu_rho, the probability is rho^{|A_b \ A_c|} = rho^{|A_b| - |A_c INTERSECTION A_b|}. The complementary event A_b NOT subset W UNION A_c is fine (we are just upper-bounding the "successful transition" probability). We want to sum these over c ~ nu and b ~ nu, weighted by the posterior 1/Z(Y). On the event Z(Y) >= e^{-10 m}, we bound 1/Z(Y) <= e^{10 m}. Then: P( Z(Y) >= e^{-10m}, |T| > m/2 ) <= e^{10 m} * sum_{c, b} nu_c nu_b * rho^{-|A_b|} * P( A_b \ A_c subset W ) * 1_{|A_c INTERSECTION A_b| > m/2}. But P({A_b \ A_c subset W}) = rho^{|A_b \ A_c|}. Combining with the rho^{-|A_b|} from the posterior: rho^{-|A_b|} * rho^{|A_b \ A_c|} = rho^{-|A_c INTERSECTION A_b|}. So: P( Z(Y) >= e^{-10m}, |T| > m/2 ) <= e^{10 m} * sum_{c, b} nu_c nu_b * rho^{-|A_c INTERSECTION A_b|} * 1_{|A_c INTERSECTION A_b| > m/2}. Now use spread: for a fixed b, and R = |A_c INTERSECTION A_b|, P_{c ~ nu}( R = r ) <= sum_{J subset A_b, |J| = r} P( J subset A_c ) <= C(m, r) * a^r. (This is the "intersection bound": {R >= r} corresponds to {some r-subset of A_b is contained in A_c}, and by union bound over C(m, r) r-subsets, each of which has probability <= a^r by spread.) So doing the c-sum first: sum_c nu_c * rho^{-|A_c INTERSECTION A_b|} * 1_{|A_c INTERSECTION A_b| > m/2} <= sum_{r > m/2} C(m, r) a^r * rho^{-r} = sum_{r > m/2} C(m, r) (a/rho)^r <= sum_{r > m/2} C(m, r) (a/rho)^{m/2} <= 2^m * (a/rho)^{m/2}. (The step to (a/rho)^{m/2} uses r > m/2 and a/rho < 1. The step to 2^m * (a/rho)^{m/2} uses C(m, r) <= 2^m.) With a/rho <= e^{-50}: (a/rho)^{m/2} <= e^{-25 m}. So: P( Z(Y) >= e^{-10m}, |T| > m/2 ) <= e^{10 m} * (sum_b nu_b) * 2^m * e^{-25 m} = e^{10 m} * 2^m * e^{-25 m} = e^{-15 m + m log 2} <= e^{-14 m}. Adding the small-denominator bound e^{-10 m}: P(local failure) <= e^{-10 m} + e^{-14 m} <= e^{-9 m}. (Check for m >= 1: e^{-10 m} + e^{-14 m} = e^{-9 m} * (e^{-m} + e^{-5 m}) <= e^{-9 m} * (e^{-1} + e^{-5}) ~ 0.373 * e^{-9 m}, well under the promised e^{-9 m}. Part (i) is done.) 5.7. Proof of the lemma, part (ii): distortion bound. ------------------------------------------------------------ Now fix a target index b and a nonnegative function f(W) that depends only on W INTERSECTION (X \ A_b). We want E[ 1_{target = b} * 1_{Z(Y) >= e^{-10 m}} * f(W) ] <= e^{11 m} * nu_b * E f(W). We proceed by the exact chain in the original. Bound 1/Z(Y) <= e^{10 m} on the event Z >= e^{-10 m}, and average over source c, target b: E[ 1_{target=b, Z>=e^{-10m}} f(W) ] <= e^{10 m} * nu_b * sum_c nu_c * rho^{-|A_b|} * E[ 1_{A_b \ A_c subset W} f(W) ]. Key claim: E[ 1_{A_b \ A_c subset W} f(W) ] = rho^{|A_b \ A_c|} * E f(W). Reason: the event {A_b \ A_c subset W} only involves coordinates in A_b \ A_c, which is a subset of A_b. The function f(W) only involves coordinates in X \ A_b, which is disjoint from A_b \ A_c. Since W's coordinates are independent, and A_b \ A_c and X \ A_b are disjoint: E[ 1_{A_b \ A_c subset W} f(W) ] = E[ 1_{A_b \ A_c subset W} ] * E f(W) = rho^{|A_b \ A_c|} * E f(W). Combining the last two displayed equations: E[ 1_{target=b, Z>=e^{-10m}} f(W) ] <= e^{10 m} * nu_b * E f(W) * sum_c nu_c * rho^{-|A_b|} * rho^{|A_b \ A_c|} = e^{10 m} * nu_b * E f(W) * sum_c nu_c * rho^{-|A_c INTERSECTION A_b|}. Now bound the c-sum using the intersection bound with the full range r = 0, 1, ..., m (not just r > m/2 -- every r is possible here): sum_c nu_c * rho^{-|A_c INTERSECTION A_b|} <= sum_{r=0}^m C(m, r) (a/rho)^r = (1 + a/rho)^m <= (1 + e^{-50})^m <= e^m. (Using a/rho <= e^{-50} and 1 + x <= e^x.) So: E[ 1_{target=b, Z>=e^{-10m}} f(W) ] <= e^{10 m} * nu_b * E f(W) * e^m = e^{11 m} * nu_b * E f(W). That is exactly part (ii). Done. 5.8. Sanity check of the constants. ------------------------------------------------------------ * e^{-9 m}: what's the probability I skip a level? About 1 in 8000 for m = 1; astronomically small for larger m. Since the tree has at most log_2 h levels, the total failure probability from collecting all such events is at most about log_2 h * 1.2 e-4. That is tiny. * e^{11 m}: this is "the cost of one level of the tree". It is huge, but it is paid in a very specific way: it inflates the "effective spread parameter" of the fragment distribution. Because each tree level's labels grow by a factor of 16, the sum of the resulting e^{11 m_i} factors is dominated by the largest m_i, giving a logarithm of h, not of n. * 50: arbitrary but chosen so that log_2 50 is large enough. The actual paper uses e^{50} to make the constants cleanly separate from "e^2" or "e^5", giving final constant around e^{...}. Any bigger number would work. The lemma has all the slack it needs, because everything is exponential and controlled. Now we use it many times simultaneously, using the SAME W at every tree node. 5.9. What we will actually plug in for a, rho, m. ------------------------------------------------------------ In the tree application, the "labels" A_b of the local lemma are going to be the CHILD LABELS A_v(b) of a probability tree. At a node v whose outgoing level has capacity m_s (the integer ell_s), we set: a = alpha_v (the spread parameter of that node's child distribution, which will be at most 4 sigma), m = m_s (the incoming positive integer capacity), rho = 4 sigma e^50 (independent of v, s). Then a/rho = alpha_v / (4 sigma e^50) <= 4 sigma / (4 sigma e^50) = e^{-50}. The lemma applies to every node, with the SAME rho. That "same rho" is the crucial technical point. If we used a different rho at every node of the tree, we would not be able to run all the transitions on ONE shared random set W, and the whole argument collapses into a linear factor of log^2 h again. We will handle the re-spreading that the tree needs (each level becomes slightly less spread) via a product estimate on (1 - e^{-m}) factors. That is exactly where the "4 sigma" bound in Part 6's statement of Theorem B comes from. The 4 in "4 sigma" is what remains after accounting for the spread cost of compounding reductions. ================================================================================ PART 6. MODULE B: COVERING A TREE ================================================================================ 6.0. The idea in one picture. ------------------------------------------------------------ Imagine a family tree of "possible small sets". The root is an empty set. From the root, a small number of children represent possible "first labels" to commit to. From each of those, another small number of grandchildren represent possible "second labels to add", and so on down to a leaf depth k. Every root-to-leaf path has exactly k arcs (k "levels"). Along each arc v -> b the tree carries a label A_v(b) subset X. Take any one root-to-leaf path P. Its union U(P) is a subset of X. The unions of different paths are allowed to be identical; the tree does not "know" that they are identical, and we treat them as separate. We say the tree is DISJOINT if, along every path, the labels A_v(b) are pairwise disjoint. Then the union U(P) has size |A_v1(b1)| + ... + |A_vk(bk)|, no overlaps inside one path. We say a level has CAPACITY m if every label on every arc into that level has size <= m, and a level is a-SPREAD if the child distribution at every node immediately above that level is a-spread (in the sense of 5.0). Here is what we want to prove. Coverage: given a disjoint probability tree with exponentially growing capacities, find a single independent Bernoulli-p subset W of X of moderate p that, with high probability, CONTAINS the entire union U(P) for at least one root-to-leaf path P. This is only possible if p is at least as large as the maximum label size in the tree, roughly - if labels have size m_max, then picking out the whole label at density p requires p^{m_max} "probability mass", so p needs to be at least a bit above m_max / |X| on average. In our application m_max = ell_k and |X| = C(n, 2) is huge; the actual numerical bound on p is what the theorem gives. Suppose we didn't care about efficiency: we could just sample 2^d different random sets W at various densities, one for each path, and take union. But that's wasteful. The point of the theorem is to do it with ONE W of density r = 16 e^50 sigma (1 + log_2 ell_k). That is a single logarithm, not something worse. 6.1. Definitions. ------------------------------------------------------------ PROBABILITY TREE ON X. A finite rooted tree with all leaves at the same depth k (so every path from root to leaf has k arcs), equipped with: * for each non-leaf node v, a probability distribution nu_v on its children Ch(v); * for each arc v -> b (with b a child of v), a label A_v(b) subset X. Different nodes and arcs may have IDENTICAL labels. Nodes are never identified just because their labels agree. PATH. We always mean a full root-to-leaf path of k arcs unless we say otherwise. A path P is a sequence (v_0 -> b_1), (b_1 -> b_2), ..., (b_{k-1} -> b_k) where v_0 = root. UNION OF A PATH. UU(P) = union over arcs (v -> b) of P of A_v(b). DISJOINT. For every path P of the tree, the labels along P are pairwise disjoint subsets of X. CAPACITY OF A LEVEL. A positive integer m is the capacity of the s-th level if every label on every arc v -> b where b is at level s has |A_v(b)| <= m. SPREAD OF A LEVEL. A parameter sigma > 0: every level s of the tree is "sigma-spread" if, for every node v at level s-1, the child distribution nu_v is sigma-spread in the sense of 5.0. Note: we do NOT assume anything about the distribution of full paths. Only that each child distribution is a-spread at every node. 6.2. The tree-covering theorem. ------------------------------------------------------------ THEOREM B (Tree covering). Let TT be a disjoint probability tree on a finite set X, with k >= 1 levels and positive integer capacities ell_1, ..., ell_k satisfying ell_{i+1} >= 16 * ell_i (1 <= i < k). Suppose every level is sigma-spread, where sigma > 0. Set r = min{ 1, 16 * e^50 * sigma * (1 + log_2 ell_k) }. Then, if W ~ mu_r is an independent sample (each point of X with probability r, independently), we have P( UU(P) subset W for SOME path P of TT ) >= 2/3. Note the "some": it is enough that at least one path's whole union lands inside W. The path can be chosen by any rule after W is revealed. 6.3. Sanity check of the constants. ------------------------------------------------------------ - Factor 16 for the growth. The labels grow geometrically. The exponent 16 in "ell_{i+1} >= 16 ell_i" is not magic; any factor bigger than 1 would work, but bigger is better for us because it makes the geometric sum collapse faster. - Factor (1 + log_2 ell_k). The "cost of a level" is e^{11 m_i} from the local resampling. In the geometric growth, the total is dominated by the LARGEST level. Since ell_k >= 16 ell_{k-1} >= 256 ell_{k-2} ..., the "spread cost" from all levels combined gives a log_2 ell_k factor (a geometric sum of logs), not the sum of all ell_i. - The 1 + log_2 ell_k instead of just log_2 ell_k is because even the SMALLEST level wants 1 unit of "log". If ell_1 = 1 (e.g. the tree has a single point in each label at level 1) then 1 + log_2 ell_k keeps the bound at >= 1 in a friendly way. - 16 e^50 from iterating. After each reduction, spread grows by at most e per level of compression, and we retry until sizes go to zero. The tightening over all iterations is bounded by 4 sigma; multiplied by e^50 from the local resampling cost, and by 4 from Markov's inequality in the iteration analysis. So 4 * 4 * e^50 = 16 e^50. Sanity: no cleverness in the constants, we are happy to spend an extra factor of 16 to keep the argument clean. 6.4. The reduction lemma. ------------------------------------------------------------ Here is the one-shot engine. It takes a disjoint probability tree with sigma-spread levels, and an independent W ~ mu_rho with rho = e^50 a (for the a that upper-bounds the levels), and outputs a smaller tree with halved capacities. This is the engine we iterate. LEMMA B (Reduction). Let TT be a disjoint probability tree with k >= 1 levels and positive integer capacities m_1, ..., m_k satisfying m_{j+1} >= 16 m_j for every j. Suppose every level j is alpha_j-spread, where 0 < alpha_j <= a, rho = e^50 a < 1. Given a single independent W ~ mu_rho, there is a deterministic procedure which succeeds with probability at least 3/4 and, on success, returns a disjoint probability tree TT' with the same k levels and: (i) level j of TT' has capacity floor(m_j / 2); level j of TT' is alpha_j / (1 - e^{-m_j})-spread. (ii) For every path Q of TT', there exists a path P of TT such that UU(P) subset W UNION UU(Q). Points to note. * (ii) is the "recovery guarantee": the smaller TT' does not lose information. Any path Q in TT' points back to a path P in TT that is covered by W plus Q's own labels. * The factor 1/(1 - e^{-m_j}) in the spread is only very slightly worse than alpha_j. For m_j >= 1, 1 - e^{-m_j} >= 1 - e^{-1} ~ 0.63, so this is a bounded degradation (worse by a factor of ~1.6 at m=1, and astronomically closer to 1 as m grows). * "The same k levels" is important: we do not compress the depth in the reduction lemma. Compression to zero happens later, during the iteration. 6.5. What the reduction procedure is, in words. ------------------------------------------------------------ Pre-fix W. We will build TT' as a pruned subtree of TT. For every node v of TT whose outgoing level is j, use the local transition of Part 5 with its child distribution nu_v, capacity m_j, and the FIXED set W. That is, for each child b: - sample a source c ~ nu_v, - plant Y = W UNION A_v(c), - resample target b' ~ posterior given Y and rho, - retain fragment T = A_v(b') \ W. At fixed W, we do not actually sample; we compute the probability of each outcome. Let d_v(W) be the total probability of local failure at v. Let t_{vb}(W) be the probability of local non-failure with target exactly b. Then (5.3(i) and the transition definition): d_v(W) + sum_{b in Ch(v)} t_{vb}(W) = 1. This is at each node v, for the given fixed W. Pruning: define "good" nodes bottom-up. Leaves are good. A node v with outgoing level j is good if sum over good children b of v of t_{vb}(W) >= 1 - e^{-m_j}. That is, at least (1 - e^{-m_j}) of the transition mass at v is on children that are themselves good. Success: the attempt succeeds iff the root is good. Output tree TT' (on success): starting from the root, keep only the good children; replace each kept arc's label A_v(b) with the smaller label T_v(b) = A_v(b) \ W; reweight the kept child probabilities: weight of kept child b = t_{vb}(W) / (sum of t_{vb} over kept b). This is a smaller tree. On success, TT' is a valid probability tree with the properties claimed. We have to prove: (a) success prob is >= 3/4; (b) the shrink and the spread bounds hold; (c) the recovery guarantee (ii). Property (a) is the main work (the "potential" argument in 6.6/6.7). Property (b) is a direct consequence of the local lemma. Property (c) is almost tautological (recall A_b subset W UNION T_b from Part 5). 6.6. Proof of (a): a potential on the tree. ------------------------------------------------------------ Define, for every node v of the input TT, a potential D_v(W) as follows. At a leaf: D_v(W) = 0. At a node v whose outgoing level is j, recursively: D_v(W) = [ d_v(W) + sum_{b in Ch(v)} t_{vb}(W) * D_b(W) ] / e^{-m_j} . This is exactly the "failure + worse-deeper" mixture, divided by the "tolerance" e^{-m_j} at v. Claim 1: If v is bad, then D_v(W) > 1. Proof by backward induction from the leaves. A leaf is never bad (leaves are declared good). Suppose v is a non-leaf with outgoing level j, and suppose the claim is true for all its bad children (if any). Since v is bad, the mass on good children is < 1 - e^{-m_j}. In other words: sum_{b good} t_{vb}(W) < 1 - e^{-m_j}. Then: d_v + sum_{b bad} t_{vb} * D_b > d_v + sum_{b bad} t_{vb} = d_v + (1 - sum_{b good} t_{vb}) > d_v + e^{-m_j} > e^{-m_j}. Here the first strict inequality uses the induction hypothesis D_b > 1 on bad children, and the second uses the badness of v; d_v >= 0. Dividing by e^{-m_j} gives D_v > 1. This is what we needed. So: P(root is bad) <= P(D_root > 1) <= E D_root (Markov, since D_root >= 0). We will show E D_root < 1/4, giving P(success) > 3/4. 6.7. Proof of (a): bounding the expected potential. ------------------------------------------------------------ We need E_W ~ mu_rho [ D_root(W) ] < 1/4. Step 1: local bound at one node v. Recall from 6.6, D_v = e^{m_j} * d_v + e^{m_j} * sum_b t_{vb} D_b. Take expectations over W ~ mu_rho. For the first term: E[ e^{m_j} * d_v(W) ] <= e^{m_j} * E[ 1_{local failure at v} ] <= e^{m_j} * e^{-9 m_j} (Part 5 Lemma A, part (i)) = e^{-8 m_j}. For the second term: e^{m_j} * sum_b E[ t_{vb}(W) D_b(W) ]. The key observation: D_b(W) depends only on W INTERSECTION (X \ A_v(b)). Why? Every label in the entire subtree below b is disjoint from A_v(b): each such label lies on a path of the disjoint tree through the arc v -> b, so it is disjoint from A_v(b) by the disjoint hypothesis on TT. And the transition at any node in that subtree only inspects W on the union of that node's child labels, which lies below b. So the outcome of the transition at each node below b depends only on W's restriction to (X \ A_v(b)). This is the crucial "spatial locality" that lets us use the distortion bound with f = D_b. The local transition probability t_{vb}(W) is bounded by: t_{vb}(W) <= P( target = b, Z(Y) >= e^{-10 m_j} | W ) (the rest of the transition mass is on local failures at v, which we've already accounted for). So: E[ t_{vb}(W) D_b(W) ] <= E[ 1_{target = b, Z >= e^{-10 m_j}} D_b(W) ] <= e^{11 m_j} * nu_v(b) * E D_b(W) (Part 5 Lemma A, part (ii)) (Here we applied the distortion bound with f = D_b(W), which is nonnegative and depends only on W INTERSECTION (X \ A_v(b)) as we just argued.) Therefore: E D_v(W) <= e^{-8 m_j} + e^{12 m_j} * sum_b nu_v(b) * E D_b(W). That is the master inequality. Everything else is bookkeeping. Step 2: unroll the master inequality along the tree. Let s be the outgoing level of v. Let m_s, m_{s+1}, ..., m_k be the capacities from level s down to the leaves. Claim: E D_v(W) <= sum_{j = s}^{k} exp( 12 * sum_{h = s}^{j-1} m_h - 8 * m_j ). Proof by backward induction on j going up the tree. Base: leaves, s = k+1, D = 0, empty sum = 0. Consistent. Inductive: at a node with outgoing level s, use the master inequality: E D_v <= e^{-8 m_s} + e^{12 m_s} * sum_b nu_v(b) * E D_b. Since {nu_v(b)} is a probability distribution and by induction each E D_b is at most the corresponding sum from s+1: sum_b nu_v(b) * E D_b <= sum_{j = s+1}^k exp( 12 * sum_{h = s+1}^{j-1} m_h - 8 m_j ). So: E D_v <= e^{-8 m_s} + sum_{j = s+1}^k exp( 12 m_s + 12 * sum_{h = s+1}^{j-1} m_h - 8 m_j ) = e^{-8 m_s} + sum_{j = s+1}^k exp( 12 * sum_{h = s}^{j-1} m_h - 8 m_j ) = sum_{j = s}^k exp( 12 * sum_{h = s}^{j-1} m_h - 8 m_j ). (The j = s term is e^{-8 m_s}, since the empty sum is 0.) Step 3: plug in geometric growth. We need: for j > s, 12 * sum_{h = s}^{j-1} m_h - 8 m_j <= -7 m_j. By geometric growth m_{h} <= m_{j-1} / 16^{j-1-h}. So: sum_{h = s}^{j-1} m_h <= m_{j-1} * (1 + 1/16 + 1/256 + ...) <= m_{j-1} * 16/15 <= (m_j / 16) * 16/15 = m_j / 15. So: 12 * sum_{h=s}^{j-1} m_h - 8 m_j <= 12 * (m_j / 15) - 8 m_j = (4/5 - 8) * m_j = -36/5 * m_j < -7 * m_j. So each j > s term is at most e^{-7 m_j}. The j = s term is e^{-8 m_s} <= e^{-7 m_s}. Altogether: E D_v(W) <= sum_{j = s}^k e^{-7 m_j} <= sum_{m = 1}^{infinity} e^{-7 m} = e^{-7} / (1 - e^{-7}) ~ 0.000913 < 1/4. (The "sum over all positive integers" step uses that m_s, ..., m_k are distinct positive integers with 1 <= m_s < m_{s+1} < ... < m_k. The sum of e^{-7 m} over all such m is an upper bound for the sum over any subset of positive integers.) Hence P(success) = P(root good) = 1 - P(root bad) >= 1 - E D_root >= 1 - 1/4 = 3/4. Great. Claim (a) proved. 6.8. Proof of (b) and (c): shrink, spread, and recovery. ------------------------------------------------------------ Now we prove, on the success event, that the output tree TT' actually has the claimed properties. Property (c) (recovery) first. At each arc v -> b, the fragment T_v(b) = A_v(b) \ W satisfies A_v(b) subset W UNION T_v(b) (this is Part 5's inclusion (ii)). So for any path Q of TT', the union of the CORRESPONDING original labels equals the union of the ORIGINAL labels along the corresponding path P of TT, which is: UU(P) = union of A_v(b) over arcs (v,b) in P. But since each A_v(b) subset W UNION T_v(b), and T_v(b) = A_v(b) \ W: A_v(b) subset W UNION (A_v(b) \ W) = W UNION T_v(b). Union over arcs gives UU(P) subset W UNION UU(Q) where UU(Q) is the union of the t_v(b) over the same arcs. That is exactly claim (ii). Property (b): size of the new label. By Lemma A(i), on a non-failure transition at v, |T_v(b)| <= m_j / 2 for the capacity m_j. So the capacity at level j of TT' is floor(m_j / 2). Note: m_j is a positive integer, so we can also write |T| <= floor(m_j / 2). This is the shrink. Property (b): spread of the new child distribution. At fixed W, and on the success event, node v has mass >= 1 - e^{-m_j} on good children. Let E_v be the joint event "local non-failure at v AND target is good". Then: P(E_v | W) = gamma_v(W) >= 1 - e^{-m_j}. The new distribution on kept children is the conditional distribution of the target given E_v (and W). For any nonempty J subset X, P( J subset T | E_v, W ) <= P( J subset T, E_v | W ) / gamma_v(W) <= P( J subset A_v(c) | W ) / gamma_v(W) (T subset A_v(c)) = P( J subset A_v(c) ) / gamma_v(W) (c indep of W) <= alpha_j^{|J|} / (1 - e^{-m_j}) <= ( alpha_j / (1 - e^{-m_j}) )^{|J|}. The step "P(J subset T, E_v | W) <= P(J subset A_v(c) | W)" uses the fragment inclusion T subset A_v(c) from Part 5 (which holds for EVERY transition, success or failure). So the new child distribution is precisely alpha_j / (1 - e^{-m_j})-spread, as claimed. Property (b): depth preserved. Since gamma_v > 0 at every retained non-leaf node (success = good root, and good means the mass on good children is at least 1 - e^{-m_j} > 0), the retained subtree reaches the depth of TT. Same k levels. And the labels are subsets of the old labels, so TT' is disjoint. Property (b): recovery is via labels only; nothing else is needed. Done. 6.9. Proof of Theorem B: iterating the reduction. ------------------------------------------------------------ We will use the reduction lemma as a "compressor". Each successful compression halves all capacities. After s successes, capacities are floor(ell_i / 2^s); when s > log_2 ell_k, all capacities are zero. # ^C interrupted by user!