Theorem 1.6 — (D,S,π) has an M-basic packing of arborescences iff π is M-independent and (D,S,π) is M-connected
ProvedBasicPackArb.Main.theorem_1_6Let be a finite digraph (parallel arcs allowed), a finite set, a placement of the elements of at vertices, and a matroid on with rank function . Write and , and for the number of arcs entering .
An -basic packing of arborescences in is a family of pairwise arc-disjoint arborescences in , rooted at and not necessarily spanning, such that for every vertex the set is a base of .
Theorem 1.6. There exists an -basic packing of arborescences in if and only if
- is -independent: is independent in for every ; and
- is -connected:
With the free matroid on , , and every element placed at one vertex , this is Edmonds' theorem on arc-disjoint spanning arborescences rooted at . Through Frank's orientation theorem it also yields Katoh and Tanigawa's characterization of matroid-based rooted-tree packings in undirected graphs.
Formalization Note The packing is a family T : S → Arborescence D with IsBasicPacking D π M T, indexed by (so equal single-vertex arborescences at a vertex are distinct members). Arborescences are sub-digraphs given by a vertex set, an arc set inside and a root, with root in-degree , in-degree elsewhere, and every vertex reachable from the root (equivalent to being a directed tree). The rank is Matroid.eRk in and (3) is written . The matroid's ground set is the whole root type; no other hypothesis is made.
import Mathlib import Definitions.Def_BasicPackArb_Main_RootedDigraph
namespace BasicPackArb.Main
/-- Theorem 1.6 (p. 3). Let `(D, S, π)` be a digraph with roots and `M` a matroid on `S`. There
exists an `M`-basic packing of arborescences in `(D, S, π)` if and only if `π` is `M`-independent
and `(D, S, π)` is `M`-connected. -/
theorem theorem_1_6 {V Arc S : Type*} [Fintype V] [DecidableEq V] [Fintype S]
(D : Digraph V Arc) (π : S → V) (M : Matroid S) (hM : M.E = Set.univ) :
(∃ T : S → Arborescence D, IsBasicPacking D π M T) ↔
MIndependent π M ∧ MConnected D π M := by sorry
end BasicPackArb.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.