balanced_multipartite_max_tripartite_info_nonneg
For any natural numbers k and s, the maximum tripartite information balanced_multipartite_max_tripartite_info k s of the complete multipartite graph with k parts of size s is at least 0.
Statement
theorem balanced_multipartite_max_tripartite_info_nonneg (k s : ℕ) :
0 ≤ balanced_multipartite_max_tripartite_info k s- Source
- folklore
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- balanced_multipartite_max_tripartite_infoFor natural numbers k and s, balanced_multipartite_max_tripartite_info k s is the maximum tripartite information…
- simple_graph_max_tripartite_info_nonnegFor every finite simple graph G, the maximum tripartite information simple_graph_max_tripartite_info G is at least 0, witnessed by the…
Read back from the Lean
For all natural numbers k and s, the maximum tripartite information (balanced_multipartite_max_tripartite_info k s) of the complete balanced multipartite graph with k parts of size s 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 balanced complete multipartite graph is defined directly as the maximum tripartite information of the complete multipartite graph with k parts of size s. The non-negativity of this quantity follows immediately by applying the general theorem that the maximum tripartite information of any finite simple graph is at least 0.
The maximum tripartite information of the balanced complete multipartite graph with k parts of size s is at least 0 (0 ≤ balanced_multipartite_max_tripartite_info k s).
Unfolding the definition of balanced_multipartite_max_tripartite_info expresses it as the maximum tripartite information of the complete multipartite graph with k parts each of size s (SimpleGraph.completeMultipartiteGraph (fun _ : Fin k => Fin s)). The inequality then holds directly by simple_graph_max_tripartite_info_nonneg, which proves that the maximum tripartite information of any finite simple graph is non-negative.
uses
simple_graph_max_tripartite_info_nonneg,SimpleGraph.completeMultipartiteGraphunfold balanced_multipartite_max_tripartite_info exact simple_graph_max_tripartite_info_nonneg (SimpleGraph.completeMultipartiteGraph fun x : Fin k => Fin s)
simple_graph_max_tripartite_info_nonneg- For any finite simple graph G, its maximum tripartite information is at least 0.
SimpleGraph.completeMultipartiteGraph- The complete multipartite graph associated with an indexed collection of vertex sets, having an edge between two vertices if and only if they belong to different parts.
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 complete balanced multipartite graph is nonnegative. -/theorem balanced_multipartite_max_tripartite_info_nonneg (k s : ℕ) : 0 ≤ balanced_multipartite_max_tripartite_info k s := by unfold balanced_multipartite_max_tripartite_info exact simple_graph_max_tripartite_info_nonneg (SimpleGraph.completeMultipartiteGraph fun x : Fin k => Fin s)