Lemma 4.7 — a Majority-excluding relaxation
ProvedSymBoolPCSP.CFixing.lemma_4_7booleanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite, symmetric, folded, idempotent family of Boolean promise relations such that for some odd . Then there is such that is a relaxation of for one of
- , , with odd; or
- , , with and .
Lemma 4.12 analyses the polymorphisms of these two relaxations.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.CFixing
/-- Lemma 4.7 (p. 19): if `Γ` is symmetric, folded and idempotent and `Maj_L ∉ Pol(Γ)` for some
odd `L`, then `Γ′ = {(P, Q)}` is a relaxation of `Γ` for either
`P = Ham_k({(k + 1)/2})`, `Q = Ham_k({0, 1, …, k − 1})`, `k ≥ 3` odd, or
`P = Ham_k({1, k})`, `Q = Ham_k({0, 1, …, k} ∖ {b})`, `k ≥ 3`, `b ∈ {2, …, k − 1}`. -/
theorem lemma_4_7 {τ : Type} [Fintype τ] {ar : τ → ℕ} (𝔸 𝔹 : RelStruct τ ar Bool)
(hPF : IsPromiseFamily 𝔸 𝔹) (hsym : IsSymmetricFamily 𝔸 𝔹) (hfold : IsFoldedFamily 𝔸 𝔹)
(hidem : IsIdempotentFamily 𝔸 𝔹) (L : ℕ) (hL : Odd L) (hMaj : ¬ IsPolymorphism 𝔸 𝔹 (Maj L)) :
∃ k : ℕ,
(3 ≤ k ∧ Odd k ∧ IsRelaxation 𝔸 𝔹 (Ham k {(k + 1) / 2}) (Ham k (Set.Iic (k - 1)))) ∨
(3 ≤ k ∧ ∃ b : ℕ, 2 ≤ b ∧ b ≤ k - 1 ∧
IsRelaxation 𝔸 𝔹 (Ham k {1, k}) (Ham k (Set.Iic k \ {b}))) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 19, Lemma 4.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.