Clause labels in a ball are unaffected by a distant insertion
ProvedKSATSingleFlip.Connect.ballClauseLabels_eq_disjointLet be a finite formula, a clause, a variable, and a nonnegative integer. If the variables of are disjoint from the variable vertices of the radius- factor-graph ball around in , then the set of original clause-occurrence labels in that ball is unchanged by insertion. Repeated clauses have distinct occurrence labels. This supports the sensitivity estimate in Lemma 2.7.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_TrimmedBall open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
theorem ballClauseLabels_eq_disjoint {n : ℕ} (Φ : GFormula (Fin n)) (C : GClause (Fin n))
(root : Fin n) (r : ℕ) (hno : Disjoint (vbl C) (ballVars (Φ ++ [C]) root r)) :
ballClauseLabels (Φ ++ [C]) root r = ballClauseLabels Φ 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