Graph-deletion bit changes under the full bijunctive seed law
ProvedStabilityDichotomies.Bijunctive.expected_seed_graph_deletion_changes_boundUnder the full Definition 4.8 priority, cutoff, and exponential-shift seed law for a satisfiable input, fix a variable. Keeping the random feasible-root instance fixed, sum the changes in that bit over deletion of each occurrence from the random graph subinstance. This count is integrable and has expectation 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.expected_seed_graph_deletion_changes_bound {Γ : Language} {V : Type} [Fintype V] [Nonempty V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I)
(ε : ℝ) (hε : 0 < ε) (v : V) :
let μ := bijunctiveSeedMeasure rep I ε
let C := fun 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 C μ ∧ (∫ s, C s ∂μ) ≤
(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, first sensitivity step.