AFTD Auto-Formalizing Theoretical Domains

simple_graph_max_tripartite_info_nonneg

theoremverified

For every finite simple graph G, the maximum tripartite information simple_graph_max_tripartite_info G is at least 0, witnessed by the constant four-coloring with three empty parts.

Statement

theorem simple_graph_max_tripartite_info_nonneg
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    0 ≤ simple_graph_max_tripartite_info G
Source
arXiv:2511.19585
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For every finite type V with decidable equality and every simple graph G on V with decidable adjacency, simple_graph_max_tripartite_info G is greater than or equal to 0.

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

The maximum tripartite information of a finite graph G is defined as the maximum over all 4-colorings of the vertex set of the tripartite information of the resulting four color classes. The proof evaluates this functional at the constant coloring that assigns every vertex to color 0, which partitions the vertex set into (V, ∅, ∅, ∅). Because the tripartite information of this trivial partition is known to be 0, and the maximum over all colorings is at least the value achieved by any specific coloring, the maximum tripartite information is at least 0.

  1. Define f(c) as the tripartite information of the partition of vertices induced by a 4-coloring c.

    We introduce the auxiliary function f mapping each vertex coloring c : V → Fin 4 to the tripartite information of the four fiber sets c⁻¹(0), c⁻¹(1), c⁻¹(2), and c⁻¹(3).

    lines 5–10

      let f : (V → Fin 4) → ℤ := fun c =>
        tree_graph_state_tripartite_info G
          (Finset.univ.filter (fun v => c v = 0))
          (Finset.univ.filter (fun v => c v = 1))
          (Finset.univ.filter (fun v => c v = 2))
          (Finset.univ.filter (fun v => c v = 3))
  2. Under the constant coloring c₀ ≡ 0, the fiber for color 0 is all of V, while the fibers for colors 1, 2, and 3 are empty.

    For color 0, every vertex satisfies c₀(v) = 0, so the filtered subset is the universal set Finset.univ. For colors 1, 2, and 3, no vertex satisfies 0 = 1, 0 = 2, or 0 = 3, so each corresponding filtered subset is empty. Each equality is established by set extensionality followed by simplification.

    lines 11–18

      have h1 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (0:Fin 4)) = Finset.univ := by
        ext v; simp
      have h2 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (1:Fin 4)) = ∅ := by
        ext v; simp
      have h3 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (2:Fin 4)) = ∅ := by
        ext v; simp
      have h4 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (3:Fin 4)) = ∅ := by
        ext v; simp
  3. The tripartite information of the constant zero coloring is 0, so f(c₀) = 0.

    Rewriting f(c₀) using the fiber descriptions from the previous step gives the tripartite information on the partition (univ, ∅, ∅, ∅). By tree_graph_state_tripartite_info_trivial_zero, this value is 0.

    lines 19–22

    uses tree_graph_state_tripartite_info_trivial_zero

      have hval : f (fun _ => 0) = 0 := by
        change tree_graph_state_tripartite_info G _ _ _ _ = 0
        rw [h1, h2, h3, h4]
        exact tree_graph_state_tripartite_info_trivial_zero G
  4. The maximum tripartite information of G is at least 0.

    By definition, simple_graph_max_tripartite_info G is the maximum of f(c) over all colorings c. Since c₀ is an element of the universe of colorings, f(c₀) belongs to the image set via Finset.mem_image_of_mem and Finset.mem_univ. Because the maximum of a finite set is at least any of its members (Finset.le_max'), and f(c₀) = 0, we conclude 0 ≤ simple_graph_max_tripartite_info G.

    lines 23–26

    uses Finset.le_max', Finset.mem_image_of_mem, Finset.mem_univ

      unfold simple_graph_max_tripartite_info
      change 0 ≤ (((Finset.univ : Finset (V → Fin 4)).image f).max' _)
      rw [← hval]
      exact Finset.le_max' _ (f (fun _ => 0)) (Finset.mem_image_of_mem f (Finset.mem_univ _))
Finset.le_max'
Every element of a nonempty finite set with a linear order is less than or equal to the maximum element of that set.
Finset.mem_image_of_mem
If an element a belongs to a set s, then f(a) belongs to the image of s under f.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set Finset.univ.
tree_graph_state_tripartite_info_trivial_zero
For any simple graph G, the tripartite information of the partition (univ, ∅, ∅, ∅) is 0.

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 maximum tripartite information of any finite graph state is nonnegative. -/theorem simple_graph_max_tripartite_info_nonneg    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :    0 ≤ simple_graph_max_tripartite_info G := by  let f : (V → Fin 4) → ℤ := fun c =>    tree_graph_state_tripartite_info G      (Finset.univ.filter (fun v => c v = 0))      (Finset.univ.filter (fun v => c v = 1))      (Finset.univ.filter (fun v => c v = 2))      (Finset.univ.filter (fun v => c v = 3))  have h1 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (0:Fin 4)) = Finset.univ := by    ext v; simp  have h2 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (1:Fin 4)) = ∅ := by    ext v; simp  have h3 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (2:Fin 4)) = ∅ := by    ext v; simp  have h4 : (Finset.univ : Finset V).filter (fun v => (fun (_ : V) => (0:Fin 4)) v = (3:Fin 4)) = ∅ := by    ext v; simp  have hval : f (fun _ => 0) = 0 := by    change tree_graph_state_tripartite_info G _ _ _ _ = 0    rw [h1, h2, h3, h4]    exact tree_graph_state_tripartite_info_trivial_zero G  unfold simple_graph_max_tripartite_info  change 0 ≤ (((Finset.univ : Finset (V → Fin 4)).image f).max' _)  rw [← hval]  exact Finset.le_max' _ (f (fun _ => 0)) (Finset.mem_image_of_mem f (Finset.mem_univ _))
See it in the graphDiscuss this resultChallenge it