A retained occurrence rarely violates an expanded clause under the full seed law
ProvedStabilityDichotomies.Bijunctive.retained_occurrence_clause_violation_seed_boundFor a satisfiable input and , fix an occurrence and a non-tautological clause in its 2-CNF expansion. Under the complete Definition 4.8 product seed law, the probability that the occurrence is retained in the graph subinstance and the output violates this clause is at most , where .
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.retained_occurrence_clause_violation_seed_bound {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I)
(ε : ℝ) (hε : 0 < ε) (i : Fin I.constraints.card)
(q : Clause (Fin (occurrenceAt I i).rel.val.arity)) (hq : q ∈ rep.clauses (occurrenceAt I i).rel)
(ht : (substituteClause (occurrenceAt I i) q).1 ≠ literalNeg (substituteClause (occurrenceAt I i) q).2) :
(bijunctiveSeedMeasure rep I ε
{seed | seed.1 i ≤ 1 - ε / 2 ∧
¬ clauseSatisfied (bijunctiveOutput rep I ε seed.1 seed.2.1 seed.2.2)
(substituteClause (occurrenceAt I i) q)}).toReal ≤
1 - Real.exp (-bijunctiveRate rep ε) := 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.