Adding feasibility constraints cannot increase a literal score
ProvedStabilityDichotomies.Bijunctive.score_decreases_when_feasible_roots_shrinkWith graph and shifts fixed, adding constraints to the feasibility-testing instance can only remove feasible roots and therefore cannot increase any literal score.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.score_decreases_when_feasible_roots_shrink {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (G F F' : Instance Γ V) (δ : Literal V → ℝ)
(hsub : ∀ c ∈ F.constraints, c ∈ F'.constraints) (target : Literal V) :
literalScore rep G F' δ target ≤ literalScore rep G F δ target := 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, feasibility-root sensitivity step.