Isolated variables have graph-independent literal scores
ProvedStabilityDichotomies.Bijunctive.isolated_variable_graph_deletion_score_unchangedIf a variable lies outside every original constraint scope, then with feasible roots and shifts fixed, both of its literal scores are the same for every occurrence-thinned implication graph. Consequently graph-step deletions cannot change that variable’s output.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.isolated_variable_graph_deletion_score_unchanged {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I F : Instance Γ V) (v : V)
(hiso : ∀ c ∈ I.constraints, ∀ k : Fin c.rel.val.arity, c.scope k ≠ v)
(mask mask' : Fin I.constraints.card → Bool) (δ : Literal V → ℝ) (b : Bool) :
literalScore rep (thinnedInstance I mask) F δ (v,b) =
literalScore rep (thinnedInstance I mask') F δ (v,b) := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, first sensitivity step.