Geelen's Growth Rate Conjecture for minor-closed matroid classes

About 13 years old · traced to

For a matroid MM and a positive integer aa, let τa(M)\tau_a(M) denote the minimum number of sets of rank at most aa needed to cover E(M)E(M), and let r(M)r(M) denote the rank of MM. A class of matroids is minor-closed if it contains every minor of each of its members. Let M\mathcal{M} be a minor-closed class of matroids.

Growth Rate Conjecture. For every integer age1a ge 1, there is an integer c>0c>0 such that at least one of the following holds:

τa(M)≤cr(M)\tau_a(M) \le c r(M)

for all M∈MM\in\mathcal{M};

τa(M)≤cr(M)2\tau_a(M) \le c r(M)^2

for all M∈MM\in\mathcal{M} and M\mathcal{M} contains all graphic matroids or all bicircular matroids; there is a prime power qq such that

τa(M)≤cqr(M)\tau_a(M) \le c q^{r(M)}

for all M∈MM\in\mathcal{M} and M\mathcal{M} contains all GF⁡(q)\operatorname{GF}(q)-representable matroids; or M\mathcal{M} contains all rank-(a+1)(a+1) uniform matroids. This conjecture refines the polynomial-exponential growth-rate theorem: the theorem in the paper establishes a weaker polynomial bound in the first alternative, while the linear and quadratic alternatives, and the complete classification, remain the conjectural part.

References

Primary source

Peter Nelson, “Projective geometries in exponentially dense matroids. II”, arXiv:1306.0244 (2013).

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.