AFTD Auto-Formalizing Theoretical Domains

simple_graph_cut_rank

def

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

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