13
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ is such a connection not there in Schrijver's volume 2? $\endgroup$
    – Suvrit
    Nov 17, 2010 at 15:07
  • $\begingroup$ as i suspected, page 720 of Schrijver's book cites Tutte's proof of Menger's theorem for matroids (see books.google.com/…) $\endgroup$
    – Suvrit
    Nov 17, 2010 at 21:59
  • $\begingroup$ Thanks, Suvrit! The book does not open, but maybe it is the same theorem which Tony cites below? $\endgroup$ Nov 18, 2010 at 21:33
  • $\begingroup$ 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! $\endgroup$
    – Suvrit
    Nov 19, 2010 at 17:22
  • $\begingroup$ @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( $\endgroup$ Nov 20, 2010 at 6:41

1 Answer 1

20
$\begingroup$

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$.
$\endgroup$
12
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 17, 2010 at 20:41
  • $\begingroup$ @Fedor: perhaps submodularity is hiding somewhere? $\endgroup$
    – Suvrit
    Nov 17, 2010 at 22:03
  • $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Nov 18, 2010 at 11:57
  • $\begingroup$ @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? $\endgroup$ Nov 19, 2010 at 19:08
  • 1
    $\begingroup$ @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 $\endgroup$
    – Tony Huynh
    Nov 19, 2010 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.