2014/10/28 by Jim Geelen, Peter Nelson, Geelen, Jim +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1410.7676
openalex publication_date 2014/10/28 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
The \growth rate function for a nonempty minor-closed class of\nmatroids \M is the function h\M(n) whose value at an\ninteger n \≥ 0 is defined to be the maximum number of elements in a simple\nmatroid in \M of rank at most n. Geelen, Kabell, Kung and Whittle\nshowed that, whenever h\M(2) is finite, the function\nh\M grows linearly, quadratically or exponentially in n (with\nbase equal to a prime power q), up to a constant factor.\n We prove that in the exponential case, there are nonnegative integers k and\nd \≤ tfracq2k-1q-1 such that h\M(n) =\n fracqn+k-1q-1 - qd for all sufficiently large n, and we characterise\nwhich matroids attain the growth rate function for large n. We also show that\nif \M is specified in a certain `natural' way (by intersections of\nclasses of matroids representable over different finite fields and/or by\nexcluding a finite set of minors), then the constants k and d, as well as\nthe point that `sufficiently large' begins to apply to n, can be determined\nby a finite computation.\n