Total graph-only deletion disagreement probabilities obey the source bound
ProvedStabilityDichotomies.Bijunctive.total_graph_deletion_bit_change_probabilities_boundSum, over all constraint occurrences and variables, the shared-seed probabilities that deleting only the occurrence’s implication arcs changes the output bit. This total is bounded by , with the source exponential rate . The probability form connects the proved graph-change estimate to the Wasserstein coupling split.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Function StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.total_graph_deletion_bit_change_probabilities_bound {Γ : Language} {V : Type} [Fintype V] [Nonempty V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I) (ε : ℝ) (hε : 0 < ε) :
let μ := bijunctiveSeedMeasure rep I ε
let mid := fun (j : Fin I.constraints.card) (z : (Fin I.constraints.card → ℝ) × ℝ × (Literal V → ℝ)) v =>
decide (literalScore rep (thinnedInstance I (fun i => decide (z.1 i ≤ 1 - ε / 2) && decide (i ≠ j)))
(thinnedInstance I (fun i => decide (z.1 i ≤ z.2.1))) z.2.2 (v,false) <
literalScore rep (thinnedInstance I (fun i => decide (z.1 i ≤ 1 - ε / 2) && decide (i ≠ j)))
(thinnedInstance I (fun i => decide (z.1 i ≤ z.2.1))) z.2.2 (v,true))
(∑ j : Fin I.constraints.card, ∑ v : V,
(μ {z | bijunctiveOutput rep I ε z.1 z.2.1 z.2.2 v ≠ mid j z v}).toReal) ≤
(maxArity Γ * I.constraints.card : ℕ) *
((Real.log (Fintype.card (Literal V)) + 1) / 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, graph-only deletion bound.