On minor-closed classes of matroids with exponential growth rate

2011/10/31 by Geelen, Jim, Nelson, Peter
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1110.6668

Abstract

Let \cM be a minor-closed class of matroids that does not contain arbitrarily long lines. The growth rate function, h:\bN→ \bN of \cM is given by h(n) = max(|M| : M∈ \cM, simple, rank-n). The Growth Rate Theorem shows that there is an integer c such that either: h(n)≤ c n, or n+1 \choose 2 ≤ h(n)≤ c n², or there is a prime-power q such that (qⁿ-1)/(q-1) ≤ h(n) ≤ c qⁿ; this separates classes into those of linear density, quadratic density, and base-q exponential density. For classes of base-q exponential density that contain no (q²+1)-point line, we prove that h(n) =(qⁿ-1)/(q-1) for all sufficiently large n. We also prove that, for classes of base-q exponential density that contain no (q²+q+1)-point line, there exists k∈\bN such that h(n) = \fracq^n+k-1q-1 - q\fracq^2k-1q²-1 for all sufficiently large n.

Related

• The densest matroids in minor-closed classes with exponential growth\n rate
• Matroids denser than a projective geometry
• Matroids denser than a clique
• Growth rate functions of dense classes of representable matroids
• Growth rate of binary matroids with no P₉^*-minor