Lemma 7.1: random logarithmic-width CNFs are unsatisfiable boundary expanders
ProvedSemAC02.Supplement.lemma_7_1_random_logwidth_expansionPut and . Sample clauses independently and uniformly, with repetition, from the clauses of width exactly on distinct variables among Boolean variables. Let be their conjunction. For a set of clause indices, write for its neighboring variables and for the variables occurring in exactly one of the indexed clauses.
There is an absolute constant such that, with probability tending to one as , is unsatisfiable and simultaneously every nonempty set of at most clause indices satisfies
This supplies the common expansion event used to prove the bounded-bottom-degree lower bounds for random logarithmic-width CNFs.
Formalization Note The graph keeps the sampled clause indices, so repeated clauses remain distinct left vertices. The CNF itself is the set of sampled clauses, which preserves satisfiability. Neighborhoods and boundaries are written directly as finite sets. The ceiling logarithm is Nat.clog, and probability is the mission's uniform counting probability.
import Mathlib import Definitions.Def_LiftSAParity_CNF import Definitions.Def_SemAC02_Supplement_randCNF open Filter Topology LiftSAParity SemAC02.Supplement
theorem SemAC02.Supplement.lemma_7_1_random_logwidth_expansion :
∃ η : ℝ, 0 < η ∧ Tendsto (fun n : ℕ => uprob
(fun ω : Fin (n*2^Nat.clog 2 n) → WClause n (Nat.clog 2 n) =>
¬ Satisfiable (seqCNF ω) ∧ ∀ J : Finset (Fin (n*2^Nat.clog 2 n)),
J.Nonempty → J.card ≤ ⌊η*n/(Nat.clog 2 n : ℝ)⌋₊ →
(3 : ℝ)*(Nat.clog 2 n)*J.card/4 ≤
((J.biUnion (fun j => (ω j).1.image Prod.fst)).card : ℝ) ∧
((Nat.clog 2 n : ℝ)/2)*J.card ≤
((Finset.univ.filter (fun v : Fin n =>
(J.filter (fun j => v∈(ω j).1.image Prod.fst)).card=1)).card : ℝ))) atTop (𝓝 1) := by sorry