Bridging separations in matroids

被引:5
作者
Geelen, J [1 ]
Hlineny, P
Whittle, G
机构
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[2] Univ Victoria, Sch Math & Comp Sci, Wellington, New Zealand
关键词
matroids; connectivity; blocking sequences;
D O I
10.1137/S089548010139638X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let (X-1, X-2) be an exact k-separation of a matroid N. If M is a matroid that contains N as a minor and the k-separation (X-1, X-2) does not extend to a k-separation in M, then we say that M bridges the k- separation (X-1, X-2) in N. One would hope that a minor minimal bridge for (X-1, X-2) would not be much larger than N. Unfortunately there are instances in which one can construct arbitrarily large minor-minimal bridges. We restrict our attention to the class of matroids representable over a fixed finite field and show that here minor-minimal bridges are bounded in size.
引用
收藏
页码:638 / 646
页数:9
相关论文
共 5 条
[1]   The excluded minors for GF(4)-representable matroids [J].
Geelen, JF ;
Gerards, AMH ;
Kapoor, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 79 (02) :247-299
[2]   Branch-width and well-quasi-ordering in matroids and graphs [J].
Geelen, JF ;
Gerards, AMH ;
Whittle, G .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) :270-290
[3]   On packing minors into connected matroids [J].
Lemos, M ;
Oxley, J .
DISCRETE MATHEMATICS, 1998, 189 (1-3) :283-289
[4]   DECOMPOSITION OF REGULAR MATROIDS [J].
SEYMOUR, PD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (03) :305-359
[5]   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-+