Bounding a set whose m-subsets all evaluate to 1 under a disjoint-family bound
ProvedSymBoolPCSP.CFixing.card_lt_of_subsets_truebooleancombinatoricspolymorphismspromise-csp
Let , and . Suppose that for every with , and that at most pairwise disjoint sets can satisfy for all (that is, any such family has ). Then .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- If every `m`-element subset `Z ⊆ I` has `f(e_Z) = 1` and at most `c` pairwise disjoint sets
can have `f(e_{S_i}) = 1`, then `|I| < m (c + 1)` (BG, proof of Lemma 4.12, Case 1). -/
theorem card_lt_of_subsets_true {L : ℕ} (f : (Fin L → Bool) → Bool) (c m : ℕ)
(I : Finset (Fin L)) (hI : ∀ Z ⊆ I, Z.card = m → f (indicator Z) = true)
(hdisj : ∀ (ℓ : ℕ) (S : Fin ℓ → Finset (Fin L)), (∀ i j, i ≠ j → Disjoint (S i) (S j)) →
(∀ i, f (indicator (S i)) = true) → ℓ ≤ c) :
I.card < m * (c + 1) := 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 (with Corollary 4.11)