# Menger theorem via matroids

Let $G=(V,E)$ be oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint pathes strating in $A$ and ending in $Y$. It is not hard to prove this independence system is actually matroid. (I saw this example in some Russian book, but it should be well known.)

Menger's theorem (in Goering's form, I think) states that 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 theorem and matroids appear in the title, but on the first glance they deal with usual cycles/cuts grtaph matroids.

-
is such a connection not there in Schrijver's volume 2? – Suvrit Nov 17 '10 at 15:07
as i suspected, page 720 of Schrijver's book cites Tutte's proof of Menger's theorem for matroids (see books.google.com/…) – Suvrit Nov 17 '10 at 21:59
Thanks, Suvrit! The book does not open, but maybe it is the same theorem which Tony cites below? – Fedor Petrov Nov 18 '10 at 21:33
Yeah, somehow the link does not open; but if you search for "menger theorem matroids" on books.google.com, it shows you Schrijver's book, for which it shows page 720 (though sometimes it refuses to show the content); but yes, Tony is citing the same result! – Suvrit Nov 19 '10 at 17:22
@Suvrit: it looks like googlebooks changed the rules, and now we not from the States have no right to see many books, including this one( – Fedor Petrov Nov 20 '10 at 6:41

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.

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$.
-
Thank you for this very nice answer! I did not know this theorem. Let me express it as min-mux formula $$\min_{A\subset X\subset B} r(X)+r(E\setminus X)-r(E)=\max_{C\subset E\setminus (A\cup B)} r(A\cup C)+r(B\cup C)-r(C)-r(A\cup B\cup C)$$ and ask, wether is it the most general min-max principle for matroids, or it is a particular case of something even more general? – Fedor Petrov Nov 17 '10 at 20:41
@Fedor: perhaps submodularity is hiding somewhere? – Suvrit Nov 17 '10 at 22:03
@Fedor: It is possible to view (an equivalent form of) Tutte's Linking Theorem as a special case of the Matroid Intersection Theorem, which is a min-max formula. I believe this is the approach that the encyclopedia (Schrijver) takes. See my answer to this question for a statement and application of matroid intersection. – Tony Huynh Nov 18 '10 at 11:57
@Tony: I do not see how to does it follow from the matroid intersection, or matroid union, or Rado transversal theorem or anything in such flavour. Would you please give a hint? – Fedor Petrov Nov 19 '10 at 19:08
@Fedor: If C is a maximum size common independent set of M / A \B and M \A /B, then C in fact gives equality in the min-max formula that you wrote – Tony Huynh Nov 19 '10 at 19:39