In this post I’ll discuss a way of constructing matroids from other matroids. A simpler form of this construction was first introduced by Rado. I will follow partly Matt DeVos’ notes on Rado matroids and partly [Oxley11, Sections 11.1-11.3].

Let $G$ be a bipartite graph, with bipartition $(X,Y)$. Denote by $N(S)$ the set of neighbours of vertices in $S$ that are in $V(G)-S$. Suppose that $M$ is a matroid on ground set $Y$ with rank function $r$. Let $t$ be any integer and define $\mathcal{C}$ to be the set of minimal non-empty subsets of $X$ satisfying $|S|>r(N(S))+t$. With this definition we have the following proposition. The proof is short, so I’ll include it.

Proposition 1: $\mathcal{C}$ is the set of circuits of a matroid on $X$.

proof: From the definition we immediately have that the first two circuit axioms are satisfied. Now consider distinct $C_1, C_2 \in \mathcal{C}$ and an element $e \in C_1 \cap C_2$. Using (in the last inequality) the fact that $C_1\cap C_2$ does not contain any member of $\mathcal{C}$, we have that $\\|C_1 \cup C_2| + |C_1 \cap C_2| = |C_1| + |C_2|\\ \geq r(N(C_1))+r(N(C_2))+2t+2\\ \geq r(N(C_1)\cup N(C_2)) + r(N(C_1) \cap N(C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+r(N(C_1 \cap C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+|C_1 \cap C_2|-t +2t +2$.

Therefore $r(N(C_1 \cup C_2)) \leq |C_1 \cup C_2|-t-2$. Let $C’=(C_1 \cup C_2)-e$.

Then $r(N(C))\leq kr(N(C_1 \cup C_2))\leq |C_1 \cup C_2|-t-2=|C|-t-1$. Hence $r(N(C))< |C|-t$, so $C$ contains an element of $\mathcal{C}$. $\hspace{2 cm} \Box$

I’ll call a matroid defined this way a Rado matroid. Rado defined these matroids for $t=0$, so in this case I will call the matroid a standard Rado matroid. We may make the definition above more general by adding a parameter $k \geq 1$ and defining $\mathcal{C}$ to be the minimal non-empty sets satisfying $|S|>kr(N(S))+t$. Then the proposition above still holds (with the same proof). However, all the examples I’m going to introduce here have $k=1$, so I will stick to the simpler definition.

Note that, strictly speaking, every matroid is a Rado matroid: if $N$ is any matroid on ground set $E$, then we can obtain it as a standard Rado matroid on $G$ with bipartition $(E,E)$, where every vertex is adjacent to its copy (and the matroid on $Y=E$ is $N$). However, seeing a matroid as a Rado matroid is sometimes useful, for example in the case of the hypergraphic matroids (which I will define later).

Lots of matroids may be constructed as Rado matroids (in a non-trivial way). Since there are many objects involved in the definition of a Rado matroid and I’m a bit lazy, in the following examples I will always assume that $G, X, Y, M$ and $t$ are as above and I’ll denote just by $R$ the Rado matroid.

• If $t \leq -r(M)$, then $R=U_{0,n}$.
• If $t \geq |Y|$, then $R=U_{n,n}$.
• If $M$ is a free matroid, then the standard Rado matroid is a transversal matroid (with respect to the sets $N(v)$ for $v \in X$).
• If $H$ is a graph and $G$ has bipartition $(E(H),V(H))$, where $e \in E(H)$ is adjacent to $v \in V(H)$ if $v \in e$, and $M$ is a free matroid, then the standard Rado matroid is the bicircular matroid of $H$. Thus we see that bicircular matroids are transversal matroids [Mat77].
• Define $G$ from $H$ as above and let $M$ be a free matroid again. If now we choose $t=-1$ we obtain as a Rado matroid the graphic matroid of $H$.

We can generalise the construction above to hypergraphs. Suppose that $H=(V,F)$ is a hypergraph and define $G$ as the graph with bipartition $(F,V)$, where $f \in F$ is adjacent to $v \in V$ if $v \in f$. Let $M$ be a free matroid and set $t=-1$. Then $R$ is the hypergraphic matroid, defined by Lorea [Lor75]. We can also see hypergraphic matroids as standard Rado matroids, with this alternative definition. Our starting hypergraph is still $H=(V,F)$. We define the bipartition of $G$ to be $(F,E)$, where $E$ is the edge set of $K_V$, the complete graph on $V$. For $f \in F$ and $e=uv \in E$, we set $e$ to be adjacent to $f$ if $u,v \in f$. Now if we choose $M$ to be the graphic matroid on $K_V$ then the standard Rado matroid is again the hypergraphic matroid of $H$. The advantage of this alternative definition is that Rado [Rado42] proved the following result for standard Rado matroids (where again $G, X, Y$ and $M$ are as in definition above). Call a matching independent if the set of vertices it covers in $Y$ is independent in $M$.

Theorem 2: If $R$ is a standard Rado matroid then a set $S \subseteq X$ is independent in $R$ if and only if there is an independent matching in $G$ covering $S$ (i.e. $S$ may be matched to an independent set of $M$).

From the definition of standard Rado matroids, we immediately have that a set $S \subseteq X$ is independent in $R$ exactly when $|S’|\leq r(N(S’))$ for every $S’$ contained in $S$. Thus Rado’s theorem is saying that this condition is satisfied exactly when $S$ may be matched to an independent set of $M$. This result looks suspiciously similar to P. Hall’s marriage theorem [Hall35]: in fact we obtain Hall’s marriage theorem from Theorem 2 when $M$ is a free matroid. A proof of Theorem 2 may be found, for example, in Matt DeVos’ notes on Rado matroids. In the same notes you may also find a proof of the following generalisation of König’s Theorem for bipartite graphs.

Theorem 3: There exists $A$ contained in $X$ such that the size of the largest independent matching is equal to $|X-A|+r(N(A))$.

Corollary 4: In a standard Rado matroid, the rank of $S\subseteq X$ is equal to $$min_{A \subseteq S} \{|S-A|+r(N(A))\}.$$

Going back to our definition of a hypergraphic matroid as a standard Rado matroid, Theorem 2 tells us that a set of hyperedges $I$ is independent in this matroid if and only if we may replace every $f \in I$ with an edge $uv$, for $u,v \in f$, so that the resulting graph is a forest. This result was proved in [FKK03] (using the first definition of hypergraphic matroids).

Another interesting application of Rado’s construction is that we may obtain the Matroid Union Theorem (so relevant to our blog) as a consequence.  In fact, let $N_1,\ldots,N_k$ be matroids on a common ground set $E$, and let $M$ be the direct sum of $N_1,\ldots,N_k$. Define a bipartite graph $G$ with bipartitions $E$ and $E_1\cup \cdots\cup E_k$, where each $E_i$ is a copy of $E$ (seen as the ground set of $N_i$). Any element $e \in E$ is adjacent to each of its copies in $E_1,\ldots,E_k$. Then the standard Rado matroid is just the union matroid $N_1 \vee \cdots \vee N_k$, first introduced by Nash-Williams [N-W66]. As expected, Corollary 4 implies that the rank of a set $S$ in $N_1 \vee \cdots \vee N_k$ is $$min_{A \subseteq S} \{|S-A|+r_1(A)+\cdots +r_k(A)\},$$ where $r_i(A)$ is the rank of $A$ in $N_i$.

I was first introduced to Rado matroids while working on a paper [DMP13] with Matt DeVos and Jessica McDonald. Another nice theorem that we used in that paper is a result by Király, Lau and Singh [KLS08]. Basically this theorem says that, if $M$ has a fractional basis satisfying some constraints, then it has an actual basis almost satisfying those constraints. This theorem has nothing to do with Rado matroids, but I think it’s a nice result so I’m going to go ahead and end my post on it. First let me define what I mean by a fractional basis.

Let $M$ be a matroid on $E$ with rank function $r$ and let $x \in \mathbb{R}^E$ be a vector satisfying the following three constraints:

1. $0 \leq x(e) \leq 1$, for every $e \in E$.
2. $x(S) \leq r(S)$, for every $S \subseteq E$.
3. $x(E)=r(E)$.

Then we say that $x$ is a fractional basis of $M$. The name is justified by the following result of Edmonds’ [Edm69].

Theorem 5: If a vector $x$ satisfies 1. and 2. above, then $x$ is a convex combination of incidence vectors of independent sets of $M$.

Thus a fractional basis is a convex combination of incidence vectors of bases of $M$. The last result of this post (from [KLS08]) may be used, for example, to prove the existence of a bounded degree spanning tree in a graph if a bounded degree fractional spanning tree exists.

Theorem 6: Let $M$ be a matroid on $E$, let $x$ be a fractional basis of $M$, and let $\mathcal{F}$ be a collection of subsets of $E$ so that every $e \in E$ is contained in at most $d$ members of $\mathcal{F}$. Then $M$ has a basis $B$ such that every $F \in \mathcal{F}$ satisfies $|B \cap F| \leq \lceil x(F) \rceil +d -1$.

References

[DMP13] M. DeVos, J. McDonald, I. Pivotto, Packing Steiner trees, submitted. (available on the ArXiv)

[Edm69] J. Edmonds, Submodular functions, matroids and certain polyhedra, Com- binatorial structures and their applications (Proc. Calgary Internat. Conf. 1969), 69-87. Gordon and Breach, New York.

[FKK03] A. Frank, T. Király, and M. Kriesell, On decomposing a hypergraph into $k$ connected sub-hypergraphs, Discrete Appl. Math. 131 (2003), 373-383.

[Hall35] P. Hall, On representatives of subsets, Quart. J. London Math. Soc. 10 (1935), 26-30.

[KLS08] T. Király, L. C. Lau, and M. Singh, Degree bounded matroids and submodular flows, Proceedings of 13th International Conference IPCO 2008, LNCS 5035 (2008), 259-272.

[Lor75] M. Lorea, Hypergraphes et matroides, Cahiers Centre Etud. Rech. Oper. 17 (1975), 289-291.

[Mat77] L.R. Matthews, Bicircular Matroids, Quart. J. Math. Oxford (2), 28 (1977), 213-228.

[N-W66] C. St. J. A, Nash-Williams, An application of matroids to graph theory, In Theory of Graphs (Internat. Sympos. Rome) (1966), 263-265. Dunod, Paris

[Oxley11] J. Oxley, Matroid Theory, Oxford University Press, New York (2011).

[Rado42] R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89.

In this post I’m going to conclude my investigation of Coxeter matroids and related objects.

We can motivate the definition of Coxeter matroids by thinking about a geometrical problem in the Euclidean space $\mathbb{R}^{n}$. Recall that a (closed) half-space is a set of the form $\{\mathbf{v}\in \mathbb{R}^{n}\colon
\mathbf{v}\cdot \mathbf{a}\geq b\}$, where $\mathbf{a}$ is a fixed (non-zero) vector, $b$ is a real number, and the dot denotes the standard inner product. A polyhedron is an intersection of finitely many half-spaces. A polyhedron is a polytope if it is bounded, meaning that there there must be some ball of finite radius centred on the origin that contains every point of the polytope. A vertex of a polyhedron is a point $\mathbf{p}$ in the polyhedron with the property that some affine hyperplane intersects the polyhedron exactly in $\mathbf{p}$. Similarly, an edge of a polyhedron is a line segment, $l$, such that some affine hyperplane intersects the polyhedron exactly in $l$. The terminal points of an edge are always vertices of the polytope.

Now let $P$ be a polytope. For every edge $l$ of $P$, there is an affine hyperplane that is perpendicular to $l$ and that passes through the mid-point of $l$. This affine hyperplane determines an isometry (a distance-preserving transformation) of $\mathbb{R}^{n}$: namely, reflection through the hyperplane.

What can we say about the group of isometries generated by these reflections? As the composition of any reflection with itself is the identity, this group is a Coxeter group, since the definition of such a group is that it must have a set of generators each of which has order two. When will this Coxeter group be finite? It is easy to find examples of polytopes that lead to finite Coxeter groups: just take any regular polygon. In this case the reflections generate the dihedral group. On the other hand, consider the points with polar coordinates $(0,0)$, $(1,-\alpha)$, $(1,\alpha)$, and $(1,3\alpha)$, where $\alpha$ is an irrational fraction of a full rotation. The intersection of all half-spaces that contain these four points is a polytope. The reflections corresponding to the edges of the polytope include the reflection in the horizontal axis, and also the reflection in the line with an angle of $2\alpha$ from the horizontal. Between them, these reflections generate a rotation of $4\alpha$ around the origin. The way that we chose $\alpha$ means that no finite power of this rotation will ever be equal to the identity isometry. Therefore the generated Coxeter group is infinite. The definition of Coxeter matroids is motivated by a partial solution of this problem of determining whether this generated group of isometries will be finite or infinite.

We have said that any regular polygon gives rise to a finite Coxeter group of isometries.
Let us now develop another method for finding such polytopes. Let $W$ be a finite group of isometries of $\mathbb{R}^{n}$ and assume that $W$ is generated by a collection of reflections. We will show that there is a point that is fixed by every isometry in $W$. Indeed, if $\mathbf{v}\in \mathbb{R}^{n}$ is arbitrarily chosen, then the barycentre of the images of $\mathbf{v}$ is fixed by every isometry in $W$, because
\[
u\left(\frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})\right)
= \frac{1}{|W|}\sum_{w\in W}u(w(\mathbf{v}))
= \frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})
\]
for every $u\in W$. Therefore, by translating, we might as well assume that the reflections that generate $W$ all fix the origin. For each reflection $r\in W$, choose two vectors, $\mathbf{v}_{r}$ and $-\mathbf{v}_{r}$ that are orthogonal to the $r$-invariant hyperplane. Thus $r(\pm\mathbf{v}_{r})=\mp\mathbf{v}_{r}$. We shall call the collection $R=\{\pm \mathbf{v}_{r}\colon r\ \text{is a reflection in}\ W\}$ a root system of $W$. Note that the vectors in $R$ correspond in a natural way to the reflections in $W$. We have given no consideration to the length of the vectors $\mathbf{v}_{r}$, which means that we are not using the standard definition of a root system. This diagram shows a possible root system in $2$ dimensions.

