simple_graph_max_tripartite_info
For 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 G A B C D over all four-colorings c : V → Fin 4, taking A, B, C, D as the four color classes.
Statement
noncomputable def simple_graph_max_tripartite_info {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℤ
- Related work
- arXiv:2511.19585
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 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
Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, simple_graph_max_tripartite_info G is defined as the maximum (as an integer) over all functions c : V → Fin 4 of tree_graph_state_tripartite_info G A B C D, where:
- A = {v : V | c v = 0}
- B = {v : V | c v = 1}
- C = {v : V | c v = 2}
- D = {v : V | c v = 3}
as finite subsets (Finset V) of V.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Maximum tripartite information of a graph state over all four-partitions of its vertices. -/ noncomputable def simple_graph_max_tripartite_info {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℤ := ((Finset.univ : Finset (V → Fin 4)).image (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)))).max' (by rw [Finset.image_nonempty, Finset.univ_nonempty_iff] exact ⟨fun _ => 0⟩)