Obstructions to branch-decomposition of matroids (Q2496205)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 5040282
Language Label Description Also known as
default for all languages
No label defined
    English
    Obstructions to branch-decomposition of matroids
    scientific article; zbMATH DE number 5040282

      Statements

      Obstructions to branch-decomposition of matroids (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      12 July 2006
      0 references
      From the abstract: ``A \((\delta, \gamma)\)-net in a matroid \(M\) is a pair \((N, {\mathcal P})\) where \(N\) is a minor of \(M\), \(\mathcal P\) is a set of series classes in \(N\), \(| \mathcal P| \geq \delta\), and the pairwise connectivity, in \(M\), between any two members of \(\mathcal P\) is at least \(\gamma\). We prove that, for any finite field \(\mathbb F\), nets provide a qualitative characterization for branch-width in the class of \(\mathbb F\)-representable matroids. That is, for an \(\mathbb 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.'' For graphs, such a qualitative characterization was obtained by \textit{N. Robertson} and \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 41, 92--114 (1986; Zbl 0598.05055)].
      0 references
      branch width
      0 references
      matroids
      0 references
      connectivity
      0 references

      Identifiers