Now let $\mathbf{a}$ be a fixed and arbitrary vector, and let $R^{+}=\{\mathbf{u}\in R\colon \mathbf{u}\cdot\mathbf{a}>0\}$ be the set of positive roots. The positive roots generate the positive cone, consisting of all linear combinations of vectors in $R^{+}$ with all coefficients non-negative. This positive cone is a polyhedron. Those vectors in $R^{+}$ that are parallel with an edge of the positive cone form a simple system of roots. In the following diagram, we have chosen $\mathbf{a}$ to be the vector $(1,0)$. There are three positive roots, and they generate the shaded positive cone. The two vectors coloured red form the corresponding simple system.

Let $I$ be the simple system of roots, and let $J$ be a non-empty subset of $I$. The roots in $J$ correspond to a collection of reflections in $W$. Let $P$ be the subgroup of $W$ generated by these reflections. This subgroup is called a standard parabolic subgroup of $W$. In our example, let $P$ be the subgroup generated by the reflection along the line parallel to $(1,1)$, that is, the reflection corresponding to the blue vector in the diagram below. Let $\mathcal{M}$ be a collection of cosets of $P$. In our example, we will keep things simple, and just let $\mathcal{M}$ be the collection of all cosets. We choose a point $\mathbf{v}$ that is fixed by $P$. For every coset $wP$ in $\mathcal{M}$, we find the image of $\mathbf{v}$ under $w$. Note that this image is well-defined, in the sense that it does not depend on the representative $w$, since $\mathbf{v}$ will be fixed by every isometry in $P$. Now we have generated a collection of images of $\mathbf{v}$. We construct the convex hull of these images: that is, we take the polytope consisting of the intersection of all half-spaces that contain the images of $\mathbf{v}$. It turns out that the Coxeter group generated by the edges of this polytope is finite (a subgroup of $W$ in fact). In the diagram below, the vector $\mathbf{v}$ is marked. There are four images of $\mathbf{v}$ under cosets of $P$, and the convex hull of those images is the shaded square.

