Minimal 1-sets are small under (Ham_{b+r}{1,b+r}, Ham_{b+r}({0..b+r} \ {b}))
ProvedSymBoolPCSP.CFixing.card_lt_of_minimalbooleanpolymorphismspromise-csp
Let , and let be a folded polymorphism of the promise relation . If is minimal with , meaning that for every proper subset , 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 2 of BG Lemma 4.12: let `f` be a folded polymorphism of
`(Ham_{b+r}({1, b+r}), Ham_{b+r}({0, …, b+r} \ {b}))` with `b ≥ 1`. If `S` is minimal with
`f(e_S) = 1` (all proper subsets `T ⊂ S` have `f(e_T) = 0`), then `|S| < b`. -/
theorem card_lt_of_minimal {L b r : ℕ} (f : (Fin L → Bool) → Bool) (hfold : IsFolded f)
(hb : 1 ≤ b)
(hpol : PolOf (Ham (b + r) {1, b + r}) (Ham (b + r) (Set.Iic (b + r) \ {b})) f)
(S : Finset (Fin L)) (hS : f (indicator S) = true)
(hmin : ∀ T ⊂ S, f (indicator T) = false) :
S.card < b := 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, pp. 24–25