Timeline for Menger's theorem via matroids
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2016 at 15:43 | comment | added | Fedor Petrov | @TonyHuynh yes, it would be nice to have a proof using gammoid | |
| Jun 12, 2016 at 14:07 | comment | added | Tony Huynh | @FedorPetrov I see. So you want a matroid proof of the directed version of Menger's Theorem? | |
| Jun 11, 2016 at 7:39 | comment | added | Fedor Petrov | @TonyHuynh but how does gammoid help to prove Menger theorem? This was my original question:) | |
| Jun 11, 2016 at 5:59 | comment | added | Tony Huynh | @FedorPetrov Yes, for graphs, oriented Menger is essentially the same as Menger. But oriented Menger for graphs you can get from Menger for matroids (via Gammoids). wikiwand.com/en/Gammoid | |
| Jun 10, 2016 at 21:27 | comment | added | Fedor Petrov | @TonyHuynh Thank you, very interesting! But this is strange: Holmsen' theorem looks deep, with topological proof, while oriented Menger theorem does not essentially differ from the non-oriented, right? | |
| Jun 10, 2016 at 18:03 | comment | added | Tony Huynh | @FedorPetrov To be honest, I do not know too much about oriented matroids. The only theorem I know along these lines is a paper of Andreas Holmsen about the intersection of an oriented matroid with a matroid. sciencedirect.com/science/article/pii/S0001870815005149 | |
| Jun 10, 2016 at 8:54 | comment | added | Fedor Petrov | @TonyHuynh Menger theorem also holds true for oriented graphs. Is there oriented matroids version of Tutte linking theorem (or, to start with, of matroid intersection theorem?) | |
| May 23, 2016 at 18:53 | history | edited | Tony Huynh | CC BY-SA 3.0 |
Added a link to an electronic version of Tutte's paper.
|
| Nov 19, 2010 at 19:39 | comment | added | Tony Huynh | @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 | |
| Nov 19, 2010 at 19:08 | comment | added | Fedor Petrov | @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? | |
| Nov 18, 2010 at 13:03 | history | edited | Tony Huynh | CC BY-SA 2.5 |
removed a comma.
|
| Nov 18, 2010 at 11:57 | comment | added | Tony Huynh | @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. | |
| Nov 17, 2010 at 22:03 | comment | added | Suvrit | @Fedor: perhaps submodularity is hiding somewhere? | |
| Nov 17, 2010 at 20:41 | comment | added | Fedor Petrov | 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? | |
| Nov 17, 2010 at 15:44 | history | answered | Tony Huynh | CC BY-SA 2.5 |