On minor-closed classes of matroids with exponential growth rate

Details On minor-closed classes of matroids with exponential growth rate On minor-closed classes of matroids with exponential growth rate

2011-10-31

arxiv.org/abs/1110.6668v1

Mathematics

Combinatorics

Scientific paper

Let $\cM$ be a minor-closed class of matroids that does not contain arbitrarily long lines. The growth rate function, $h:\bN\rightarrow \bN$ of $\cM$ is given by $$h(n) = \max(|M|\, : \, M\in \cM, simple, rank-$n$).$$ The Growth Rate Theorem shows that there is an integer $c$ such that either: $h(n)\le c\, n$, or ${n+1 \choose 2} \le h(n)\le c\, n^2$, or there is a prime-power $q$ such that $\frac{q^n-1}{q-1} \le h(n) \le c\, q^n$; 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^2+1)$-point line, we prove that $h(n) =\frac{q^n-1}{q-1}$ for all sufficiently large $n$. We also prove that, for classes of base-$q$ exponential density that contain no $(q^2+q+1)$-point line, there exists $k\in\bN$ such that $h(n) = \frac{q^{n+k}-1}{q-1} - q\frac{q^{2k}-1}{q^2-1}$ for all sufficiently large $n$.

Affiliated with

Also associated with

No associations

Rating

On minor-closed classes of matroids with exponential growth rate does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On minor-closed classes of matroids with exponential growth rate, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On minor-closed classes of matroids with exponential growth rate will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146907