digraph_arborescence_count_at_through
def
through_r(D, a → b): the number of spanning arborescences of D directed towards the root r that use the arc a → b, i.e. whose successor map sends a to b.
Statement
def digraph_arborescence_count_at_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r a b : Fin n) : ℕ- Source
- step towards tournament_not_near_regular_exists_improving_tournament
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 6
- tournament_reverse_arc_through_root_endpoint_eqIn a tournament T with arc u → v, the number of arborescences rooted at v using u → v equals the number of arborescences of reverse(T, u,…
- 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_count_at_through_root_eq_zeroThe number of arborescences directed towards root r that use an arc starting at r is 0 whenever the target differs from r.
- digraph_arborescence_count_throughthrough(D, a → b): the number of spanning arborescences of D, over all choices of root, that use the arc a → b.
- 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
/-- Number of arborescences of D directed towards r whose successor map sends a to b. -/ def digraph_arborescence_count_at_through {n : ℕ} (D : Digraph (Fin n)) [DecidableRel D.Adj] (r a b : Fin n) : ℕ := (Finset.univ.filter (fun p : Fin n → Fin n => p r = r ∧ (∀ w, w ≠ r → D.Adj w (p w)) ∧ (∀ w, p^[n] w = r) ∧ p a = b)).card