Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Proposition 42 (⇐), p. 28 — a (d+1)-dimensional pseudo-cube B gives a d-dimensional good complex C(B)

Proved
MulticlassDS.NatGap.prop42_pseudo_cube_good_complex

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

good-complexp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pseudo-cubesimplicial-complex

Let B⊆Yd+1B \subseteq \mathcal Y^{d+1}B⊆Yd+1 be a pseudo-cube of dimension d+1d + 1d+1. Then the complex C(B)C(B)C(B), whose faces are the subsets of the sets {(yi,i):i∈[d+1]}\{(y_i, i) : i \in [d+1]\}{(yi​,i):i∈[d+1]} for (y1,…,yd+1)∈B(y_1, \dots, y_{d+1}) \in B(y1​,…,yd+1​)∈B, is a good simplicial complex of dimension ddd.

This is the converse half of the equivalence between pseudo-cubes and good complexes; together with the first half it shows that every concept class of this kind is a properly colored good complex and conversely.

Formalization Note The paper states the converse for a "ddd-dimensional pseudo-cube" and a "(d−1)(d-1)(d−1)-dimensional" complex; it is indexed here by d+1d + 1d+1 and ddd to avoid natural-number subtraction (at d=0d = 0d=0 the page's complex would be "(−1)(-1)(−1)-dimensional"). The vertex type is Y×\mathcal Y \timesY× Fin (d + 1); only the vertices that occur in faces matter. Replacement is the version with a new vertex.

Preamble
import Mathlib
import Definitions.Def_MulticlassDS_NatGap_Dimensions
import Definitions.Def_MulticlassDS_NatGap_Complexes
Formal statement
namespace MulticlassDS.NatGap

theorem prop42_pseudo_cube_good_complex {Y : Type*} (d : ℕ) (B : Set (Fin (d + 1) → Y))
    (hB : IsPseudoCube B) :
    IsGood (complexOf B) d := by sorry

end MulticlassDS.NatGap
Source
Brukhim, Carmon, Dinur, Moran, Yehudayoff, A Characterization of Multiclass Learnability, arXiv:2203.01550v1, p. 28, Proposition 42, second sentence (pseudo-cube ⟹ good complex)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me