×

zbMATH — the first resource for mathematics

Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids. (English) Zbl 1125.05025
Rota’s conjecture states that for any finite field \(F\) there are only finitely many excluded minors for the class of \(F\)-representable matroids. In an effort to further progress on Rota’s conjecture, the authors prove the following conjecture of Johnson, Robertson and Seymour [handwritten notes]: For any positive integer \(\theta\) and finite field \(F\), there exists an integer \(\omega\) such that if \(M\) is an \(F\)-representable matroid with branch-width at least \(\omega\), then \(M\) contains a minor isomorphic to the cycle-matroid of the \(\theta\) by \(\theta\) grid.
Furthermore, the authors prove a stronger theorem that does not require representability.
Author’s abstract: “We prove that a binary matroid with huge branch-width contains the cycle matroid of a large grid as a minor. This implies that an infinite antichain of binary matroids cannot contain the cycle matroid of a planar graph. The result also holds for any other finite field.”

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Erdős, P.; Pósa, L., On the maximal number of disjoint circuits of a graph, Publ. math. debrecen, 9, 3-12, (1962) · Zbl 0133.16701
[2] Geelen, J.F.; Whittle, G.P., Branch-width and Rota’s conjecture, J. combin. theory ser. B, 86, 315-330, (2002) · Zbl 1027.05018
[3] Geelen, J.F.; Whittle, G.P., Cliques in dense \(\mathit{GF}(q)\)-representable matroids, J. combin. theory ser. B, 87, 264-269, (2003) · Zbl 1026.05023
[4] Geelen, J.F.; Gerards, A.M.H.; Whittle, G.P., Branch-width and well-quasi-ordering in matroids and graphs, J. combin. theory ser. B, 84, 270-290, (2002) · Zbl 1037.05013
[5] 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
[6] Geelen, J.F.; Gerards, A.M.H.; Whittle, G.P., Disjoint cocircuits in matroids with large rank, J. combin. theory ser. B, 87, 270-279, (2003) · Zbl 1032.05028
[7] Geelen, J.F.; Gerards, A.M.H.; Robertson, N.; Whittle, G.P., Obstructions to branch-decomposition of matroids, J. combin. theory ser. B, 96, 560-570, (2006) · Zbl 1094.05011
[8] Hliněný, P., Branch-width, parse trees, and monadic second-order logic for matroids, J. combin. theory ser. B, 96, 325-351, (2006) · Zbl 1088.05022
[9] T. Johnson, N. Robertson, P.D. Seymour, Connectivity in binary matroids, handwritten manuscript
[10] Mader, W., Homomorphieeigenschaften und mittlere kantendichte von graphen, Math. ann., 174, 265-268, (1967) · Zbl 0171.22405
[11] Oxley, J.G., Matroid theory, (1992), Oxford Univ. Press New York · Zbl 0784.05002
[12] Robertson, N.; Seymour, P.D., Graph minors V: excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[13] Seymour, P.D., Recognizing graphic matroids, Combinatorica, 1, 75-78, (1981) · Zbl 0501.05022
[14] Tutte, W.T., Menger’s theorem for matroids, J. res. natl. bureau of standards—B. math. math. phys., 69B, 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.