Total graph-deletion changes satisfy the source sensitivity bound
ProvedStabilityDichotomies.Bijunctive.expected_total_seed_graph_deletion_changes_boundUnder the complete Definition 4.8 seed law for a satisfiable instance, fix the random feasible-root set and sum Hamming changes over all occurrence deletions from the random graph subinstance. The count is integrable and its expectation is at most , where is the maximum relation arity and . Isolated variables contribute zero.
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.expected_total_seed_graph_deletion_changes_bound {Γ : Language} {V : Type} [Fintype V] [Nonempty V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I)
(ε : ℝ) (hε : 0 < ε) :
let μ := bijunctiveSeedMeasure rep I ε
let C := fun (v : V) (s : (Fin I.constraints.card → ℝ) × ℝ × (Literal V → ℝ)) =>
∑ j : Fin I.constraints.card,
if decide (literalScore rep
(thinnedInstance I (fun i => decide (s.1 i ≤ 1 - ε / 2) && decide (i ≠ j)))
(thinnedInstance I (fun i => decide (s.1 i ≤ s.2.1))) s.2.2 (v,false) <
literalScore rep (thinnedInstance I (fun i => decide (s.1 i ≤ 1 - ε / 2) && decide (i ≠ j)))
(thinnedInstance I (fun i => decide (s.1 i ≤ s.2.1))) s.2.2 (v,true)) ≠
bijunctiveOutput rep I ε s.1 s.2.1 s.2.2 v then (1 : ℝ) else 0
Integrable (fun s => ∑ v, C v s) μ ∧
(∫ s, ∑ v, C v s ∂μ) ≤ (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-deletion sensitivity step.