Reverse locally tree-structured ball bound
ProvedKSATSingleFlip.Connect.lemma_2_7_reverse_ball_boundLet be a finite formula in which every clause involves at most variables. Fix a variable , a radius , and a degree cutoff . At most
variables have both an -locally tree-structured ball and in that ball. This strengthens the reverse-neighborhood estimate in (2.1) of Lemma 2.7 by one geometric term; the proof does not use acyclicity.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_GoodReach open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
theorem lemma_2_7_reverse_ball_bound {n : ℕ} (Φ : GFormula (Fin n))
(k r D : ℕ) (hwidth : ∀ c : Fin Φ.length, (vbl (Φ.get c)).card ≤ k) (u : Fin n) :
(Finset.univ.filter fun v : Fin n => LocallyTree Φ v r D ∧ u ∈ ballVars Φ v r).card ≤
∑ h ∈ Finset.range (r + 1), (k*D)^h := by
sorry
end KSATSingleFlip.Connect
Source
Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, Lemma 2.7, equation (2.1), printed pp. 12–13, STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf