AFTD Auto-Formalizing Theoretical Domains

tripartite_turan_hypergraph_three_uniform

theoremverified

For any family of finite sets V : ZMod 3 → Finset α, the tripartite Turán hypergraph tripartite_turan_hypergraph V is 3-uniform (is_three_uniform).

Statement

theorem tripartite_turan_hypergraph_three_uniform {α : Type*} [DecidableEq α]
    (V : ZMod 3 → Finset α) : is_three_uniform (tripartite_turan_hypergraph V)
Source
arXiv:2611.16654 Section 3
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • tripartite_turan_hypergraphGiven a type α with decidable equality and a family of finite sets V : ZMod 3 → Finset α, tripartite_turan_hypergraph V is the finite set…
  • is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.
Used by 1

Read back from the Lean

For any type α with decidable equality, and for any family V : ZMod 3 → Finset α of three finite subsets of α, the tripartite Turán hypergraph on V is 3-uniform.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, a hypergraph is 3-uniform if every edge has cardinality 3. The edges of the tripartite Turán hypergraph are defined by filtering the 3-element subsets (powersetCard 3) of the vertex set by a partition condition. Consequently, every edge has size 3 by construction.

  1. To show 3-uniformity, it suffices to prove that an arbitrary edge e in the hypergraph has cardinality 3.

    By definition of 3-uniformity (is_three_uniform), every edge in the hypergraph must have cardinality 3. We let e be an arbitrary edge and assume that e belongs to the tripartite Turán hypergraph (he).

    line 4

      intro e he
  2. The edge e has cardinality 3, completing the proof.

    Unfolding the definition of tripartite_turan_hypergraph using Finset.mem_filter and Finset.mem_powersetCard reveals that every edge e is selected from the 3-element subsets (powersetCard 3) of the union of the parts. In particular, the assumption that e belongs to the hypergraph directly contains the requirement that |e| = 3.

    lines 5–6

    uses tripartite_turan_hypergraph, Finset.mem_filter, Finset.mem_powersetCard

      simp only [tripartite_turan_hypergraph, Finset.mem_filter, Finset.mem_powersetCard] at he
      exact he.1.2
tripartite_turan_hypergraph
The hypergraph whose edges are the 3-element subsets of the union of three parts V(0), V(1), V(2) that either meet each part in 1 vertex, or meet one part in 2 vertices and the cyclic next part in 1 vertex.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filtering predicate.
Finset.mem_powersetCard
A finite set belongs to powersetCard n s if and only if it is a subset of s and has cardinality n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The tripartite Turán hypergraph is 3-uniform. -/theorem tripartite_turan_hypergraph_three_uniform {α : Type*} [DecidableEq α]    (V : ZMod 3 → Finset α) : is_three_uniform (tripartite_turan_hypergraph V) := by  intro e he  simp only [tripartite_turan_hypergraph, Finset.mem_filter, Finset.mem_powersetCard] at he  exact he.1.2
See it in the graphDiscuss this resultChallenge it