digraph_arborescence_count_at
def
a_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 vertex v other than r has the arc v -> p v, and iterating p from any vertex reaches r (so the arcs form a spanning tree oriented towards r).
Statement
def digraph_arborescence_count_at {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj]
(r : Fin n) : ℕ- Defined in
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; the rooted counts a_r(D) of Sec. 1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 6
- digraph_eulerian_orientation_arborescence_count_posAn Eulerian orientation D of a finite connected simple graph is strongly connected, so for every root r it has at least one spanning…
- 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…
- 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…
- digraph_arborescence_counttau(D): the total number of arborescences of D, the sum of a_r(D) over all roots r.
- digraph_arborescence_count_at_sanitySanity check: on two vertices, the digraph with no arcs has no arborescence towards 0, and the complete digraph (with loops) has exactly…
- digraph_arborescence_count_at_reverse_arc_add_throughFor a tournament with an arc u → v and any root r, the number of arborescences towards r grows by exactly (through-count of v → u after…
Lean source view module on GitHub
/-- a_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 vertex v other than r has the arc v -> p v, and iterating p from any vertex reaches r (so the arcs form a spanning tree oriented towards r). -/ def digraph_arborescence_count_at {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r : Fin n) : ℕ := (Finset.univ.filter (fun p : Fin n → Fin n => p r = r ∧ (∀ v, v ≠ r → D.Adj v (p v)) ∧ ∀ v, p^[n] v = r)).card