Obstructions to branch-decomposition of matroids

被引:20
作者
Geelen, J [1 ]
Gerards, B
Robertson, N
Whittle, G
机构
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[2] CWI, NL-1090 GB Amsterdam, Netherlands
[3] Eindhoven Univ Technol, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands
[4] Ohio State Univ, Dept Math, Columbus, OH 43210 USA
[5] Victoria Univ Wellington, Sch Math & Comp Sci, Wellington, New Zealand
基金
加拿大自然科学与工程研究理事会;
关键词
branch-width; matroids; connectivity;
D O I
10.1016/j.jctb.2005.11.001
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A (delta,gamma)-net in a matroid M is a pair (N, P) where N is a minor of M, P is a set of series classes in N, vertical bar P vertical bar >=delta, and the pairwise connectivity, in M, between any two members of P is at least gamma. We prove that, for any finite field F, nets provide a qualitative characterization for branch-width in the class of F-representable matroids. That is, for an F-representable matroid M, we prove that: (1) if M contains a (delta, gamma)-net where delta and gamma are both very large, then M has large branch-width, and, conversely, (2) if the branch-width of M is very large, then M or M* contains a (delta, gamma)-net where delta and gamma are both large. (C) 2005 Elsevier Inc. All rights reserved.
引用
收藏
页码:560 / 570
页数:11
相关论文
共 10 条
[1]  
[Anonymous], 1996, CONT MATH
[2]  
Bixby R. E., 1995, Handbook of Combinatorics
[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]  
JOHNSON T, UNPUB CONNECTIVITY B
[5]  
Kung J., 1993, GRAPH STRUCTURE THEO, P21
[6]   Partitioning matroids with only small cocircuits [J].
Oporowski, B .
COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (02) :191-197
[7]  
Oxley J., 1993, MATROID THEORY
[8]   GRAPH MINORS .5. EXCLUDING A PLANAR GRAPH [J].
ROBERTSON, N ;
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :92-114
[9]   GRAPH MINORS .10. OBSTRUCTIONS TO TREE-DECOMPOSITION [J].
ROBERTSON, N ;
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1991, 52 (02) :153-190
[10]   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-+