Menger theorem via matroids

2010-11-17T14:54:34Z

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.

Answer by Tony Huynh for Menger theorem via matroids

2010-11-17T15:44:35Z

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:

$k = \kappa_{M(G)}(A,B)+1,$ and
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$.

Menger theorem via matroids - MathOverflow

Menger theorem via matroids

Answer by Tony Huynh for Menger theorem via matroids