Results on thresholds, expectation thresholds, spread families, unions of likely sets and graph containment, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Monotone coupling — Lemma 1.1. For an increasing family F, p -> mu_p(F) is a nondecreasing polynomial, strictly increasing from 0 to 1 when F is nontrivial.
• Unions of independent product sets — Lemma 1.2. A union of independent mu_(p_i)-random sets is mu_(p*)-random with 1 - p* = prod (1 - p_i), and p* <= sum p_i.
• Expectation thresholds — Proposition 2.2. q(F) <= q_f(F) <= p_c(F) for every nontrivial increasing family F.
• Spread members — Proposition 2.3. If a random member A of F satisfies P(J in A) <= sigma^|J| for nonempty J, then q(F) <= q_f(F) <= sigma.
• Counting copies — Lemma 3.1. M(F) = (n)_v(F) / |Aut F|, and a uniformly random copy of I contains a fixed copy of F with probability M(I,F)/M(F).
• The expectation threshold of a graph — Lemma 3.2. p_E(n,H) is determined by the nonempty edge subsets of H, satisfies 0 < p_E(n,H) <= p_c(n,H), and ignores isolated vertices.
• Graph and abstract expectation thresholds — Proposition 3.3. p_E(n,H) <= q(F_H) <= q_f(F_H) <= p_c(n,H).
• Expectation threshold of a perfect matching — Proposition 4.2. 1/(2n) <= p_E(n, PM_n) <= e^2/n for every even n.
• Isolated vertices — Proposition 4.3. For n >= 16, G(n, log n/(3n)) has an isolated vertex with probability greater than 1/2; hence p_c(n, PM_n) > log n/(3n).
• Fractional threshold of a perfect matching — Proposition 4.4. q(F_PM_n) <= q_f(F_PM_n) <= e^2/n for every even n.
• Overlaps of a spread family — Lemma 1.3. For an a-spread family and a label of size at most m, P(|A_c intersect A_b| = r) <= binom(m,r) a^r.
• Planting — Lemma 2.2. If W ~ mu_rho is independent of the source, Y = W union A_c has density Z with respect to mu_rho, the target is a posterior sample, and P(Z(Y) < theta) <= theta.
• Local resampling (OpenAI) — Theorem 3.1. For an a-spread family with labels of size at most m and a <= e^(-50) rho, a local failure has probability at most e^(-9m), and the event that the target is b changes the law of W outside A_b by at most e^(11m) nu_b.
• One simultaneous reduction (OpenAI) — Lemma 2.1. With probability at least 3/4, one mu_rho-random set W halves every capacity of a disjoint spread probability tree, keeps it nearly spread, and every new path union together with W contains an old one.
• Tree covering (OpenAI) — Theorem 3.2. If every level is sigma-spread and the capacities grow by factors of at least 16, a mu_r-random set with r = min{1, 16 e^50 sigma (1 + log_2 l_k)} contains some path union with probability at least 2/3.
• The spread lemma — Corollary 4.1. A sigma-spread family of sets of size at most l has a member inside a mu_r-random set, r = min{1, 16 e^50 sigma (1 + log_2 l)}, with probability at least 2/3.
• Maximizers are small — Lemma 1.1. With sigma = 128 p_E(n,H), every maximizer S of R(I, .) satisfies |S| < |I|/17.
• Conditional extensions — Lemma 2.1. Given a copy of H_(i-1), the edges added by a uniform extension to a copy of H_i form a 128 p_E(n,H)-spread random set.
• The tree of extensions (OpenAI, after Tran) — Lemma 2.2. There is a disjoint 128 p_E(n,H)-spread probability tree whose path unions are copies of H and whose capacities grow by factors of at least 16 up to at most e(H).
• The second Kahn-Kalai conjecture (OpenAI) — Theorem 3.1. p_c(n,H) <= min{1, 2048 e^50 p_E(n,H) (1 + log_2 e(H))} <= 6144 e^50 p_E(n,H) log_2 n.
• Perfect matchings — Corollary 3.2. log n/(3n) < p_c(n, PM_n) <= 2048 e^52 log_2 n / n for every even n >= 16.
• Maximal truncation — Lemma 2.1. If an admissible cutoff exists, the largest one, epsilon, leaves at most m/d masses above epsilon.
• Multiscale selector estimate (OpenAI) — Theorem 3.1. If F is not p-small, then with probability at least 9/10 a random colouring with colour probabilities 256^i p has one member H capturing lambda_H-mass at least 1 - 2^-i of the colours <= i, for every scale i.
• Talagrand's conjecture (OpenAI) — Theorem 4.1. q_f(F) <= 25 * 512^4 q(F) for every nontrivial increasing family F, with the same budget 1/2.
• Global weight bound — Lemma 2.1. The weights w(U) = b(U)^2 satisfy sum_U q^|U| w(U) <= mu_q(F).
• Signed identity — Lemma 3.1. If S is not covered by l members of F, then sum over U subset S of (-1)^|U| b(U)^l = 0.
• Li's fractional cover — Proposition 4.1. If mu_q(F) >= 1/2, the sets not covered by two members of F have a fractional cover of cost at most 1/2 at density q/2.
• Two unions (OpenAI) — Corollary 4.2. If mu_p(D) >= 1/2, the sets not covered by two members of D form a p/(50 * 512^4)-small family.
• Covering lemma (OpenAI) — Lemma 5.1. If |H| rho^r <= 2^(h+1) for an r-uniform family H, h >= 64, the sets containing 2^(12h) members of H have a cover of cost at most 3 * 2^-h at rho.
• Thirty-two unions (OpenAI) — Proposition 6.1. If mu_q(F) >= 1/2, the sets not covered by 32 members of F form a q/2^70-small family.
• Talagrand's discrete convexity conjecture (OpenAI) — Theorem 7.1. If mu_p(D) >= 1 - 2^-75, the sets not covered by 2^75 members of D form a p-small family.
• Positive selector processes (Park-Pham) — Corollary 7.2. For phi(S) = sup over t in T of sum_(i in S) t_i with nonnegative t, {phi >= 2^150 E phi} is p-small.
• Lower bounds for the integral threshold — Lemma 1.1. q(H;n) >= 1/(n(n-1)) and q(H;n) >= n^(-2/d)/2 when H has degeneracy d.
• Paley-Zygmund inequality — Lemma 2.1. P(Z > theta E Z) >= (1 - theta)^2 (E Z)^2 / E Z^2 for Z >= 0 and 0 <= theta <= 1.
• Compression after a random extension (OpenAI) — Lemma 3.1. A family of sets of size at most s has a subfamily of at most ceil(2 r^-s) members that every set satisfying the family satisfies with probability at least 1/2 after a mu_r-random extension.
• Neighbourhood transfer (OpenAI) — Proposition 4.1. There is a typical family D with mu_r(D) >= 1 - 2^-75 such that bipartite graphs across a small set Y, with edges in a member of D and outside degrees at most s, have threshold at most 32 r.
• Bounded degeneracy and maximum degree (OpenAI) — Proposition 5.1. Graphs with degeneracy at most s, maximum degree at most n^(2/3) and at most n/4 non-isolated vertices have threshold at most r when r^s >= n^(-1/100).
• Small star forests (OpenAI, after Ascoli-He-Park-Talagrand) — Proposition 6.1. Star forests with at most n/100 non-isolated vertices have threshold at most 800 e^4 times their integral expectation threshold.
• A typical cover of one copy — Corollary 1.1. If q(H;n) < r and mu_r(D) >= 1 - 2^-75, some copy of H lies in the union of 2^75 members of D.
• Degeneracy splitting (Ascoli-He-Park-Talagrand) — Lemma 2.1. A graph of degeneracy d is the edge-disjoint union of m graphs of degeneracy at most ceil(d/m).
• Forests into star forests — Lemma 2.2. Every forest is the edge-disjoint union of two star forests.
• The Ascoli-He-Park-Talagrand conjecture (OpenAI) — Theorem 3.1. Every graph H on at most n vertices splits into k pieces with p_c(H_i;n) <= L q(H;n), k and L absolute.

Reading order

Read lessons 1 to 4 in order for the second Kahn–Kalai conjecture. Lessons 5 to 8 use only the first lesson from that part and are read in order.