Countable Menger's Theorem with Finitary Matroid Constraints on the Ingoing Edges

  • Attila Joó
Keywords: Menger's theorem, Matroid, Infinite graph


We present a strengthening of the countable Menger's theorem of R. Aharoni. Let $ D=(V,A) $ be a countable digraph with $ s\neq t\in V $ and let $\mathcal{M}=\bigoplus_{v\in V}\mathcal{M}_v $ be a matroid on $ A $ where $ \mathcal{M}_v $ is a finitary matroid on the ingoing edges of $ v $. We show that there is a system of edge-disjoint $ s \rightarrow t $ paths $ \mathcal{P} $ such that the united edge set of these paths is $ \mathcal{M} $-independent, and there is a $ C \subseteq A $ consisting of one edge from each element of $\mathcal{P} $ for which $ \mathsf{span}_{\mathcal{M}}(C) $ covers all the $ s\rightarrow t $ paths in $ D $.

Article Number