AFTD Auto-Formalizing Theoretical Domains

tbt_sn_opt

def

For a finite type V and a simple graph T on V, tbt_sn_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H f over all finite types W, subcubic trees H on W, and injective maps f : V ↪ W.

Statement

noncomputable def tbt_sn_opt {V : Type} [Fintype V] (T : SimpleGraph V) : ℕ
Defined in
arXiv:2610.39863, Section 3
Verified
02 Nov 2026
Axioms
none listed
Built on 2
  • tree_routing_costFor any finite type V, type W, simple graph T on V, simple graph H on W, and function f : V → W, tree_routing_cost T H f is the sum over…
  • is_subcubic_treeA finite simple graph is a subcubic tree if it is connected, acyclic, and every vertex has degree at most 3.
Used by 1

Read back from the Lean

Given a finite type V and a simple graph T on V, tbt_sn_opt T is defined as the infimum (in ℕ) of the set of natural numbers c for which there exist: 1. a finite type W (in Type 0), 2. a simple graph H on W such that H is a subcubic tree (i.e., H is a connected, acyclic graph and every vertex of W has degree at most 3 in H), and 3. an injective function f : V ↪ W, such that the routing cost of T in H under f equals c, where the routing cost is the sum over all edges e = {u, v} of T (in T.edgeFinset) of the graph distance in H between f u and f v.

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 optimal Tree in Binary Tree with Steiner Nodes (TBT-SN) routing cost. -/
noncomputable def tbt_sn_opt {V : Type} [Fintype V] (T : SimpleGraph V) : ℕ := open Classical in
  sInf { c : ℕ | ∃ (W : Type) (_ : Fintype W) (H : SimpleGraph W) (_ : is_subcubic_tree H)
    (f : V ↪ W), tree_routing_cost T H f = c }
See it in the graphDiscuss this resultChallenge it