Lemma 6.4 — All properties of the expander formula, including counts, occurrences and the satisfying-set characterization
OpenMTWalkSAT3CNF.TwoOcc.Supplement.lemma_6_4p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmssatisfiability
For a graph satisfying the §6 graph conditions, let and construct using all the indexed gadgets and both orientations of each edge. Every clause has three distinct variables and is non-tautological. The counts and occurrence bound are
For every complete assignment , including all auxiliary bits,
Furthermore, satisfies if and only if . Here are the active, zero-progress and one-progress block sets, and crossing edges are counted once. All clauses of the source lemma are included.
Differences from the source:
- generalization: G is a graph of the explicitly constructed family in Lemma 6.2 → any finite simple connected 102-regular graph with λ₁=102 and every other adjacency eigenvalue of absolute value less than 21; reason: every graph in the source family satisfies exactly these conditions; the proofs use only these graph properties
- encoding: vertices, indexed gadget clauses and Boolean assignments → vertices Fin N, finite sum/product index types and Bool-valued assignments including every auxiliary bit; reason: finite bijective labels change no instance and both orientations of each edge are retained
Preamble
import Definitions.Def_MTWalkSAT3CNF_TwoOcc_Supplement_Expander set_option autoImplicit false open MeasureTheory open scoped ENNReal
Formal statement
namespace MTWalkSAT3CNF.TwoOcc.Supplement
theorem lemma_6_4 {N : ℕ} (G : SimpleGraph (Fin N)) (hG : GoodGraph G) :
(∀ i, Function.Injective ((expFormula G) i).var ∧
¬ ∃ p q, ((expFormula G) i).var p = ((expFormula G) i).var q ∧
((expFormula G) i).sign p ≠ ((expFormula G) i).sign q) ∧
Fintype.card (ExpVar N) = 823*N ∧
Fintype.card (ExpIndex G) = 1846*N ∧
numOccVars (expFormula G) = 823*N ∧
(∀ v, occCount (expFormula G) v ≤ 1740) ∧
(∀ x : ExpVar N → Bool,
(bad (expFormula G) x).card = 717*(zeroBlocks x).card + 52*(oneBlocks x).card +
2*cutCount G (active x) (zeroBlocks x) + cutCount G (active x) (oneBlocks x)) ∧
(∀ x : ExpVar N → Bool, bad (expFormula G) x = ∅ ↔ active x = Finset.univ) := by sorry
end MTWalkSAT3CNF.TwoOcc.Supplement
Source
Minbo Gao, Kun He, Tao Jiang, STOC 2027 submission #914 (October 2026), Lemma 6.4, p. 36–37; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/914.pdf