is_adj_trace_minimal
def
A graph G on a finite vertex set V is trace-minimal in the class of d-regular graphs if G is d-regular and its adjacency trace sequence is lexicographically less than or equal to the adjacency trace sequence of every d-regular graph on V.
Statement
open scoped Classical in def is_adj_trace_minimal {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.36127 Definition 14
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 3
- graph_adj_trace_seqFor a graph G on a finite vertex set V, its adjacency trace sequence (a_i(G))_{i=1}^∞ is the sequence of real numbers tr(A(G)^i) for…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For a finite type V, a natural number d, and a simple graph G on V, is_adj_trace_minimal d G asserts that G is d-regular, and for every simple graph H on V, if H is d-regular, then the sequence (Tr((adjMatrix ℝ G)^i))_{i : ℕ+} is less than or equal to (Tr((adjMatrix ℝ H)^i))_{i : ℕ+} with respect to the lexicographical ordering on functions ℕ+ → ℝ (via toLex).
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 trace-minimal if its adjacency trace sequence is lexicographically minimal among all d-regular graphs on the same vertex set. -/ def is_adj_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_adj_trace_seq G) ≤ toLex (graph_adj_trace_seq H)