Horn thinning output height is bounded by non-isolated variables
ProvedStabilityDichotomies.Solvability.horn_thinning_nonisolated_height_boundconstraint-satisfaction
For a satisfiable Horn instance, the least solution of every thinned subinstance is false outside the variables appearing in the original constraints. Consequently its number of ones is at most the number of original non-isolated variables.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Thinning noncomputable section open scoped Classical BigOperators Interval open MeasureTheory StabilityDichotomies.Solvability
Formal statement
theorem StabilityDichotomies.Solvability.horn_thinning_nonisolated_height_bound (Γ : Language)
(hHorn : ∀ R ∈ Γ.relations, ∀ x y : Fin R.arity → Bool,
x ∈ R.tuples → y ∈ R.tuples → (fun i => x i && y i) ∈ R.tuples)
(V : Type) [Fintype V] (I : Instance Γ V) (hSat : Satisfiable I)
(mask : Fin I.constraints.card → Bool) :
(∑ v : V, if extremalSolution (thinnedInstance I mask) false v then (1 : ℝ) else 0) ≤
((I.constraints.toFinset.biUnion fun c => Finset.univ.image c.scope).card : ℝ) := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, proof of Theorem 4.3, pp. 16–17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf