Growth Rates II

$\newcommand{\cM}{\mathcal{M}}$

This entry continues on from my last, which concerns the growth rates of matroids in minor-closed classes. A one-line recap of my notation is that, if $\cM$ is a minor-closed class of matroids, then $h_{\cM}(n)$ denotes the ($\mathbb{Z} \cup \{\infty\}$)-valued function whose value at each integer $n$ is the maximum number of elements in a simple matroid in the class of rank at most $n$. Last time I finished with the growth rate theorem of Geelen, Kabell, Kung and Whittle – here it is again.

Growth Rate Theorem
Let $\cM$ be a minor-closed class of matroids. Either

  1.  $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
  2. $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$, and $\cM$ contains all graphic matroids,
  3. $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n \ge 2$ and some prime power $q$, and $\cM$ contains all GF$(q)$-representable matroids, or
  4. $h_{\cM}(n) = \infty$ for all $n \ge 2$, and $\cM$ contains all simple rank-$2$ matroids.

This is surprising – up to a constant factor, the growth rate function for an arbitrary minor-closed class has just four possible types and, if the class has superlinear growth rate function then the function is `explained’ by the class containing a natural class with which its growth rate function agrees asymptotically. In this entry and the next, we’ll discuss some questions related to this theorem, starting with the scariest.

Structure

Thinking as we did with Mader’s theorem (Theorem 1 in my last entry), the burning question is why growth rate functions are restricted in this way. In the case of graphs, growth rate functions are controlled because of the structure guaranteed by the graph minors structure theorem. For this purpose, we can only really hope to describe classes satisfying outcomes 1-3 of the theorem, so we exclude some rank-$2$ uniform matroid to gain traction, and pose the following question:

Problem 1: Given an integer $n$, find a structural description for minor-closed classes of matroids not containing $U_{2,n}$.

An solution to this problem would yield a theorem that implies the growth rate theorem (and much more) very easily.

This problem is probably extremely difficult in general, but the case where the matroids are representable over a fixed finite field GF($q$) has been solved. As a major part of their work on the recently vanquished Rota’s Conjecture, Geelen, Gerards and Whittle have proved (but unfortunately not quite written yet – see [GGW07]) a structure theorem for the matroids in arbitrary minor-closed class of GF$(q)$-representable matroids. The representable case of the growth rate theorem falls out of their theorem without much effort.

However, the non-representable case has genuine difficulties not arising from representable matroids that make a structure theorem much harder to dream up. Spikes, for example, cause a special type of trouble that doesn’t crop up over finite fields (see [G08] for a discussion). Problem 1 in its full generality is still very much open.

Zooming In

Something that seems more approachable is to ask more exact questions about how growth rate functions behave. It is one thing to know that $h_{\cM}(n)$ is bounded above and below by, say, a quadratic in $n$, but it is another thing to know the asymptotic or exact behaviour of the function itself. In some cases, this is trivial; there are no prizes for working out the answer if $\cM$ is the class of graphic matroids, for example. In some cases, it seems very hard – even the class of graphic matroids with no $M(K_t)$-minor for general $t$ has a growth rate function that is only partially understood (it is a linear function whose gradient is known asymptotically in $t$, but not known for any fixed $t > 9$ (edit: corrected – thanks Jim), see Thomason [T01]).

However, for many specific classes, the problem is interesting and some results are known. Kung, Mayhew, Pivotto and Royle [KMPR13] recently showed that the growth rate function for the binary matroids with no AG$(3,2)$-minor is the same as that of the graphic matroids for all $n \ge 5$. Geelen and I [GN10] showed that, for sufficiently large $n$, the growth rate function for the class of matroids with no $U_{2,\ell+2}$-minor is equal to that of the GF$(q)$-representable matroids, where $q$ is the largest prime power not exceeding $\ell$. We also have shown, (and will write someday) that every minor-closed class $\cM$ whose growth rate function is exponential in $n$ satisfies $h_{\cM}(n) = \frac{q^{n+k}-1}{q-1} – qd$ for all sufficiently large $n$, where $k$ and $d$ are nonnegative integers with $d \le \frac{q^{2k}-1}{q^2-1}$.

Many questions of this sort are still open. Here is one in quite a general form:

Problem 2: Let $\mathfrak{F}$ be a set of fields containing at least one finite field, and $\cM$ be the class of matroids representable over all fields in $\mathfrak{F}$. Determine $h_{\cM}(n)$.

This determination could be asymptotic, exact, or exact for all large $n$. Some cases are easy; if $\mathfrak{F}$ contains GF$(2)$ then it is either the class of binary matroids or regular matroids. If $\mathfrak{F}$ contains GF$(3)$ then the answer will follow from Whittle’s characterisation of ternary matroids [W97]. If all fields in $\mathfrak{F}$ share a common subfield that is not itself in $\mathfrak{F}$, then $\cM$ has exponential growth rate function and the (eventually exact) answer probably follows from our theorem above. If $\mathfrak{F} = \{\mathrm{GF}(4), \mathrm{GF}(5)\}$ then $\cM$ is the class of golden-mean matroids and there is a conjectured answer of Archer [A05] confirmed in some cases by Welsh [W11]. The case where $\mathfrak{F}$ contains $\mathbb{C}$ and one other field GF$(q)$ is very interesting and the extremal examples are probably all Dowling geometries over GF$(q)$. Here is a concrete conjecture to that effect:

Conjecture 1: Let $q$ be a prime power. The class $\cM$ of matroids representable over $\mathbb{C}$ and GF$(q)$ has growth rate function $h_{\cM}(n) = n + (q-1)\binom{n}{2}$ for all sufficiently large $n$.

One could modify this conjecture to the case where $\cM$ is the class of $\mathbb{C}$-representable matroids with no $U_{2,t}$-minor for some integer $t \ge 4$. In this case, the extremal examples are still probably the Dowling geometries, but again not much is known.

Next time, we’ll talk about generalisations of $h_{\cM}(n)$ applying to classes that do contain all simple rank-$2$ matroids. See you then.

References

[A05] S. Archer. Near varieties and extremal matroids, PhD thesis, Victoria University of Wellington, 2005.

[G08] J. Geelen. Some open problems on excluding a uniform matroids. Adv. in Appl. Math. 41(4):628-637, 2008.

[GGW07] J. Geelen, B. Gerards, G. Whittle. Towards a matroid-minor structure theory. In Combinatorics, complexity and chance, vol. 34 of Oxford Lecture Ser. Math. Applic. 72-92. Oxford Univ. Press, Oxford, 2007.

[GN10] J. Geelen, P. Nelson. The number of points in a matroid with no $n$-point line as a minor. J. Combin. Theory Ser. B, 100(6):625-630, 2010

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, G. Royle. Maximum size binary matroids with no AG(3,2)-minor are graphic. arXiv:1304.2448 [math.CO]

[T01] A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser.B 81:318-338, 2001

[W11] M. Welsh. Golden mean and secret sharing matroids. Master’s thesis, Victoria University of Wellington, 2011.

[W97] G. Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579-603, 1997

 

10 thoughts on “Growth Rates II

  1. Hi Peter,

    The growth-rate function is known for graphs with no $K_8$-minor and for graphs with no $K_9$-minor; the latter is due to Song and Thomas.

  2. Maybe I can pose a conjecture/problem about growth rates here.

    The motivation is the following: in the class of binary matroids, $EX(F_7)$ has the same size function $\binom {n+1}{2}$ as graphic matroids.

    What is the analogue for signed graphs? Maybe a reasonable conjecture is that if we exclude all rank-$3$ non-signed-graphic ternary matroids (inside ternary matroids), then the size function of that minor-closed class is, for sufficiently large $n$ [optimistically, $n \geq 5 would do], $n^2,$
    the same as the size function of the class of signed-graphic matroids.

    The idea behind this conjecture is that to get the size function of signed-graphic matroids, it suffices to exclude the rank-3 non-signed graphic matroids — the rank-3 excluded minors determine the size function. (The conjecture, as stated, is somewhat weaker. )

    .

    • Hi Joseph,

      I think that there is only one rank-3 matroid that you need to exclude over GF(3), it has three lines through a point, two of length 4 and one of length 3. That is of course a Reid matroid. I think that there is exactly one over GF(3) and that excluding it should give growth rate $n^2$ for sufficiently large $n$.

      • I must be getting old, since I simply forgot that I have proved this conjecture in 1990! This is in Discrete and Computational Geometry 5 (1990) 83–95. I meant to posed a general form of this conjecture:
        it’s easier to explain this conjecture in $U(4)$ — the class of matroids with no 6-point-line minor. Let $C$ be the class of all rank-3 matroids in $U(4)$ not contained in $Q_3(C_3,)$ the rank-3 Dowling matroid on the cyclic group of order $3$. Then this class should have size function
        $$
        3\binom {n}{r} + r.
        $$
        The conjecture reflects the “intuition” that the rank-3 excluded minors determines the size function for large rank $r.$ .

  3. On Conjecture 1: There is a similar conjecture in my paper [J. Combin. Theory Ser. B, 50 (1990) 41 — 53; p. 42, after Proposition 1.2]. The conjecture is stated less clearly than it might have been (it allows for field extensions), but basically part of it says that the size of a rank $n$ matroid representable over $GF(q)$ and $GF(s)$ is at most the size of a rank-n Dowling matroid representable over those two fields. By one of Rado’s theorems, this conjecture is stronger than Conjecture 1, but I think it is probably of equal difficulty.

    The Reid matroids (the rank-3 matroids coding the statement that an integer $m$ equals 0) seems to play a key role here. The Reid matroids (and matroids obtained by deleting the apex) are worth further study in this context.

  4. I simply forgot that the case $q=3$ of Conjecture 1 was proved in
    “Combinatorial Geometries Representable over $GF(3)$ and $GF(q)$ I.
    {Discrete and Computational Geometry 5 (1990) 83–95]. In Part II [Graphs and Combinatorics [4 (1988) 323–332], James Oxley and I determined the maximum size matroids [for rank 3, $AG(2,3)$ is also a maximum size matroid].
    My apologies for my “senior moment”.

    The $q=3$ case was done in 1987, before all the developments in connectivity and representation theory; so there is a high probability that $q=5$ can be done relatively easily. There is also a similar conjecture for $GF(4)$ [representable over both $GF(4)$ and $GF(s),$ $s$ an odd prime, $3$ divides $p-1.$

  5. Pingback: Matroid Computation with Sage: Extensions | The Matroid Union

  6. What is known, if anything, about classes of matroids with linear growth rate? Is it essentially that the growth rate is known if and only if a precise structural characterisation is known, or are there (natural) classes where the growth rate is known but not the exact structure?

    • Maybe Jim can think of something, but I certainly can’t. As mentioned, various results of Thomason say some fairly strong things about the growth rate function for classes of graphs (he gets close to determining the linear coefficient when you exclude a fixed graph H as a minor) but there are no matroidal results I know of.

    • The growth-rate functions are known for graphs with no $K_n$-minor, for all $n\le 9$, and yet we have little idea about structure for $n>5$. I think that a lot depends on the type of extremal matroids, if the extremal behaviour is exhibited by matroids of lagre branch-width then I think that the problem becomes easier.
      The short answer is that nothing is known in general. The main conjecture is that the growth-rate is of the form $a n + b_n$ where $b_n$ is eventually periodic; moreover, it is conjectured that the extremal function is attained by matroids of bounded branch-width.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.