Factor-graph balls grow under clause insertion
ProvedKSATSingleFlip.Connect.append_ballVars_monoLet be a finite formula, a clause, a variable, and a nonnegative integer. Let denote the variable vertices of the radius- factor-graph ball, including itself. Appending can only enlarge this variable set:
Clause occurrences remain distinct. 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_mono {n : ℕ} (Φ : GFormula (Fin n)) (C : GClause (Fin n))
(v : Fin n) (r : ℕ) : ballVars Φ v r ⊆ ballVars (Φ ++ [C]) v 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