Majority-closed Boolean relations are determined by their binary projections
ProvedStabilityDichotomies.Bijunctive.majority_pairwise_extensioncombinatoricsconstraint-satisfactionlogic
Let R be a nonempty finite relation on Boolean tuples, closed under coordinatewise majority. If a Boolean tuple x has the property that every pair of its coordinates is matched by some tuple of R, then x itself belongs to R. This two-decomposability property is the key construction step for fixed two-CNF representations of bijunctive relations.
Preamble
import Mathlib noncomputable section open scoped Classical BigOperators
Formal statement
theorem StabilityDichotomies.Bijunctive.majority_pairwise_extension {ι : Type} [Fintype ι] (R : Finset (ι → Bool))
(hR : R.Nonempty) (hmajority : ∀ a b c, a ∈ R → b ∈ R → c ∈ R →
(fun i => (a i && b i) || (a i && c i) || (b i && c i)) ∈ R)
(x : ι → Bool) (hpairs : ∀ i j : ι, ∃ y ∈ R, y i = x i ∧ y j = x j) : x ∈ R := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, use of two-CNF representations in §4.2.2, p. 19, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf