Change in variable degree upon insertion of a clause
ProvedKSATSingleFlip.Connect.degree_append_oneFor a finite formula , a clause , and a variable , appending changes the full-formula degree of by exactly one if occurs in , and leaves it unchanged otherwise:
Clause occurrences are counted with multiplicity. This is a supporting fact for the sensitivity part of Lemma 2.7.
Preamble
import Definitions.Def_KSATSingleFlip_Connect_FactorGraph open scoped Classical BigOperators
Formal statement
namespace KSATSingleFlip.Connect
theorem degree_append_one {n : ℕ} (Φ : GFormula (Fin n)) (C : GClause (Fin n)) (u : Fin n) :
degree (Φ ++ [C]) u = degree Φ u + if u ∈ vbl C then 1 else 0 := 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