simple_graph_cut_rank
For a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset X : Finset V, simple_graph_cut_rank G X is the rank over ZMod 2 of the submatrix of G.adjMatrix (ZMod 2) with rows indexed by X and columns indexed by the complement Xᶜ.
Statement
noncomputable def simple_graph_cut_rank {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) : ℕ
- Defined in
- arXiv:2511.19585 Eq. (2.19)
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 2
- 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,…
- 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 ∅ ∅ ∅…
Read back from the Lean
The definition simple_graph_cut_rank takes a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finset X : Finset V. It returns the natural number given by the rank (over the field ZMod 2) of the submatrix of G's adjacency matrix (over ZMod 2) whose rows are indexed by the elements of X and whose columns are indexed by the elements of the complement Xᶜ (i.e., V \ X).
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
/-- The rank over F₂ of the cut submatrix between X and V \ X. -/ noncomputable def simple_graph_cut_rank {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) : ℕ := Matrix.rank ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥X → V) (Subtype.val : ↥(Xᶜ) → V))