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)))