Timeline for Acyclicity equivalent to unique paths
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2010 at 15:44 | vote | accept | lifeofpi | ||
| May 8, 2010 at 6:25 | comment | added | Tony Huynh | You're welcome. Regarding (induced) subgraphs I'm not sure what you are looking for exactly. But with respect to matroids there is indeed a nice duality relation. For matroids we use branch-width instead of tree-width (since graphic matroids don't really have vertices). The corresponding dual notion is tangles instead of brambles. We can think of branch-width as a measure of how tree-like a structure is, and a tangle as a highly connected component of the structure. Again, we have the same duality relation. See math.uwaterloo.ca/~jfgeelen/publications/net.pdf | |
| May 7, 2010 at 23:48 | comment | added | lifeofpi | Thanks! This is a very helpful answer. Is something similar also known for forbidden (induced) subgraphs? I'm pretty naive in graph theory, but I've heard that people also study linear spaces generated by associating each vertex or each edge with independent elements of a vector space. Can one get interesting duality relations from there? I guess such a study will also have intersection with matroid theory. | |
| May 7, 2010 at 20:55 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 49 characters in body
|
| May 7, 2010 at 20:26 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 8 characters in body
|
| May 7, 2010 at 20:20 | history | answered | Tony Huynh | CC BY-SA 2.5 |