Stability, fragility, and Rota's conjecture

DOI10.1016/J.JCTB.2011.09.004zbMATH Open1241.05010arXiv1006.1418OpenAlexW2122667898MaRDI QIDQ414652FDOQ414652

Authors: Dillon Mayhew, Stefan H. M. van Zwam, Geoff Whittle 

Publication date: 11 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Fix a matroid N. A matroid M is N-fragile if, for each element e of M, at least one of Me and M/e has no N-minor. The Bounded Canopy Conjecture is that all GF(q)-representable matroids M that have an N-minor and are N-fragile have branch width bounded by a constant depending only on q and N. A matroid N stabilizes a class of matroids over a field F if, for every matroid M in the class with an N-minor, every F-representation of N extends to at most one F-representation of M. We prove that, if Rota's conjecture is false for GF(q), then either the Bounded Canopy Conjecture is false for GF(q) or there is an infinite chain of GF(q)-representable matroids, each not stabilized by the previous, each of which can be extended to an excluded minor. Our result implies the previously known result that Rota's conjecture holds for GF(4), and that the classes of near-regular and sixth-roots-of-unity have a finite number of excluded minors. However, the bound that we obtain on the size of such excluded minors is considerably larger than that obtained in previous proofs. For GF(5) we show that Rota's Conjecture reduces to the Bounded Canopy Conjecture.

Full work available at URL: https://arxiv.org/abs/1006.1418

Recommendations

• Matroid fragility and relaxations of circuit hyperplanes
• On matroids of branch-width three.
• A geometric approach to forbidden minors for GF(3)
• Towards a matroid-minor structure theory
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids

zbMATH Keywords

fragilityrepresentationsmatroidsexcluded minorsstabilizersblocking sequencesbranch widthRota's conjecture

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25)

Cites Work

• Decomposition of regular matroids
• Title not available (Why is that?)
• Towards a matroid-minor structure theory
• Lectures on matroids
• Almost-graphic matroids
• Branch-width and Rota's conjecture
• Title not available (Why is that?)
• The structure of crossing separations in matroids
• A Combinatorial Decomposition Theory
• The excluded minors for GF(4)-representable matroids
• Stabilizers of classes of representable matroids
• On the Uniqueness of Matroid Representations Over GF(4)
• On inequivalent representations of matroids over finite fields
• On Rota's conjecture and excluded minors containing large projective geometries.
• Bridging Separations in Matroids
• The structure of the 3-separations of 3-connected matroids
• A decomposition theory for matroids. III. Decomposition conditions
• A characterization of a class of non-binary matroids
• Matroid representation over GF(3)
• A decomposition theory for matroids. VI: Almost regular matroids
• On Reid's characterization of the ternary matroids
• Weak maps and stabilizers of classes of matroids
• Matroid 4-connectivity: A deletion-contraction theorem
• A characterisation of the matroids representable over GF(3) and the rationals
• Inequivalent representations of ternary matroids
• Partial fields and matroid representation
• The excluded minors for near-regular matroids
• Title not available (Why is that?)
• On Matroids Representable over 𝐺𝐹(3) and Other Fields
• Confinement of matroid representations to subsets of partial fields
• A decomposition theory for matroids. I: General results
• Lifts of matroid representations over partial fields

Cited In (12)

• On two classes of nearly binary matroids
• The excluded minors for 2- and 3-regular matroids
• Fork-decompositions of matroids
• On almost-planar graphs
• Excluded minors are almost fragile. II: Essential elements
• Relaxations of \(\mathrm{GF}(4)\)-representable matroids
• Delta-wye reduction of almost-planar graphs
• Fan-extensions in fragile matroids
• On matroids of branch-width three.
• Excluded minors are almost fragile
• The structure of \(\{U_{2,5}, U_{3,5}\}\)-fragile matroids
• An algorithm for delta-wye reduction of almost-planar graphs

This page was built for publication: Stability, fragility, and Rota's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414652)