AFTD Auto-Formalizing Theoretical Domains

is_lap_trace_minimal

def

A graph G on a finite vertex set V is Laplacian trace-minimal in the class of d-regular graphs if G is d-regular and its Laplacian trace sequence is lexicographically less than or equal to the Laplacian trace sequence of every d-regular graph on V.

Statement

open scoped Classical in
def is_lap_trace_minimal {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) : Prop
Defined in
arXiv:2610.36127 Definition 31
Verified
28 Oct 2026
Axioms
none listed
Built on 3
  • graph_lap_trace_seqFor a graph G on a finite vertex set V, its Laplacian trace sequence (ℓ_i(G))_{i=1}^∞ is the sequence of real numbers tr(L(G)^i) for…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For a finite type V, a natural number d, and a simple graph G on V, is_lap_trace_minimal d G asserts that: 1. G is regular of degree d; and 2. For every simple graph H on the same vertex type V, if H is regular of degree d, then toLex (graph_lap_trace_seq G) ≤ toLex (graph_lap_trace_seq H), meaning that the sequence (Tr((L(G))^i))_{i ∈ ℕ+} is lexicographically less than or equal to (Tr((L(H))^i))_{i ∈ ℕ+} (i.e., either the two trace sequences are identical, or at the smallest index i ≥ 1 where they differ, the trace of the i-th power of the Laplacian of G is strictly less than that of H).

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

open scoped Classical in
/-- A d-regular graph G is Laplacian trace-minimal if its Laplacian trace sequence is lexicographically minimal among all d-regular graphs on the same vertex set. -/
def is_lap_trace_minimal {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) : Prop :=
  open scoped Classical in
  G.IsRegularOfDegree d ∧
    ∀ H : SimpleGraph V, H.IsRegularOfDegree d →
      toLex (graph_lap_trace_seq G) ≤ toLex (graph_lap_trace_seq H)
See it in the graphDiscuss this resultChallenge it