tree_graph_state_tripartite_info_trivial_zero
For any finite graph G on type V with decidable equality and decidable adjacency, tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ equals 0.
Statement
theorem tree_graph_state_tripartite_info_trivial_zero {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ = 0
- Source
- arXiv:2511.19585
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_cut_rankFor a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset X : Finset V,…
- 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
- square_grid_max_tripartite_info_nonnegFor every natural number n, the maximum tripartite information square_grid_graph_max_tripartite_info n of the n-by-n square grid graph…
- 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 every finite type V with decidable equality and every simple graph G on V with decidable adjacency, the quantity tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ equals 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 tripartite information of the partition (V, ∅, ∅, ∅) is defined as a signed sum of cut ranks of the subsets and their pairwise unions. Since any union with the empty set is trivial, the expression reduces entirely to cut ranks of the full vertex set V and the empty set ∅. The cut rank of ∅ vanishes because its submatrix has no rows, and the cut rank of V vanishes because its submatrix has no columns. Substituting these zero ranks into the formula immediately yields zero.
The cut rank of the empty set in G is 0.
The cut rank of a vertex subset X is defined as the rank over ℤ/2ℤ of the adjacency submatrix with rows indexed by X and columns indexed by Xᶜ. For X = ∅, the row index set is empty. By Matrix.rank_le_card_height, the rank of this submatrix is bounded by its number of rows, which by Fintype.card_coe and Finset.card_empty is 0. Since the rank is a natural number bounded by 0, omega concludes that it equals 0.
uses
Matrix.rank_le_card_height,Fintype.card_coe,Finset.card_emptydsimp [simple_graph_cut_rank] have h := Matrix.rank_le_card_height ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(∅ : Finset V) → V) (Subtype.val : ↥((∅ : Finset V)ᶜ) → V)) simp only [Fintype.card_coe, Finset.card_empty] at h omega
The cut rank of the universal set V in G is 0.
For X = V (the universal set), the column index set is Vᶜ, which by Finset.compl_univ is ∅. By Matrix.rank_le_card_width, the rank of the submatrix is at most its number of columns, which is 0 (by Fintype.card_coe and Finset.card_empty). Since the rank is a natural number bounded by 0, omega concludes that it equals 0.
uses
Matrix.rank_le_card_width,Finset.compl_univ,Fintype.card_coe,Finset.card_emptydsimp [simple_graph_cut_rank] have h := Matrix.rank_le_card_width ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(Finset.univ : Finset V) → V) (Subtype.val : ↥((Finset.univ : Finset V)ᶜ) → V)) simp only [Finset.compl_univ, Fintype.card_coe, Finset.card_empty] at h omega
Expanding tree_graph_state_tripartite_info on (V, ∅, ∅, ∅) reduces to a combination of cut ranks of V and ∅.
Unfolding the definition of tree_graph_state_tripartite_info G V ∅ ∅ ∅ yields an alternating sum of the cut ranks of the four sets V, ∅, ∅, ∅ and the pairwise unions V ∪ ∅, V ∪ ∅, and ∅ ∪ ∅. Applying Finset.union_empty simplifies these unions to V and ∅, leaving an integer linear combination involving only cut ranks of V and ∅.
uses
Finset.union_emptydsimp [tree_graph_state_tripartite_info] simp only [Finset.union_empty]
The tripartite information of (V, ∅, ∅, ∅) is 0.
Rewriting with the helper lemmas tree_graph_state_tripartite_info_trivial_zero_univ and tree_graph_state_tripartite_info_trivial_zero_empty replaces every cut rank term with 0. The resulting integer arithmetic expression 0 + 0 + 0 + 0 - 0 - 0 - 0 = 0 is evaluated and closed by ring.
uses
tree_graph_state_tripartite_info_trivial_zero_univ,tree_graph_state_tripartite_info_trivial_zero_emptyrw [tree_graph_state_tripartite_info_trivial_zero_univ, tree_graph_state_tripartite_info_trivial_zero_empty] ring
Matrix.rank_le_card_height- The rank of a matrix over a commutative ring is at most its number of rows (the cardinality of its row index set).
Matrix.rank_le_card_width- The rank of a matrix over a commutative ring is at most its number of columns (the cardinality of its column index set).
Fintype.card_coe- The cardinality of a finite set coerced to a subtype equals the cardinality of the finset itself.
Finset.card_empty- The empty set has cardinality zero.
Finset.compl_univ- The complement of the universal set of a finite type is the empty set.
Finset.union_empty- The union of any finite set with the empty set is the set itself.
tree_graph_state_tripartite_info_trivial_zero_univ- For any finite graph, the cut rank of the full vertex set is zero.
tree_graph_state_tripartite_info_trivial_zero_empty- For any finite graph, the cut rank of the empty set is zero.
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.
lemma tree_graph_state_tripartite_info_trivial_zero_empty {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : simple_graph_cut_rank G ∅ = 0 := by dsimp [simple_graph_cut_rank] have h := Matrix.rank_le_card_height ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(∅ : Finset V) → V) (Subtype.val : ↥((∅ : Finset V)ᶜ) → V)) simp only [Fintype.card_coe, Finset.card_empty] at h omegalemma tree_graph_state_tripartite_info_trivial_zero_univ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : simple_graph_cut_rank G Finset.univ = 0 := by dsimp [simple_graph_cut_rank] have h := Matrix.rank_le_card_width ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(Finset.univ : Finset V) → V) (Subtype.val : ↥((Finset.univ : Finset V)ᶜ) → V)) simp only [Finset.compl_univ, Fintype.card_coe, Finset.card_empty] at h omega/-- The trivial four-partition (V, ∅, ∅, ∅) of any finite graph has tripartite information zero. -/theorem tree_graph_state_tripartite_info_trivial_zero {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ = 0 := by dsimp [tree_graph_state_tripartite_info] simp only [Finset.union_empty] rw [tree_graph_state_tripartite_info_trivial_zero_univ, tree_graph_state_tripartite_info_trivial_zero_empty] ring