An occurrence is omitted with probability ε/2 under the full seed law
ProvedStabilityDichotomies.Bijunctive.bijunctive_seed_occurrence_omission_probabilityUnder the complete Definition 4.8 product seed law, for , the probability that a fixed original constraint occurrence is omitted from the graph subinstance is exactly .
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.bijunctive_seed_occurrence_omission_probability {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (ε : ℝ)
(hε : 0 < ε) (hε1 : ε ≤ 1) (i : Fin I.constraints.card) :
(bijunctiveSeedMeasure rep I ε {seed | 1 - ε / 2 < seed.1 i}).toReal = ε / 2 := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, Definition 4.8 and proof of Theorem 4.9.