Article ID Journal Published Year Pages File Type
4624915 Advances in Applied Mathematics 2013 13 Pages PDF
Abstract

Let MM be a minor-closed class of matroids that does not contain arbitrarily long lines. The growth rate function, h:N→Nh:N→N of MM is given byh(n)=max{|M|:M∈M is simple, and r(M)⩽n}.h(n)=max{|M|:M∈M is simple, and r(M)⩽n}. The Growth Rate Theorem shows that there is an integer c   such that either: h(n)⩽cnh(n)⩽cn, or (n+12)⩽h(n)⩽cn2, or there is a prime-power q   such that qn−1q−1⩽h(n)⩽cqn; 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 (q2+1)(q2+1)-point line, we prove that h(n)=qn−1q−1 for all sufficiently large n. We also prove that, for classes of base-q   exponential density that contain no (q2+q+1)(q2+q+1)-point line, there exists k∈Nk∈N such that h(n)=qn+k−1q−1−qq2k−1q2−1 for all sufficiently large n.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,