Variable ball unaffected by a distant inserted clause
ProvedKSATSingleFlip.Connect.append_ballVars_eq_disjointLet be a finite formula, a clause, a variable, and a nonnegative integer. Suppose none of the variables of belongs to the variable vertices of the radius- factor-graph ball around in the enlarged formula . Then those variable vertices are unchanged by insertion:
The ball includes its root even if that root is isolated. This is a supporting fact for the sensitivity estimate in Lemma 2.7.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_FactorGraph open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
theorem append_ballVars_eq_disjoint {n : ℕ} (Φ : GFormula (Fin n))
(C : GClause (Fin n)) (root : Fin n) (r : ℕ)
(hno : Disjoint (vbl C) (ballVars (Φ ++ [C]) root r)) :
ballVars (Φ ++ [C]) root r = ballVars Φ root r := by
sorry
end KSATSingleFlip.Connect
Source
Auxiliary result for Lemma 2.7 of Wang, Yin, Yu, Zhang, Single-Variable Connectivity in Random k-SAT, printed pp. 12–13, STOC 2027 submission #737, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/737.pdf