digraph_arborescence_count
def
tau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.
Statement
def digraph_arborescence_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : ℕ- Defined in
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; tau(D) of Sec. 1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- digraph_arborescence_count_ata_r(D): the number of spanning arborescences of D directed towards the root r. Each is recorded by its successor map p: p r = r, every…
- Used by 5
- digraph_arborescence_count_reverse_arc_add_throughReversing a single arc u → v of a tournament satisfies tau(T) + through(T', v → u) = tau(T') + through(T, u → v), so the gain in the…
- tournament_reverse_arc_through_lt_iff_arborescence_ltIn a tournament T with an arc u → v, the total through-count strictly increases upon reversing u → v if and only if the total number of…
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
- digraph_arborescence_count_through_sanitythrough(D, a → b) vanishes when a → b is not an arc of D, never exceeds tau(D), and on the two-vertex complete digraph the arc 0 → 1 lies…
- tournament_four_arborescence_maximizer_is_near_regularEvery tournament on 4 vertices maximizing the total number of spanning arborescences among all tournaments on 4 vertices is near-regular.
Lean source view module on GitHub
/-- tau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r. -/ def digraph_arborescence_count {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] : ℕ := ∑ r, digraph_arborescence_count_at D r