What is surprising about this construction, is that every polytope generating a finite Coxeter group can essentially be constructed in this way. This is a consequence of a theorem due to Gelfand and Serganova (details are in the book Coxeter matroids).
So far, the link to matroids is not at all obvious, so I will conclude by drawing a connection back to my first post. Let $w_{1},\ldots, w_{t}$ be the reflections in $W$ that correspond to the vectors in a simple root system. Then $W$ is generated by $w_{1},\ldots, w_{t}$, so every $u\in W$ can be expressed as a word in these reflections. Such a word is said to be reduced if it is as short as possible. Now for $u,v\in W$ we say that $v\leq u$ in the Bruhat ordering if there is a reduced word that represents $u$, with the property that I can obtain a word representing $v$ by deleting some characters. If $w\in W$, then we write $v\leq^{w} u$ to mean $w^{-1}v\leq w^{-1}u$. If $A$ and $B$ are cosets, then $A\leq^{w} B$ means that $v\leq^{w} u$ for some representatives $v\in A$ and $u\in B$. The connection to matroids comes from the collection $\mathcal{M}$ of cosets. In our construction, $\mathcal{M}$ has the following property: if $w$ is any reflection in $W$, then there is a coset $B\in \mathcal{M}$ with the property that $A\leq^{w} B$ for all $A\in \mathcal{M}$. Now the resemblance to matroids, as axiomatised via Gale’s Theorem, is quite striking. The cosets in $\mathcal{M}$ play the role of bases in Gale’s Theorem. Now we can finally give the definition of a Coxeter matroid, which is justified by this resemblance to Gale’s axiomatization. If $W$ is a Coxeter group with $P$ as a parabolic subgroup, and $\mathcal{M}$ is a collection of cosets, then $\mathcal{M}$ is a Coxeter matroid if, for every $w\in W$, there is a coset $B\in \mathcal{M}$ such that $A\leq^{w} B$ for all $A\in \mathcal{M}$.

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]