Obstructions to branch-decomposition of matroids (Q2496205)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Obstructions to branch-decomposition of matroids
scientific article

    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
    0 references
    branch width
    0 references
    matroids
    0 references
    connectivity
    0 references
    0 references