Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The densest matroids in minor-closed classes with exponential growth rate


Authors: Jim Geelen and Peter Nelson
Journal: Trans. Amer. Math. Soc. 369 (2017), 6751-6776
MSC (2010): Primary 05B35, 05D99
DOI: https://doi.org/10.1090/tran/7186
Published electronically: May 16, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The growth rate function for a nonempty minor-closed class of matroids $ \mathcal {M}$ is the function $ h_{\mathcal {M}}(n)$ whose value at an integer $ n \ge 0$ is defined to be the maximum number of elements in a simple matroid in $ \mathcal {M}$ of rank at most $ n$. Geelen, Kabell, Kung and Whittle showed that, whenever $ h_{\mathcal {M}}(2)$ is finite, the function $ h_{\mathcal {M}}$ grows linearly, quadratically or exponentially in $ n$ (with base equal to a prime power $ q$), up to a constant factor.

We prove that in the exponential case, there are nonnegative integers $ k$ and $ d \le \tfrac {q^{2k}-1} {q-1}$ such that $ h_{\mathcal {M}}(n) = \frac {q^{n+k}-1}{q-1} - qd$ for all sufficiently large $ n$, and we characterise which matroids attain the growth rate function for large $ n$. We also show that if $ \mathcal {M}$ is specified in a certain `natural' way (by intersections of classes of matroids representable over different finite fields and/or by excluding a finite set of minors), then the constants $ k$ and $ d$, as well as the point that `sufficiently large' begins to apply to $ n$, can be determined by a finite computation.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05B35, 05D99

Retrieve articles in all journals with MSC (2010): 05B35, 05D99


Additional Information

Jim Geelen
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

Peter Nelson
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

DOI: https://doi.org/10.1090/tran/7186
Keywords: Matroids, growth rates
Received by editor(s): October 28, 2014
Received by editor(s) in revised form: January 5, 2017
Published electronically: May 16, 2017
Additional Notes: This research was partially supported by a grant from the Office of Naval Research [N00014-10-1-0851].
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society