tbt_sn_opt
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
- 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
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 }