simple_graph_max_tripartite_info_nonneg
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
- simple_graph_max_tripartite_infoFor any finite simple graph G with decidable equality and decidable adjacency, simple_graph_max_tripartite_info G is the maximum of…
- tree_graph_state_tripartite_info_trivial_zeroFor any finite graph G on type V with decidable equality and decidable adjacency, tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅…
- tree_graph_state_tripartite_infoFor a simple graph G on a finite type V with decidable equality and decidable adjacency, and four finite subsets A, B, C, D : Finset V,…
- Used by 1
- balanced_multipartite_max_tripartite_info_nonnegFor any natural numbers k and s, the maximum tripartite information balanced_multipartite_max_tripartite_info k s of the complete…
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.
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).
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))
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.
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
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.
uses
tree_graph_state_tripartite_info_trivial_zerohave 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
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.
uses
Finset.le_max',Finset.mem_image_of_mem,Finset.mem_univunfold 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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 _))