Proposition 46, p. 31 — the coset complex of Theorem 45 has dimension d − 1, is good and has no empty squares
ProvedMulticlassDS.NatGap.prop46_coset_complex_goodcoset-complexgood-complexgroup-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplicial-complex
Let be a finite group, , and subgroups such that
- for every , and
- the coset complex contains no empty square.
Then has dimension , is good (finite, pure, properly colorable with colors, and satisfies replacement), and has no empty squares.
This is the step that turns the group-theoretic construction of Theorem 45 into a good complex, from which Proposition 42 produces a -dimensional pseudo-cube.
Formalization Note The hypotheses are exactly "as in Theorem 45". The dimension is with natural-number subtraction, which is exact because ; the coloring then takes values in Fin (d - 1 + 1), i.e. colors.
Preamble
import Mathlib import Definitions.Def_MulticlassDS_NatGap_Dimensions import Definitions.Def_MulticlassDS_NatGap_Complexes
Formal statement
namespace MulticlassDS.NatGap
theorem prop46_coset_complex_good {F : Type*} [Group F] [Finite F] (d : ℕ) (hd : 1 < d)
(Hs : Fin d → Subgroup F)
(h1 : ∀ i : Fin d, ∃ z : F, (∀ j : Fin d, j ≠ i → z ∈ Hs j) ∧ z ∉ Hs i)
(h2 : NoEmptySquares (cosetComplex Hs)) :
IsGood (cosetComplex Hs) (d - 1) ∧ NoEmptySquares (cosetComplex Hs) := by sorry
end MulticlassDS.NatGap
Source
Brukhim, Carmon, Dinur, Moran, Yehudayoff, A Characterization of Multiclass Learnability, arXiv:2203.01550v1, p. 31, Proposition 46
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.