Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 560-570 |
| Journal | Journal of Combinatorial Theory, Series B |
| Volume | 96 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2006 |
Fingerprint
Dive into the research topics of 'Obstructions to branch-decomposition of matroids'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver