Tangles, tree-decompositions and grids in matroids

被引：18

作者：

Geelen, Jim ^{[1
]}

Gerards, Bert ^{[2
,3
]}

Whittle, Geoff ^{[4
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[2] Ctr Wiskunde & Informat, Amsterdam, Netherlands

[3] Tech Univ Eindhoven, NL-5600 MB Eindhoven, Netherlands

[4] Victoria Univ, Sch Math & Comp Sci, Wellington, New Zealand

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2009年 / 99卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Branch-width; Tangles; Tree-decomposition; Matroids; Graph Minors; PLANAR GRAPH; OBSTRUCTIONS; MINORS;

D O I：

10.1016/j.jctb.2007.10.008

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：657 / 667

页数：11

共 8 条

[1]

[Anonymous], 1996, CONT MATH

[2] Obstructions to branch-decomposition of matroids [J].

Geelen, J ;

Gerards, B ;

Robertson, N ;

Whittle, G .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) :560-570

[3] On the excluded minors for the matroids of branch-width k [J].

Geelen, JF ;

Gerards, AMH ;

Robertson, N ;

Whittle, GP .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (02) :261-265

[4] Excluding a planar graph from GF(q)-representable matroids [J].

Geelen, Jim ;

Gerards, Bert ;

Whittle, Geoff .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (06) :971-998

[5]

Oxley J.G., 1993, Matroid Theory

[6] QUICKLY EXCLUDING A PLANAR GRAPH [J].

ROBERTSON, N ;

SEYMOUR, P ;

THOMAS, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (02) :323-348

[7] GRAPH MINORS .10. OBSTRUCTIONS TO TREE-DECOMPOSITION [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (02) :153-190

[8] MENGERS THEOREM FOR MATROIDS [J].

TUTTE, WT .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :49-+

← 1 →