×

zbMATH — the first resource for mathematics

Obstructions to branch-decomposition of matroids. (English) Zbl 1094.05011
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 N. Robertson and P. D. Seymour [J. Comb. Theory, Ser. B 41, 92–114 (1986; Zbl 0598.05055)].

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bixby, R.E.; Cunningham, W.H., Matroid optimization and algorithms, () · Zbl 0848.05017
[2] Dharmatilake, J.S., A MIN-MAX theorem using matroid separations, (), 333-342 · Zbl 0954.05014
[3] Geelen, J.F.; Gerards, A.M.H.; Robertson, N.; Whittle, G.P., On the excluded-minors for the matroids of branch-width k, J. combin. theory ser. B, 88, 261-265, (2003) · Zbl 1032.05027
[4] T. Johnson, N. Robertson, P.D. Seymour, Connectivity in binary matroids, handwritten manuscript
[5] Kung, J.P.S., Extremal matroid theory, (), 21-62 · Zbl 0791.05018
[6] Oporowski, B., Partitioning matroids with only small cocircuits, Combin. probab. comput., 11, 191-197, (2002) · Zbl 0996.05025
[7] Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press New York · Zbl 0784.05002
[8] Robertson, N.; Seymour, P.D., Graph minors V: excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[9] Robertson, N.; Seymour, P.D., Graph minors X: obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[10] Tutte, W.T., Menger’s theorem for matroids, J. res. nat. bur. standards, B. math. math. phys. B, 69, 49-53, (1965) · Zbl 0151.33802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.