Menger's theorem via matroids

Question

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is not hard to prove this independence system is actually a matroid. Indeed, matroids arising in this way are called gammoids.

Menger's theorem (in Goering's form, I think) states that the rank function of this matroid is given by

$r(A)=$the minimum number vertices which may be deleted so that no path from $A$ to $Y$ remains.

Is there any matroid interpretation, or matroids-assisted proof of this?

I saw some papers in which both Menger's theorem and matroids appear in the title, but on the first glance they deal with usual cycles/cuts graph matroids.

Answer 1

There is indeed a Menger's theorem for matroids first proven by Tutte. The reference is

Tutte, W. T., Menger’s theorem for matroids, Journal of Research of the National Bureau of Standards—B. Mathematics and Mathematical Physics, 69B (1965), 49–53.

A copy of the paper can be found here.

This theorem is nowadays called Tutte's linking theorem, and it is sad that it is not more widely known. I'll take this chance to try and popularize it. First some notation.

Let $M=(E,r_M)$ be a matroid and let $A$ and $B$ be disjoint subsets of $E$. We define the local connectivity between $A$ and $B$ to be

$\sqcap_M(A,B):=r_M(A)+r_M(B)-r_M(A \cup B)$.

We next define $\lambda_M(A):=\sqcap_M(A,E-A)$, and call $\lambda_M$ the connectivity function of $M$. It is fairly straightforward to check that $\lambda_M$ is symmetric, submodular, invariant under duality, and monotone under taking minors. Finally, we define

$\kappa_M(A,B) = \min(\lambda_M(X) : A \subseteq X \subseteq E-B)$. It is easy to show that for any $C \subseteq E - (A \cup B)$, we have $\sqcap_{M / C} (A,B) \leq \kappa_M(A,B)$. Tutte's linking theorem says that we can always find a $C$ that gives us equality.

Tutte's Linking Theorem. There exists $C \subseteq E - (A \cup B)$, such that $\sqcap_{M / C} (A,B) = \kappa_M(A,B)$.

The proof is not very difficult, so instead I'll just briefly say why this generalizes Menger's theorem for graphs. The form of Menger's theorem that it generalizes is

Menger's Theorem. Let $a$ and $b$ be non-adjacent vertices in a graph $G$. Let $k$ be the size of a smallest vertex cut separating $a$ and $b$. Then there exist $k$ internally vertex disjoint paths between $a$ and $b$.

Proof (via Tutte's Linking Theorem). Let $A$ and $B$ be the sets of edges incident to $a$ and $b$ respectively. Note that $A$ and $B$ are disjoint since $a$ and $b$ are non-adjacent. Let $k$ be the size of the smallest vertex cut separating $a$ and $b$. Now just apply Tutte's Linking Theorem to $A$ and $B$ together with the following two observations:

1. $k = \kappa_{M(G)}(A,B)+1,$ and
2. there exists $n$ internally vertex disjoint paths between $a$ and $b$ if and only if there exists $C \subseteq E(G) - (A \cup B)$ such that $\sqcap_{M(G /C)}(A,B) \geq n-1$.