TY - JOUR

T1 - Obstructions to branch-decomposition of matroids

AU - Geelen, J.F.

AU - Gerards, B.

AU - Robertson, N.

AU - Whittle, G.

PY - 2006

Y1 - 2006

N2 - A (d,¿)-net in a matroid M is a pair where N is a minor of M, is a set of series classes in N, , and the pairwise connectivity, in M, between any two members of is at least ¿. We prove that, for any finite field , nets provide a qualitative characterization for branch-width in the class of -representable matroids. That is, for an -representable matroid M, we prove that: (1) if M contains a (d,¿)-net where d and ¿ 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 (d,¿)-net where d and ¿ are both large.

AB - A (d,¿)-net in a matroid M is a pair where N is a minor of M, is a set of series classes in N, , and the pairwise connectivity, in M, between any two members of is at least ¿. We prove that, for any finite field , nets provide a qualitative characterization for branch-width in the class of -representable matroids. That is, for an -representable matroid M, we prove that: (1) if M contains a (d,¿)-net where d and ¿ 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 (d,¿)-net where d and ¿ are both large.

U2 - 10.1016/j.jctb.2005.11.001

DO - 10.1016/j.jctb.2005.11.001

M3 - Article

VL - 96

SP - 560

EP - 570

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

IS - 4

ER -