The deleted-instance seed is a marginal of the original common seed
ProvedStabilityDichotomies.Bijunctive.bijunctive_deleted_seed_is_shared_priority_marginalDiscard the priority of one constraint occurrence from a Definition 4.8 random seed, reindex the remaining priorities, and retain the common cutoff and all exponential shifts. The resulting random seed has exactly the Definition 4.8 seed law of the instance with that occurrence deleted.
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.bijunctive_deleted_seed_is_shared_priority_marginal {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (c : Constraint Γ V)
(ε : ℝ) (hε : 0 < ε)
(e : Fin I.constraints.card ≃ Option (Fin (I.delete c).constraints.card)) :
Measure.map (fun z : (Fin I.constraints.card → ℝ) × ℝ × (Literal V → ℝ) =>
(fun i : Fin (I.delete c).constraints.card => z.1 (e.symm (some i)), z.2))
(bijunctiveSeedMeasure rep I ε) = bijunctiveSeedMeasure rep (I.delete c) ε := 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, common-randomness deletion coupling.