AFTD Auto-Formalizing Theoretical Domains

tbt_opt

def

For a finite type V and a simple graph T on V, tbt_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H id over all subcubic trees H on V.

Statement

noncomputable def tbt_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

For a finite type V (in Type 0) and a simple graph T on V, tbt_opt T is the natural number defined as the infimum (sInf) of the set of all c : ℕ such that there exists a simple graph H on V satisfying: 1. H is a subcubic tree (is_subcubic_tree H), and 2. the tree routing cost of T into H via the identity map is c (tree_routing_cost T H id = c). In other words, it is the minimum (or 0 if no such tree exists) over all subcubic trees H on V of the tree routing cost of T into H with respect to the identity map on vertices.

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 (TBT) routing cost without Steiner nodes. -/
noncomputable def tbt_opt {V : Type} [Fintype V] (T : SimpleGraph V) : ℕ := open Classical in
  sInf { c : ℕ | ∃ (H : SimpleGraph V), is_subcubic_tree H ∧ tree_routing_cost T H id = c }
See it in the graphDiscuss this resultChallenge it