کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657062 1343712 2012 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Stability, fragility, and Rotaʼs Conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Stability, fragility, and Rotaʼs Conjecture
چکیده انگلیسی

Fix a matroid N. A matroid M is N-fragile if, for each element e of M, at least one of M∖e 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 matroids 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 102, Issue 3, May 2012, Pages 760-783