The Growth Rate Conjecture for minor-closed classes of matroids

About 14 years old · traced to

Let a≥1a\geq 1 be an integer, and let M\mathcal{M} be a minor-closed class of matroids. For a matroid MM, write r(M)r(M) for its rank and let τa(M)\tau_a(M) denote the minimum number of rank-at-most-aa sets whose union is the ground set of MM. Growth Rate Conjecture. One of the following holds:

  1. τa(M)≤cMr(M)\tau_a(M)\leq c_{\mathcal{M}}r(M) for all M∈MM\in\mathcal{M};
  2. τa(M)≤cMr(M)2\tau_a(M)\leq c_{\mathcal{M}}r(M)^2 for all M∈MM\in\mathcal{M}, and M\mathcal{M} contains all graphic matroids or all bicircular matroids;
  3. there is a prime power qq such that τa(M)≤cMqr(M)\tau_a(M)\leq c_{\mathcal{M}}q^{r(M)} for all M∈MM\in\mathcal{M}, and M\mathcal{M} contains all GF⁡(q)\operatorname{GF}(q)-representable matroids; or
  4. M\mathcal{M} contains all rank-(a+1)(a+1) uniform matroids.

Here cMc_{\mathcal{M}} is a constant depending only on M\mathcal{M}. The conjecture was proved by Geelen, Kabell, Kung and Whittle, and was stated in that work as the Growth Rate Theorem.

References

Primary source

Jim Geelen and Peter Nelson, “Projective geometries in exponentially dense matroids. I”, arXiv:1209.1496 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.