Skip to main content
fixed some typos, added link to gammoids, added combinatorial optimization tag.
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Menger Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independentindependent if there exist $|A|$ vertex-disjoint pathes stratingpaths starting in $A$ and ending in $Y$. It is not hard to prove this independence system is actually a matroid. (I saw this example in some Russian bookIndeed, but it should be well knownmatroids 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 MengerMenger's theorem and matroids appear in the title, but on the first glance they deal with usual cycles/cuts grtaphgraph matroids.

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.

Menger's theorem via matroids

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.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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.