Finite exploration collision union bound
ProvedKSATSingleFlip.Connect.exploration_collision_boundFor m labels on a finite nonnegative weighted probability space, if every pair of distinct sampled labels collides with weight at most 1/n, then the total weight of an outcome with any collision is at most m²/n. This is a generic union-bound ingredient in the breadth-first exploration underlying Lemma 2.4; establishing the pairwise hypotheses for the three formula laws remains separate.
Preamble
import Mathlib set_option autoImplicit false open scoped BigOperators
Formal statement
theorem KSATSingleFlip.Connect.exploration_collision_bound {Ω : Type} [Fintype Ω] (m n : ℕ) (hn : 0 < n)
(p : Ω → ℝ) (hp : ∀ ω, 0 ≤ p ω) (X : Fin m → Ω → Fin n)
(hpair : ∀ i j : Fin m, i ≠ j → (∑ ω, if X i ω = X j ω then p ω else 0) ≤ 1/(n:ℝ)) :
(∑ ω, if ∃ i j : Fin m, i ≠ j ∧ X i ω = X j ω then p ω else 0) ≤
(m:ℝ)^2/(n:ℝ) := by sorrySource
Wang–Yin–Yu–Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.4, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf