AFTD Auto-Formalizing Theoretical Domains

simple_graph_max_tripartite_info

deforiginal

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

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⟩)
See it in the graphDiscuss this resultChallenge it