Too dense to measure? 

I’m back, writing more about growth rates of matroids in minor-closed classes. In the last two posts, I’ve been talking about the growth rate function $h_{\mathcal{M}}$ of a class, which measures the maximum number of elements in a simple rank-$n$ matroid in the class, or (essentially) equivalently the maximum number of points in a rank-$n$ matroid of the class, which is not necessarily required to be simple. In this post I’ll stop using the ‘function’ notation and instead just state things more explicitly for individual matroids.

The reason for this is that I’ll be writing this time about matroids whose growth rate function is infinite, but still seem ‘sparse’ compared to random matroids.  The easiest example of this is the class of bicircular matroids, which are the graph-like matroids obtained by starting from a basis B and freely extending lines spanned by pairs of elements of B any number of times. (Technically we have to close under minors also). These are the same class as the matroids having a real-representation where each column contains at most two nonzero entries and all nonzero entries are algebraically independent.

An easy observation is that a rank-$n$ bicircular matroid can have arbitrarily many points, as you can keep adding new points on any line between a pair of basis elements and stay bicircular. Therefore the class of bicircular matroids contains all simple rank-$2$ matroids and there is no bound on its growth rate function. The reason this seems like a problem, though, isn’t that we’re unhappy with matroids having unbounded numbers of points, it’s that the bicircular matroids seem intuitively quite sparse.

To make this concrete, we can make the easy observation that every rank-$n$ bicircular matroid is the union of at most $\binom{n}{2}$ rank-$2$ sets. This is an unusual property that dramatically separates bicircular matroids from random matroids, and it’s how we’ll talk about the more general notion of density this post is about.

Covering Number

If $M$ is a matroid (of rank at least $a$) and $a$ is a positive integer, then $\tau_a(M)$ will denote the minimum size of a collection of rank-$a$ sets with union $E(M)$. We call this the $a$-covering number of $M$. It is not too hard to see that if $M \cong \mathrm{PG}(n-1,q)$ then $\tau_a(M)$ is roughly $\frac{q^r-1}{q^a-1}$ and that if $M \cong M(K_n)$ then $\tau_a(M)$ is roughly $\binom{n+1}{2}/\binom{a+1}{2}$, so $\tau_a$ behaves pretty similarly to counting points for nice matroids like cliques and projective geometries. However, unlike the ‘number of points’ parameter, covering number enables us to say the bicircular matroids are only quadratically dense; if $M$ is a rank-$n$ bicircular matroid then $\tau_2(M) \le \binom{n}{2}$. This seems to do much better justice to their structure.

Given an $a$, it is still easy to construct fixed-rank matroids for which $\tau_a$ is arbitrarily large. The easiest construction is just the uniform matroid $U_{a+1,b}$. In covering such a matroid with rank-$a$ sets there isn’t anything clever you can do; all the rank-$a$ sets have just $a$ elements and in the end you need $\tau_a(U_{a+1,b}) = \left\lceil\frac{b}{a}\right\rceil$ sets to do the job. However, there is a beautiful partial converse to this statement due to Geelen and Kabell [gk09], who also introduced the parameter.

Theorem 1: If $r \ge a$ and $M$ is a rank-$r$ matroid with no $U_{a+1,b}$-minor then $\tau_a(M) \le \binom{b-1}{a}^{r-a}$.

Just like Kung’s theorem did for counting points  (see my first entry), this result provides a perfect description of which minor-closed classes have the property that $\tau_a$ is bounded above by a function of rank; they are exactly those that do not contain all rank-$(a+1)$ uniform matroids. Jim Geelen conjectured much more than this, though, in his excellent paper [g08] on excluding a uniform matroid as a minor. He postulated that the growth rate theorem almost survives the generalisation to $\tau_a$ unchanged:

Conjecture 1: If $a$ is an integer and $\mathcal{M}$ is a minor-closed class of matroids, then either

1. $\tau_a(M) \le c r(M)$ for all $M \in \mathcal{M}$;
2. $\tau_a(M) \le c r(M)^2$ for all $M \in \mathcal{M}$ and $\mathcal{M}$ contains all bicircular matroids or all graphic matroids;
3. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
4. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This conjecture, which is very probably true, is quite striking; it would tell us that  $\tau_a$-density is ‘controlled’ by geometry- or graph-like matroids in any minor-closed class for which it is not a useless measure of density. The only classes left to worry about would be the ones that contain all uniform matroids of every rank, and those are much easier than the bicircular matroids to dismiss as truly ‘wild’ or ‘infinitely dense’ classes.

Jim and I made some progress [gn12,n13] towards Conjecture 1, proving the following:

Theorem 2: Let $a$ be an integer and $\mathcal{M}$ be a minor-closed class of matroids. Either

1. $\tau_a(M) \le r(M)^c$ for all $M \in \mathcal{M}$;
2. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
3. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This separates the ‘exponential’ classes from the polynomial ones. We’d really like to know more, though; the quadratic and linear part of the conjecture seems quite a lot harder.

In the meantime, it would still be great to understand the parameter $\tau_a$ in more specific settings. Here is a very concrete problem:

Problem 1: Let $M$ be a rank-$r$ $\mathbb{R}$-representable matroid with no $U_{3,6}$-minor. Find an upper bound on $\tau_2(M)$ in terms of $r$.

Theorem 1 gives an upper bound of $10^{r-2}$ and, since projective geometries are not real-representable, Theorem 2 gives $\tau_2(M) \le r^c$ for some constant $c$, but neither of these are particularly satisfactory. If Conjecture 1 holds then the answer should be quadratic in $r$, but it would be nice for it to be a quadratic with reasonable coefficients.

I also believe that, despite the non-committal constants in Theorem 2, the way that $\tau_a$ behaves in exponentially dense classes is somewhat reasonable. There are some issues when computing $\tau_a(\mathrm{PG}(r-1,q)$ when the geometry doesn’t partition neatly into nice rank-$a$ flats (the answer still turns out to be equal to the obvious lower bound), but modulo a small multiplicative factor, something like the following should be true, and possibly quite approachable by the same kind of techniques that were used in the setting of excluding a rank-$2$ minor:

Conjecture 2: If $\epsilon > 0$ and $M$ is a matroid with no $U_{a+1,b}$-minor and of sufficiently large rank, then $\tau_a(M) \le (1 + \epsilon)\tau_a(\mathrm{PG}(r(M)-1,q))$, where $q$ is the largest prime power so that $U_{a+1,b}$-is GF$(q)$-representable.

In other words, the matroids with no $U_{a+1,b}$-minor should be asymptotically no denser than the projective geometries with no $U_{a+1,b}$-minor.

See you next time!

References

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

[gk09] J. Geelen, K. Kabell, the Erdos-Posa property for matroid circuits. J Combin. Theory Ser. B, 99(2):407-419, 2009.

[gn12] J. Geelen, P. Nelson, Projective geometries in exponentially dense matroids. I,  arXiv:1209.1496 [math.CO]

[n13] P. Nelson, Projective geometries in exponentially dense matroids. II, arXiv:1306.0244 [math.CO]