Menger theorem via matroids - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:07:18Z http://mathoverflow.net/feeds/question/46361 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46361/menger-theorem-via-matroids Menger theorem via matroids Fedor Petrov 2010-11-17T14:54:34Z 2010-11-18T13:03:08Z <p>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.)</p> <p>Menger's theorem (in Goering's form, I think) states that rank function of this matroid is given by </p> <p>$r(A)=$the minimum number vertices which may be deleted so that no path from $A$ to $Y$ remains.</p> <p>Is there any matroid interpretation, or matroids-assisted proof of this?</p> <p>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.</p> http://mathoverflow.net/questions/46361/menger-theorem-via-matroids/46371#46371 Answer by Tony Huynh for Menger theorem via matroids Tony Huynh 2010-11-17T15:44:35Z 2010-11-18T13:03:08Z <p>There is indeed a Menger's theorem for matroids first proven by Tutte. The reference is</p> <blockquote> <p>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.</p> </blockquote> <p>This theorem is nowadays called <em>Tutte's linking theorem,</em> and it is sad that it is not more widely known. I'll take this chance to try and popularize it. First some notation. </p> <p>Let $M=(E,r_M)$ be a matroid and let $A$ and $B$ be disjoint subsets of $E$. We define the <em>local connectivity</em> between $A$ and $B$ to be </p> <p>$\sqcap_M(A,B):=r_M(A)+r_M(B)-r_M(A \cup B)$.</p> <p>We next define $\lambda_M(A):=\sqcap_M(A,E-A)$, and call $\lambda_M$ the <em>connectivity function</em> 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 </p> <p>$\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.</p> <p><strong>Tutte's Linking Theorem.</strong> There exists $C \subseteq E - (A \cup B)$, such that $\sqcap_{M / C} (A,B) = \kappa_M(A,B)$.</p> <p>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</p> <p><strong>Menger's Theorem.</strong> 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$.</p> <p><em>Proof (via Tutte's Linking Theorem)</em>. 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:</p> <ol> <li>$k = \kappa_{M(G)}(A,B)+1,$ and</li> <li>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$. </li> </ol>