Tangles, tree-decompositions and grids in matroids

J.F. Geelen; B. Gerards; G. Whittle

doi:10.1016/j.jctb.2007.10.008

Tangles, tree-decompositions and grids in matroids

J.F. Geelen, B. Gerards, G. Whittle

Research output: Contribution to journal › Article › Academic › peer-review

13 Citations (Scopus)

1 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	657-667
Journal	Journal of Combinatorial Theory, Series B
Volume	99
Issue number	4
DOIs	https://doi.org/10.1016/j.jctb.2007.10.008
Publication status	Published - 2009

Access to Document

10.1016/j.jctb.2007.10.008

Fingerprint Dive into the research topics of 'Tangles, tree-decompositions and grids in matroids'. Together they form a unique fingerprint.

Cite this

@article{5c301566ba104b0487fda1ec6844215b,

title = "Tangles, tree-decompositions and grids in matroids",

abstract = "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.",

author = "J.F. Geelen and B. Gerards and G. Whittle",

year = "2009",

doi = "10.1016/j.jctb.2007.10.008",

language = "English",

volume = "99",

pages = "657--667",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - Tangles, tree-decompositions and grids in matroids

AU - Geelen, J.F.

AU - Gerards, B.

AU - Whittle, G.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1016/j.jctb.2007.10.008

DO - 10.1016/j.jctb.2007.10.008

M3 - Article

VL - 99

SP - 657

EP - 667

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

IS - 4

ER -