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

MaRDI QIDQ1658749zbMATH OpenFDO

Authors Attila Joó

Publication date 15 August 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.00287, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p12

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

infinite graphmatroidMenger's theorem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38) Connectivity (05C40) Infinite graphs (05C63)

Abstract: We present a strengthening of the countable Menger theorem (edge version) of R. Aharoni. Let $D=(V,A)$ be a countable digraph with $seqtinV$ and let $$ 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 $sightarrowt$ paths $mathcalP$ such that the united edge set of the paths is $mathcalM$-independent, and there is a $CsubseteqA$ consists of one edge from each element of $mathcalP$ for which $mathsf{span}_{mathcalM}(C)$ covers all the $sightarrowt$ paths in $D$.

Review text

Summary: We present a strengthening of the countable Menger's theorem of \textit{R. Aharoni} [J. Comb. Theory, Ser. B 43, 303--313 (1987; Zbl 0631.05032)]. 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\).

Recommendations

• Menger's theorem for infinite graphs
• Menger's theorem for countable graphs
• Menger's theorem for matroids
• Menger's Theorem for a Countable Source Set
• On the intersection of infinite matroids

Cites work

• Computing Maximal “Polymatroidal” Network Flows
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Menger's theorem for countable graphs
• Menger's theorem for infinite graphs

Cited in

(2)

• Menger's theorem for countable graphs
• Vertex-flames in countable rooted digraphs preserving an Erdős-Menger separation for each vertex

This page was built for publication: Countable Menger's theorem with finitary matroid constraints on the ingoing edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1658749)