×

zbMATH — the first resource for mathematics

Tangles, tree-decompositions and grids in matroids. (English) Zbl 1229.05070
Summary: 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.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C83 Graph minors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dharmatilake, J.S., A MIN-MAX theorem using matroid separations, (), 333-342 · Zbl 0954.05014
[2] Geelen, J.F.; Gerards, A.M.H.; Robertson, N.; Whittle, G.P., On the excluded-minors for the matroids of branch-width k, J. combin. theory ser. B, 88, 261-265, (2003) · Zbl 1032.05027
[3] Geelen, J.; Gerards, B.; Robertson, N.; Whittle, G., Obstructions to branch-decomposition of matroids, J. combin. theory ser. B, 96, 560-570, (2006) · Zbl 1094.05011
[4] Geelen, J.; Gerards, B.; Whittle, G., Excluding a planar graph from \(\operatorname{GF}(q)\)-representable matroids, J. combin. theory ser. B, 97, 971-998, (2007) · Zbl 1125.05025
[5] Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press New York · Zbl 0784.05002
[6] Robertson, N.; Seymour, P.D., Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[7] Robertson, N.; Seymour, P.D., Graph minors. XVI. excluding a non-planar graph, J. combin. theory ser. B, 89, 43-76, (2003) · Zbl 1023.05040
[8] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[9] Tutte, W.T., Menger’s theorem for matroids, J. res. nat. bur. standards, B. math. math. phys., 69B, 49-53, (1965) · Zbl 0151.33802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.