2009
Tangles, tree-decompositions, and grids in matroids
Publication
Publication
Journal of Combinatorial Theory - Series B , Volume 99 p. 657- 667
A tangle in a matroid is an obstruction to small branch-width. In particular, the maximum order of a tangle is equal to the branch-width. We prove that: (i) there is a tree-decomposition of a matroid that “displays” all of the maximal tangles, and (ii) when M is representable over a finite field, each tangle of sufficiently large order “dominates” a large grid-minor. This extends results of Robertson and Seymour concerning Graph Minors.
Additional Metadata | |
---|---|
Academic Press | |
Journal of Combinatorial Theory - Series B | |
Matroid Structure for Efficiency | |
Organisation | Probability, Networks and Algorithms |
Geelen, J., Gerards, B., & Whittle, G. (2009). Tangles, tree-decompositions, and grids in matroids. Journal of Combinatorial Theory - Series B, 99, 657–667. |