Small witnesses plus a disjoint-family bound give a C-fixing function
ProvedSymBoolPCSP.CFixing.cfixing_of_small_witnessbooleanpolymorphismspromise-csp
Let with , and let . Suppose that every with contains some with and , and that at most pairwise disjoint sets can satisfy for all (that is, any such family has ). Then is -fixing: there is with such that for every vanishing on .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- A generic `C`-fixing criterion (BG, proof of Lemma 4.12, Case 2): suppose `f(0) = 0`,
every `X` with `f(e_X) = 1` contains some `T` with `f(e_T) = 1` and `|T| ≤ B`, and at most `c`
pairwise disjoint sets `S_i` can have `f(e_{S_i}) = 1`. Then `f` is `(c + 1) B`-fixing. -/
theorem cfixing_of_small_witness {L : ℕ} (f : (Fin L → Bool) → Bool)
(h0 : f (fun _ => false) = false) (B c : ℕ)
(hsmall : ∀ X : Finset (Fin L), f (indicator X) = true →
∃ T ⊆ X, f (indicator T) = true ∧ T.card ≤ B)
(hdisj : ∀ (ℓ : ℕ) (S : Fin ℓ → Finset (Fin L)), (∀ i j, i ≠ j → Disjoint (S i) (S j)) →
(∀ i, f (indicator (S i)) = true) → ℓ ≤ c) :
IsCFixing ((c + 1) * B) f := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, proof of Lemma 4.12, Case 2, p. 25