m somewhere-increasing coordinates evaluate to 1 under (Ham_{2m+1}{m+1}, Ham_{2m+1}{0..2m})
ProvedSymBoolPCSP.CFixing.subset_true_of_relax_majbooleanpolymorphismspromise-csp
Let and let be a folded polymorphism of the promise relation . Let with be such that every is somewhere-increasing for : there is with , and . Then .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Case 1 of BG Lemma 4.12: let `f` be a folded polymorphism of
`(Ham_{2m+1}({m+1}), Ham_{2m+1}({0, …, 2m}))` and let `Z` be an `m`-set of coordinates on each
of which `f` is somewhere-increasing. Then `f(e_Z) = 1`. -/
theorem subset_true_of_relax_maj {L m : ℕ} (f : (Fin L → Bool) → Bool) (hfold : IsFolded f)
(hpol : PolOf (Ham (2 * m + 1) {m + 1}) (Ham (2 * m + 1) (Set.Iic (2 * m))) f)
(Z : Finset (Fin L)) (hZ : Z.card = m)
(hwit : ∀ j ∈ Z, ∃ Y : Finset (Fin L), j ∉ Y ∧ f (indicator Y) = false ∧
f (indicator (insert j Y)) = true) :
f (indicator Z) = true := 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 1, p. 24