A violated constraint has a violated non-tautological expanded clause
ProvedStabilityDichotomies.Bijunctive.violated_constraint_has_nontaut_violated_clauseIf an assignment violates an original Boolean constraint, at least one clause of its fixed defining 2-CNF expansion is violated after scope substitution, and this substituted clause is not a tautology.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.violated_constraint_has_nontaut_violated_clause {Γ : Language} {V : Type}
(rep : TwoCNFRepresentation Γ) (c : Constraint Γ V) (x : V → Bool)
(hviol : ¬ c.Satisfied x) :
∃ q ∈ rep.clauses c.rel,
(substituteClause c q).1 ≠ literalNeg (substituteClause c q).2 ∧
¬ clauseSatisfied x (substituteClause c q) := 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, approximation paragraph.