A positive winning score has a short maximizing path
ProvedStabilityDichotomies.Bijunctive.positive_score_has_short_winning_pathA positive literal score is attained by a feasible root whose shortest-path length is strictly less than that root’s shift. This is the path-length estimate used in the first sensitivity step.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.positive_score_has_short_winning_path {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (G F : Instance Γ V) (δ : Literal V → ℝ)
(target : Literal V) (hpos : (0 : WithBot ℝ) < literalScore rep G F δ target) :
∃ root : Literal V, ∃ n : ℕ, feasibleLiteral F root ∧
implicationDistance rep G root target = some n ∧
literalScore rep G F δ target = ((δ root - n : ℝ) : WithBot ℝ) ∧
(n : ℝ) < δ root := 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 step.