oriented_diameter_bound_holds
def
oriented_diameter_bound_holds d k: every finite connected bridgeless simple graph of diameter d (taken on vertex set Fin n, which loses nothing) has a strong orientation of directed diameter at most k. In the paper's notation this says f(d) <= k, where f(d) is the smallest such k.
Statement
def oriented_diameter_bound_holds (d k : ℕ) : Prop
- Defined in
- arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: the function f(d), the smallest integer such that every finite connected bridgeless simple graph of diameter d admits a strong orientation of diameter at most f(d); f(d) <= k iff this predicate holds.
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 1
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
- Used by 2
- oriented_diameter_bound_holds_monoIf every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d)…
- oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…
Lean source view module on GitHub
def oriented_diameter_bound_holds (d k : ℕ) : Prop := ∀ (n : ℕ) (G : SimpleGraph (Fin n)), G.Connected → (∀ e, ¬ G.IsBridge e) → G.diam = d → has_strong_orientation_of_diameter_le G k