Countable Menger's theorem with finitary matroid constraints on the ingoing edges

Attila Joó¹

¹Alfréd Rényi Institute of Mathematics; MTA-ELTE Egerváry Research Group

The electronic journal of combinatorics, Tome 25 (2018) no. 3

Résumé

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 $.

Détail

DOI : 10.37236/6586

Classification : 05C20, 05C38, 05C40, 05B35, 05C63, 05C30
Mots-clés : Menger's theorem, matroid, infinite graph