tbt_opt
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
- tbt_opt_eq_sn_opt_of_is_subcubicFor every finite type V with at least two elements and every subcubic tree T on V, tbt_opt T equals tbt_sn_opt T.
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 }