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?)

  • [1] Tom Brylawski, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1-44. MR 0357163, https://doi.org/10.2307/1997065
  • [2] P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85-90. MR 0111692, https://doi.org/10.1112/jlms/s1-35.1.85
  • [3] Jim Geelen and Kasper Kabell, Projective geometries in dense matroids, J. Combin. Theory Ser. B 99 (2009), no. 1, 1-8. MR 2467813, https://doi.org/10.1016/j.jctb.2008.03.003
  • [4] Jim Geelen, Joseph P. S. Kung, and Geoff Whittle, Growth rates of minor-closed classes of matroids, J. Combin. Theory Ser. B 99 (2009), no. 2, 420-427. MR 2482959, https://doi.org/10.1016/j.jctb.2008.08.006
  • [5] Jim Geelen and Peter Nelson, On minor-closed classes of matroids with exponential growth rate, Adv. in Appl. Math. 50 (2013), no. 1, 142-154. MR 2996389, https://doi.org/10.1016/j.aam.2012.03.004
  • [6] Jim Geelen and Peter Nelson, A density Hales-Jewett theorem for matroids, J. Combin. Theory Ser. B 112 (2015), 70-77. MR 3323034, https://doi.org/10.1016/j.jctb.2014.11.008
  • [7] Joseph P. S. Kung, Numerically regular hereditary classes of combinatorial geometries, Geom. Dedicata 21 (1986), no. 1, 85-105. MR 850567, https://doi.org/10.1007/BF00147534
  • [8] D. H. J. Polymath, A new proof of the density Hales-Jewett theorem, Ann. of Math. (2) 175 (2012), no. 3, 1283-1327. MR 2912706, https://doi.org/10.4007/annals.2012.175.3.6
  • [9] Peter Nelson, Growth rate functions of dense classes of representable matroids, J. Combin. Theory Ser. B 103 (2013), no. 1, 75-92. MR 2995720, https://doi.org/10.1016/j.jctb.2012.09.002
  • [10] Andrew Thomason, The extremal function for complete minors, J. Combin. Theory Ser. B 81 (2001), no. 2, 318-338. MR 1814910, https://doi.org/10.1006/jctb.2000.2013
  • [11] James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819

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