Sensitive occurrence deletions lie on a short winning-path certificate
ProvedStabilityDichotomies.Bijunctive.occurrence_graph_deletions_have_short_certificateFor the actual occurrence-indexed thinned implication graph, all occurrence deletions that can change a variable’s output with fixed feasible roots lie in a finite set of at most occurrences, where is strictly less than a feasible maximizing root’s shift. Equal constraint values remain distinct indexed occurrences.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.occurrence_graph_deletions_have_short_certificate
{Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I F : Instance Γ V)
(mask : Fin I.constraints.card → Bool) (δ : Literal V → ℝ) (v : V) (w : Bool)
(hw : w = decide (literalScore rep (thinnedInstance I mask) F δ (v,false) <
literalScore rep (thinnedInstance I mask) F δ (v,true)))
(hpos : (0 : WithBot ℝ) < literalScore rep (thinnedInstance I mask) F δ (v,w)) :
∃ root : Literal V, ∃ n : ℕ, ∃ S : Finset (Fin I.constraints.card),
S.card ≤ n ∧ (n : ℝ) < δ root ∧
∀ j ∉ S, decide (literalScore rep (thinnedInstance I (fun i => mask i && decide (i ≠ j))) F δ (v,false) <
literalScore rep (thinnedInstance I (fun i => mask i && decide (i ≠ j))) F δ (v,true)) = w := 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, graph-deletion sensitivity step.