AFTD Auto-Formalizing Theoretical Domains

graph_cut_dist

def

The unnormalized cut distance d_□(G, H) between two simple graphs G and H on the same finite vertex set V is the minimum over all bijections π : V ≃ V of the cut norm of the difference matrix A_G^π - A_H.

Statement

noncomputable def graph_cut_dist {V : Type*} [Fintype V] [DecidableEq V]
    (G H : SimpleGraph V) : ℝ
Defined in
arXiv:2611.05048, Section 1
Verified
04 Nov 2026
Axioms
none listed
Built on 1
  • matrix_cut_normThe cut norm of a real matrix M indexed by finite sets α and β is the maximum over all subsets S ⊆ α and T ⊆ β of the absolute value of…

Read back from the Lean

Given a finite type V with decidable equality and two simple graphs G and H on V, graph_cut_dist G H defines a real number equal to the minimum over all permutations π of V (i.e., π : Equiv.Perm V) of the cut norm of the difference between the adjacency matrix of G and the permutation of the adjacency matrix of H by π.

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 unnormalized cut distance d_□(G, H) between two simple graphs on the same finite vertex set V is the minimum over all bijections π of the cut norm of A_G^π - A_H. -/
noncomputable def graph_cut_dist {V : Type*} [Fintype V] [DecidableEq V]
    (G H : SimpleGraph V) : ℝ := by
  classical
  exact (Finset.univ : Finset (Equiv.Perm V)).inf' ⟨Equiv.refl V, Finset.mem_univ _⟩
    (fun π => matrix_cut_norm (fun v v' =>
      (if G.Adj v v' then (1 : ℝ) else 0) - (if H.Adj (π v) (π v') then 1 else 0)))
See it in the graphDiscuss this resultChallenge it