Fact 3.12 — all (k−i+1)-clauses form a t-extremal k-CNF,
OpenMajorityDepthThree.Exact.Supplement.all_clauses_extremalcircuit-complexityextremal-combinatoricsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and with . Let be a set of variables and the CNF consisting of all positive clauses on variables of . Then is monotone and -uniform, it is a -extremal -CNF — a valid -threshold CNF of width at most whose number of -transversals equals the maximum over all -threshold CNFs of width at most on , negative literals allowed — and
For this gives the second line of Theorem 3.10, when . The competitor class is all width- CNFs, wider than in Fact 3.2, where competitors have the clique's own width.
Differences from the source:
- encoding: n variables, t = n − k + i → the carrier Fin n with V = univ, and t written as the natural number n + i − k under k ≤ n + i; reason: relabeling changes nothing; k ≤ n + i is exactly t ≥ 0, so no truncation occurs
Preamble
import Definitions.Def_MajorityDepthThree_Exact_Supplement_Constructions set_option autoImplicit false
Formal statement
namespace MajorityDepthThree.Exact.Supplement
open MajorityDepthThree.Exact
/-- Fact 3.12 (p. 10): for `n, k ≥ 1`, `1 ≤ i ≤ k` and `t = n - k + i ≥ 0`, the monotone
CNF of all `(k - i + 1)`-clauses on `n` variables is `(k - i + 1)`-uniform and
`t`-extremal among all (signed) `t`-threshold `k`-CNFs on `n` variables, and
`Θ(n, t, k) = binom(n, t)`. Here `t` is written `n + i - k` (no truncation since
`k ≤ n + i`). -/
theorem all_clauses_extremal (n k i : ℕ) (hn : 1 ≤ n) (hk : 1 ≤ k) (hi : 1 ≤ i)
(hik : i ≤ k) (hkn : k ≤ n + i) :
let V : Finset (Fin n) := Finset.univ
let F := clique V (k - i + 1)
Monotone F ∧ Uniform (k - i + 1) F ∧ Extremal V F (n + i - k) k ∧
thetaMax V (n + i - k) k = Nat.choose n (n + i - k) := by sorry
end MajorityDepthThree.Exact.Supplement
Source
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard, STOC 2027 submission #677 (October 2026), p.10, Fact 3.12 (with Definition 2.6, p.7)