Growth Rates V

$\newcommand{\mcsigned}{\mathcal{G}^{\mathrm{sg}}}
\newcommand{\mcevencycle}{\mathcal{G}^{\mathrm{ec}}}
\newcommand{\mcfree}{\mathcal{G}^{\mathrm{tr}}}$
Hi everyone, happy new year and sorry for my recent absence/lateness!

Today I am going to say some things about growth rates of minor-closed classes, but in more concrete cases that I’ve been writing about previously. To recap on a definition that has come up many times on this blog, the growth rate function of a minor-closed class of matroids is the definition capturing the answer to a question that Joseph Kung called the ‘primary concern’ of extremal matroid theory: given a minor-closed class $\mathcal{M}$ of matroids, what is the maximum number of elements that a simple rank-$r$ matroid in $\mathcal{M}$ can have? For each nonnegative integer $n$, the growth rate function for $\mathcal{M}$ at $n$ is defined as follows:

$h_{\mathcal{M}}(n) = \max\{|M|: M \in \mathcal{M} \text{ simple}, r(M) \le n\}$.

For instance, for the class $\mathcal{G}$ is the class of graphic matroids we have $h_{\mathcal{G}}(n) = \binom{n+1}{2}$. In fact, the growth rate theorem [GKW09] says that every minor-closed class of matroids with finite growth rate function either has growth rate function in $O(n)$, or contains the graphic matroids (and therefore has growth rate function at least $\binom{n+1}{2}$ for all $n$). Thus, the graphic matroids have the smallest possible growth rate function that is not just linear in $n$.

There are other classes of matroids with growth rate function exactly $\binom{n+1}{2}$ for all $n$, or for all but a few $n$. They necessarily contain the graphic matroids, but can be strictly larger. Several were mentioned in a post by Irene last year; they include the regular matroids, and the class $\mathrm{Ex}(\mathrm{AG}(3,2))$ of binary matroids with no $\mathrm{AG}(3,2)$-minor. The former result was shown by Heller [H57] and the latter by Kung et al [KMPR13]. Given this (and Irene asked a question along these lines in her post), it is natural to ask for a characterisation of exactly which classes of matroids grow like the graphic ones:

Problem 1: Characterise the minor-closed classes of matroids $\mathcal{M}$ that satisfy $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

or, more concretely, we could ask to characterise the minors whose exclusion gives such a class:

Problem 2: Let $\mathcal{O}$ be a finite set of simple matroids and let $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$ be the class of matroids with no minor in $\mathcal{O}$. Characterise when $\mathcal{M}$ satisfies $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

Nice Classes

This post will answer both these questions. Before I state the theorem that does this, I’ll give three examples of minor-closed classes that do grow faster than the graphic matroids.

  • The class $\mcevencycle$ of even cycle matroids having a signed graph representation with a blocking pair (that is, a pair of vertices through which all negative cycles pass). This class contains only binary matroids and has growth rate function $\binom{n+2}{3}-3$.
  • The class $\mcsigned$ of signed-graphic matroids having a signed graph representation with a vertex that is contained in every nonloop negative cycle. This class contains matroids representable over every field of odd order, and has growth rate function $\binom{n+2}{2}-2$
  • The class $\mcfree$ that is the union of the class of graphic matroids and the class of truncations of graphic matroids. There is no finite field over which every matroid in this class is representable, and it has growth rate function $\binom{n+2}{2}$.

The superscripts stand for ‘even cycle’, ‘signed graphic’ and ‘truncation’ respectively.  These are three ‘nice’ classes of matroids that are a bit bigger than the graphic matroids, all arising from well-known classes and constructions. The following theorem resolves Problem 1, and will also be enough to resolve 2.

Theorem 1 [GN14]: Let $\mathcal{M}$ be a minor-closed class of matroids with growth rate function in $\Theta(n^2)$. Either

  • $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$, or
  • $\mathcal{M}$ contains one of $\mcevencycle$, $\mcsigned$, or $\mcfree$.

Note that this ‘or’ is really an ‘exclusive or’, since the latter outcome implies that $h_{\mathcal{M}}(n) \ge \binom{n+2}{2}-3$ for all $n \ge 4$ and therefore that the former outcome does not hold. This theorem gives a very nice answer for problem 1; the classes that grow like the graphic matroids are exactly those that do not contain any of three particular classes that are all too big.

To deal with Problem 2, we just need to understand which minors that $\mathcal{O}$ must contain in order that $\mathrm{Ex}(\mathcal{O})$ does not contain any of $\mcevencycle$, $\mcsigned$ or $\mcfree$. This is just saying that $\mathcal{O}$ should contain a matroid from each of these classes. The classes actually intersect, so a single matroid in $\mathcal{O}$ could serve a dual purpose. For $\mathrm{Ex}(\mathcal{O})$ to be quadratically dense, it is also necessary to have some rank-$2$ uniform matroid in $\mathcal{O}$ and no graphic matroid in $\mathcal{O}$. The answer to Problem 2 is therefore in the following corollary:

Corollary 1: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{M}$ contains a rank-$2$ uniform matroid, contains no graphic matroids, and contains a matroid from each of $\mcevencycle$, $\mcsigned$ and $\mcfree$.

This solves the problem in general. We can also obtain specialisations to particular fields. The binary case (that is, where $U_{2,4} \in \mathcal{O}$) says the following:

Corollary 2: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M}$ is the set of binary matroids with no minor in $\mathcal{O}$, then the following two statements are equivalent:

  1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
  2. $\mathcal{O}$ contains no graphic matroids, and contains a nongraphic matroid in $\mcevencycle$.

When $\mathcal{O} = \{\mathrm{AG}(3,2)\}$ we get (for large $n$) the aforementioned result of Kung et al. There is also a similar corollary for matroids over any fixed odd-order finite field, where $\mcevencycle$ is replaced by $\mcsigned$.

Future Work

Theorem 1 should just be the beginning of an effort to characterise quadratic growth rate functions completely. It would be really nice to answer the following question:

Problem 3: Which functions in $\Theta(n^2)$ can occur as growth rate functions?

It follows from Theorem 1 that any function strictly between $\binom{n+1}{2}$ and $\binom{n+2}{2}-3$ cannot. In general, a conjecture of Geelen, Gerards and Whittle [GGW14] suggests that all such functions are quadratic polynomials with half-integral leading coefficient. Matroid structure theory in [GGW14] should (with enough work) give the answer for classes over any fixed finite field, but I would love to know what can be done without appeals to structure theory, since we are probably a long way off full structure theorems for general matroids.

[H57] I. Heller, On linear systems with integral valued solutions, Pacific J. Math. 7 (1957), 1351-1364.

[GGW14] J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5102.

[GKW09] J. Geelen, J. P. S. Kung, and G. Whittle, Growth rates of minor-closed classes of matroids, J. Combin. Theory Ser. B, 99(2):420–427, 2009

[GN14] J. Geelen, P. Nelson, Matroids denser than a clique, arXiv:1409.0777

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

 

Regularity

Somewhat ironically for a ten-day-late blog post, I’ll be writing today about regularity.

This post has something of quite a different flavour from my previous posts – we’ll be discussing an analogue of Szemeredi’s regularity lemma for binary matroids. All our matroids today are simple and binary. As with the regularity lemma for graphs, though, it would be a mistake to just state the result without motivation; so we’ll discuss it in the context of trying to prove the following theorem:

Theorem 1: For all $\alpha > 0$ there exists $c \in \mathbb{N}$ such that, if $M$ is a simple binary matroid with $|M| \ge \alpha 2^{r(M)}$ and with no $C_5$-restriction, then $M$ has critical number at most $c$.

The critical number (usually called critical exponent) of a binary matroid $M$, viewed as a restriction of some projective geometry $G \cong \mathrm{PG}(n-1,2)$, is the minimum $t \ge 0$ such that $G$ has a rank-$(n-t)$ flat disjoint from $E(M)$. This doesn’t depend on the choice of $G$, giving the same $t$ even when $n > r(M)$. Critical number looks a bit strange but is actually a close analogue of chromatic number, which is why I’ve dropped the term ‘exponent’.

For example, for a graph $G$, the critical number of $M(G)$ is $1$ if and only if $G$ is bipartite. In general, the matroids of critical number $1$ are the restrictions of an affine geometry. Having bounded critical number is quite a strong constraint on a binary matroid with exponentially many elements, so Theorem 1 is a nice result. The analog for graphs, which says that every $C_5$-free graph $G$ with minimum degree at least $\alpha |V(G)|$ for $\alpha > 0$ has chromatic number bounded by a function of $\alpha$, was proved by Thomassen [3] in 2007.

The regularity lemma for graphs says, very roughly, that for every graph $G$, the vertex set $V(G)$ admits a partition into a bounded number of blocks of nearly equal size, so that nearly every pair of blocks induces a pseudorandom bipartite graph. Less roughly, the lemma that for all $\epsilon > 0$ and $m \in \mathbb{N}$, there is some $M$ such that every graph $G$ has a partition $(V_1, \dotsc, V_s)$ of its vertex set such that $s \le M$,  $|V_i|-|V_j| \le 1$ for each $i$ and $j$, and all but $\epsilon \binom{s}{2}$ of the pairs $i,j$ have the property that the bipartite graph consisting of the edges between $V_i$ and $V_j$ is $\epsilon$-uniform, which is some measure of randomness that gets stronger for smaller $\epsilon$; I’ll leave it undefined for graphs.

To state the regularity lemma for binary matroids, we first need to define a notion of pseudorandomness for sets of binary vectors. Let $X \subseteq V = \mathrm{GF(2)}^n$. For each codimension-$1$ subspace $H$ of $V$, note that $|V – H| = |H|$. A truly random subset of $V$ would therefore have roughly as many elements in $H$ as it does in $V – H$. We use this idea to define what we mean by pseudorandom; a set $X \subseteq V$ is $\epsilon$-uniform in $V$ if $| |X \cap H| – |X \cap (V -H)| | \le \epsilon|V|$. This definition turns out to have a natural interpretation in discrete Fourier analysis, but we won’t need to worry about that at all. We can now state the regularity lemma! This lemma was proved by Ben Green in a 2003 paper [1]. In fact, he does this in a much more general setting of finite abelian groups, but to his infinite credit he holds the reader’s hand and makes the much simpler $\mathrm{GF}(2)^n$ case its own section at the beginning. I’ll modify the lemma statement to be as concrete as I can, giving a statement about the entries of an actual binary matrix. Let $0 \le s \le r$ and let $W \in \mathrm{GF(2)}^{[r] \times E}$ be a matrix. For each vector $u \in \mathrm{GF}(2)^s$, let $W_u$ be the set of vectors $v \in \mathrm{GF}(2)^{r-s}$ such that $\binom{u}{v}$ is a column of $W$. For example, $W_{(1,1,0)}$ is the set of columns of $W$ whose first three entries are $(1,1,0)$, after the first three entries have been removed. Here’s the regularity lemma:

Green’s Regularity Lemma: For all $\epsilon > 0$, there exists $c \in \mathbb{N}$ such that, if $M$ is a binary matroid, then there is an integer $s \le c$ and a representation $W$ of $M$ with $r(M)$ rows such that $W_u$ is an $\epsilon$-regular for all but an $\epsilon$-fraction of $u \in \mathrm{GF}(2)^s$.

So, say $s = 4$ and $\epsilon = 1/16$ – this conclusion would mean that of the $16$ sets $W_{(0,0,0,0)}, W_{(0,0,0,0)}, \dotsc, W_{(1,1,1,1)}$, all but at most $16\epsilon = 1$ of them are $(1/16)$-uniform. So, just like the graph regularity lemma more or less partitions the edge set of a graph into random sets, the above lemma does this for binary matroids.

But how do we use $\epsilon$-uniformity? It is supposed to represent randomness, and there is a useful concrete way that it does: suppose $A$ is a truly random subset of $V = \mathrm{GF}(2)^n$ with $|A| = \alpha 2^n$, and let $x_0 \in \mathrm{GF}(2)^n$. We would expect around $\alpha^4 2^{3n}$ solutions $(a_1,a_2,a_3,a_4)$ to $a_1 + a_2 + a_3 + a_4 = v_0$, where $a_i \in A$ for each $i$. The great thing about uniform sets is that this estimate isn’t far off:

Sum Lemma: Let $\epsilon > 0$ and $A \subseteq V = \mathrm{GF}(2)^n$ be $\epsilon$-uniform set with $|A| = \alpha 2^n$. For each $x_0 \in \mathrm{GF}(2)^n$, the equation $a_1 + a_2 + a_3 + a_4 = x_0$ has at least $(\alpha^4 – \epsilon)2^{3n}$ solutions.

The above lemma, as well as essentially appearing in Green’s paper, appears in the textbook Additive Combinatorics of Tao and Vu [2]; we care about it because sets summing to zero are matroid circuits, so in an appropriate matroid, the above lemma tells us about $5$-circuits.

Amazingly, the regularity lemma and the sum lemma basically give Theorem 1 with very little work. Here goes:

Proof of Theorem 1: Let $\alpha > 0$ and $M$ be a simple $C_5$-free binary matroid with $|M| \ge \alpha 2^{r(M)}$. Let $\epsilon = \frac{1}{32} \alpha^4$. By Green’s regularity lemma, there is some $s \le c(\alpha,\epsilon)$ and a representation $W$ of $M$ such that $W_v$ is $\epsilon$-uniform for all but $\epsilon 2^s$ values of $v \in \mathrm{GF}(2)^s$. We argue that $M$ has critical number at most $s$. If $W_0$ is empty, then there is clearly a codimension-$s$ subspace of $\GF(2)^{r(M)}$ containing no column of $W$, so $M$ has critical number at most $s$ and we’re done. Otherwise, let $x_0 \in W_0$.

Since $\sum_{v \in \mathrm{GF}(2)^s} |W_v| = |M| \ge \alpha 2^{r(M)}$, and at most an $(\epsilon < \frac{\alpha}{2})$-fraction of the $W_v$ are not $\epsilon$-uniform, it follows that some $W_v$ satisfies $|W_v| \ge \frac{\alpha}{2} 2^{r(M)-s}$, and is also $\epsilon$-uniform. By the sum lemma, there are at least $\left(\left(\frac{\alpha}{2}\right)^4 – \epsilon\right) 2^{r(M)-s} > 0$ solutions to $w_1 + w_2 + w_3 + w_4 = x_0$ where $w_1,w_2,w_3,w_4 \in W_v$. Looking back at the matrix, we see that the columns corresponding to $w_1,w_2,w_3,w_4$ and $x_0$ form a $5$-element circuit of $M$, a contradiction.

Caveat – The last sentence is a bit of a lie, since it could be, for example, that $w_1 = w_2$ and $(w_3,w_4,x_0)$ gives a triangle of $M$, but it is actually easy to show that negligibly few of the solutions to $w_1 + w_2 + w_3 + w_4 = x_0$ can have this kind of degenerate form, so we can find a $5$-element circuit for sure.

Thus, the regularity lemma gave us pseudorandomness, and pseudorandomness gave us a plethora of $5$-circuits. What is great is that we received these techniques on a silver platter – when we started thinking about these questions and realised an analogue of the regularity lemma was vital, we were quite happy to find that it had already been done. At the moment, we’ve got a couple more applications of these ideas, which I will perhaps write about in a future post. In the meantime, our paper with the above proof is on the arxiv at http://arxiv.org/pdf/1403.1617.pdf – I tried to write it in a way that is friendly to matroid theorists, and it gives a bit more context motivating Theorem 1. See you next time!

[1] B. Green, A Szemeredi-type regularity lemma in abelian groups, with applications, Geometric & Functional Analysis GAFA 15 (2005), 340-376.

[2] T. C. Tao and V. H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics,  105, Cambridge University Press, Cambridge (2006).

[3] C. Thomassen, On the chromatic number of pentagon-free graphs of large minimum degree, Combinatorica 27 (2007), 241-243

 

 

 

An advertisement

Hi everyone,

Since Jim’s entries have been on other topics, I thought I’d take advantage of his modesty and use this entry to direct people’s attention to what I consider a very important paper he recently wrote with Bert Gerards and Geoff Whittle:

‘The highly connected matroids in minor-closed classes’,

This paper will appear in the special issue of Annals of Combinatorics for James Oxley, but currently can be found at http://arxiv.org/abs/1312.5012 .

The paper is the first to put in writing some of the amazing structure theorems for $\mathrm{GF}(q)$-representable matroids that the authors have proved on their way to Rota’s conjecture. The theorems aren’t proved in the paper, nor stated in their full generality; however, they are stated for the important special cases of highly vertically connected matroids. Incredibly, the authors give (among other things) an exact structure theorem for all sufficiently highly connected matroids in an arbitrary minor-closed class of $\mathrm{GF}(q)$-representable matroids.

Even though the high connectivity simplifies the structure theorem statements enormously, there are still some technical aspects. Nonetheless, I think this paper should give the community an important head-start on proving some theorems, in a way I will try to explain by sketching a proof of a conjecture in the paper that Stefan van Zwam and I recently came up with. Our write-up is mostly done and should be on the arxiv in the next few weeks.

The discussion in this post won’t use the ‘exact’ results stated in section 4, merely the more digestible ‘qualitative’ ones in section 3. First, here is Theorem 3.1 in the paper, stated for binary matroids. (We’ll stick with binary in this post.)

Theorem 1: Let $\mathcal{M}$ be a proper minor-closed class of binary matroids.  There exist integers $k$ and $t$ so that every vertically $k$-connected matroid in $\mathcal{M}$ is a rank-$(\le t)$ perturbation of a graphic or cographic matroid.

Here, a rank-$(\le t)$ perturbation of a binary matroid $N$ means a matroid of the form $M(A + T)$, where $A$ and $T$ are binary matrices such that $M(A) \equiv N$ and $T$ has rank at most $t$.

To get a feel for this theorem, consider the class of regular matroids, where it holds for $k = 5$ and $t = 0$; ie. the vertically $5$-connected regular matroids are either graphic or cographic. For general classes, the highly connected matroids are a bounded perturbation of graphic or cographic (as opposed to exactly (co)graphic), but this is often good enough to prove theorems.

The result we will prove is Conjecture 6.1 from the paper.. In the paper we’re writing, we have to make a bit of a song and dance about the exact correspondence between linear codes and matroids, but I’ll make this as brief as possible, just talking in terms of matroids.

We say a class $\mathcal{M}$ of binary matroids is asymptotically good if there exists $\delta > 0$ and a sequence $M_1,M_2, \dotsc, $ of matroids in $\mathcal{M}$ of increasing size such that for each $i$ the matroid $M_u$ satisfies $|M_i| \ge (1+\delta)r(M_i)$ and has no circuit of size less than $\delta |M_i|$. (Loosely, in coding theory terms, this corresponds to a sequence of codes of increasing size, all having reasonably large rate and minimum distance). The class of all binary codes is asymptotically good; choosing each $M_n$ to correspond to a random $n \times n$ binary matrix will work. On the other hand, Kashyap [3] proved the following:

Theorem 2: The classes of graphic and cographic matroids are not asymptotically good.

Our result generalises this to all proper minor-closed classes.

Theorem 3: No proper minor-closed class of binary matroids is asymptotically good.

Proving Theorem 3

Our goal is to prove Theorem 3 from Theorem 1. We do this in three steps, which together are a broad template for using the structure theorems in other ways, even though what I am discussing is going towards a specific result. The basic idea is this: suppose that we want to to prove that all large matroids in a proper minor-closed classes of binary matroids have property P. For all integers $t$ and $k$, we do the following:

  1. Prove that it suffices to prove Theorem X for the subclass of vertically $k$-connected matroids in $\mathcal{M}$.
  2. Prove a strong version of Theorem X for graphic and cographic matroids; call this Theorem Y.
  3. Using Theorem Y, prove that Theorem X holds for the rank-$(\le t)$ perturbations of graphic and cographic matroids.

Together with Theorem 1, these steps imply that Theorem X holds for $\mathcal{M}$. – I’ll leave that deduction as an exercise. In our case, Theorem X is the statement that the class $\mathcal{M}$ is asymptotically good.

Step 1: Connectivity reduction
First, we bootstrap our way up to vertical $k$-connectivity via the following Lemma.

Lemma 4: Let $k$ be an integer. If $\mathcal{M}$ is asymptotically good, then so is the class of vertically $k$-connected matroids in $\mathcal{M}$.

This involves thinking about how very small separations in a matroid interact with small circuits. Like with most of these things, the numbers are fiddly, but in the end small vertical separations ought not to show up in a ‘best’ sequence certifying asymptotic goodness of $\mathcal{M}$, and the numbers bear this out. Now on to the next step…

Step 2: Graphic and Cographic

We saw earlier that Kashyap proved that the graphic and cographic matroids are not asymptotically good classes. We need something stronger, though: a result that can survive a perturbation. What we prove is the following:

Lemma 5: If $M$ is a graphic or cographic matroid with $|M| \ge (1+\delta)r(M)$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X| – 2t$ and $|X| = O(\log r(M))$.

The cographic case is very easy (the associated graph has constant average degree, so just take the union of a collection of small stars). The graphic case follows from a result of Alon, Hoory and Linial [1] which finds a single circuit of logarithmic size – if we apply this $(2t+1)$ times after removing the circuits successively, we get our required set. Finally…

Step 3: Surviving a perturbation

We constructed Lemma 5 to still give us a result when $M$ is perturbed. The following is an easy exercise:

Lemma 6: If $M$ is a rank-$(\le t )$ perturbation of $M’$, then $|r_M(X) – r_{M’}(X)| \le 2t$ for each $X \subseteq E(M)$.

From this and Lemma 5 (and a tiny bit of fudging with changing the rank of the matroid), we get what we want:

Lemma 7: If $M$ is a rank-$(\le t)$ perturbation of a graphic or cographic matroid and $|M| \ge (1+ \delta)|M|$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X|$ and $|X| = O(\log r(M))$.

And now we’re done – here’s the argument. Suppose that $\mathcal{M}$ is an asymptotically good minor-closed class of binary matroids. Let $k$ and $t$ be the integers given by Theorem 1. By Lemma 4, the class of vertically $k$-connected matroids in $M$ is asymptotically good. By Theorem 1, every such matroid is a rank-$(\le t)$ perturbation of graphic or cographic. By Lemma 7, any such matroid with $|M| \ge (1+ \delta)r(M)$ contains a dependent set of logarithmic size; this contradicts the definition of asymptotic goodness.

I hope this post has given you some idea of the power of the structure theorems in this paper. Being able to apply our knowledge of graphic and cographic matroids to arbitrary minor-closed classes of binary matroids is a huge boon, one that certainly deserves our attention. I haven’t even discussed nonbinary matroids or the exact structural results – maybe I’ll get to the latter in my next post. Until then, I’ll see you round!

[1] N. Alon, S. Hoory and N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2001), 53-57.

[2] J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5102 [math.CO].

[3] N. Kashyap, A decomposition theory for binary linear codes, IEEE Transactions on Information Theory 54 (2008), 3035-3038.

Growth Rates IV

$\newcommand{\elem}{\varepsilon}$
Time for more growth rates. For a matroid $M$ we’ve looked at $\elem(M)$, the number of points in $M$, as a simple density parameter that is bounded as a function of $\ell$ and $r$ whenever we exclude $U_{2,\ell+2}$ as a minor. Then, as a way to talk about density when excluding a uniform minor of larger rank than $2$, we generalised this to $\tau_a(M)$, defined to be the number of rank-$a$ flats required to cover $\elem(M)$, which turned out to be the right notion of density to think about when excluding a rank-$(a+1)$ uniform matroid as a minor. As far as excluding different uniform minors is concerned, $\tau_a$ is the generalisation of $\elem$ that we need. However, there is another natural way to generalise $\elem(M)$ to ‘higher rank’, which is what this post is about.

For a matroid $M$ and a nonnegative integer $k$, we let $W_k(M)$ denote the number of rank-$k$ flats in $M$. This parameter, known as the $k$th Whitney number of the second kind, is clearly of interest when thinking about the lattice of flats of $M$. A 1971 conjecture of Rota [R71] is that the sequence $W_0(M),W_1(M), \dotsc, W_r(M)$ is unimodal; that is, that $W_k(M) \ge \min(W_{k-1}(M),W_{k+1}(M))$ for each $k$. From what I can see in the published literature, this conjecture is still open, although Huh, Katz and Lenz [HK11,L11] have recently used sophisticated algebraic techniques to make real progress on similar conjectures in the representable case. In fact, Mason [M72] conjectured a few strengthenings of this conjecture; the first and weakest is that the sequence of Whitney numbers is log-concave (which is itself stronger than unimodality).

What I’m considering today relates more to previous posts than the above conjectures: bounding $W_k(M)$ above by a function of $\ell$ and $r(M)$ when excluding a $U_{2,\ell+2}$ (when excluding a larger uniform minor it is not hard to argue that no such bound is possible). This has quite a different flavour to the conjecture above; we know that in many ways excluding a uniform minor gives classes whose extremal members resemble projective geometries, so we’d hope that the bounds we get are similar or equal to those we get for geometries. The number of rank-$k$ flats in a geometry PG$(n-1,q)$ is a nice number which we denote ${n \brack k}_q$. More explicitly,
\[ W_k(\mathrm{PG}(n-1,q) = {n \brack k}_q = \frac{(q^n-1)(q^{n-1}-1)\dotsc(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\dotsc(q-1)}\]
This is known as the Gaussian binomial coefficient for $n,k$ and $q$. We already know by Kung’s theorem that a rank-$r$ matroid with no $U_{2,q+2}$-minor has at most ${r \brack 1}_q = \frac{q^r-1}{q-1}$ rank-$1$ flats. The natural generalisation of this statement was conjectured by Bonin:

Conjecture 1: If $q$ is a prime power and $M$ is a rank-$r$ matroid with no $U_{2,q+2}$-minor, then $W_k(M) \le {r \brack k}_q$ for each integer $k$.

Unfortunately, this conjecture is false – I’ll get to the counterexample in a minute. In [N13] I proved this conjecture whenever $r$ is large compared to $k$ and $q$. In fact, as with our generalisation of Kung’s theorem in our first post, I get the projective geometry bound for excluding an arbitrary rank-$2$ uniform minor, not just one corresponding to a prime power.

Theorem 1: For all integers $\ell \ge 2$ and $k \ge 0$ there is an integer $r_0$ such that, if $M$ is a matroid with no $U_{2,\ell+2}$-minor and $r(M) \ge r_0$, then $W_k(M) \le {r(M) \brack k}_q$, where $q$ is the largest prime power not exceeding $\ell$.

It is good to know this. However, this theorem doesn’t tell us everything. For many reasons, it would be very nice to have a good upper bound on the number of hyperplanes of a matroid with no $U_{2,q+2}$-minor; the above theorem says nothing when $k = r-1$, only when $r$ is huge compared to $k$. One can obtain a crude upper bound on the number of hyperplanes by bounding the number of points and observing that each hyperplane is spanned by $r-1$ points, but this bound, roughly $q^{q^2}$, is likely dramatically wrong.

Conjecture 1 would imply that the correct upper bound for the number of hyperplanes when excluding $U_{2,q+2}$ is $\frac{q^r-1}{q-1}$. I don’t have any good ideas for how to prove this, and in fact this is where the conjecture fails – the next theorem follows from a construction communicated to me by Blokhuis.

Theorem 2: For each prime power $q$ there is a rank-$3$ matroid $M_q$ with no $U_{2,2q}$-minor such that $W_2(M_q) = q^2 + (q+1)\binom{q}{2}$.

For large $q$, this is too many lines for Conjecture 1 to hold! There are issues with the precise numbers, but essentially Conjecture 1 would state that $W_2(M) \le q^2 + q+ 1$ for any matroid $M$ with no $U_{2,q+2}$-minor; this is quadratic in $q$, but $W_2(M_q)$ is cubic in $q$. The factor of $2$ in the length of the line that $W_2(M_q)$ omits is unimportant in the face of this qualitative difference. It is fairly easy to use Theorem 2 to find counterexamples to Conjecture 1 for all $q \ge 128$; Using a variation on the construction and a bit of work for small $q$, Jim and I [GN13] proved the following:

Theorem 3: When $r = 3$ and $k = 2$, Conjecture 1 holds if and only if $q \le 5$. On the other hand, when $q \in \{2,3,4\}$, and $k = 2$, Conjecture 1 holds for all $r$.

The first part of this is unfortunate, as Conjecture 1 is pretty. What I would hope is that the examples in Theorem 2 are a result of rank-$3$ sporadicity of the same sort that makes projective planes so hard to classify for finite geometers. It’s quite possible that Conjecture 1 holds for all $r \ge 4$, but I would settle for the following.

Conjecture 2: For all $q$ there is an integer $r_0$ such that Conjecture 1 holds for $q$, all $k$ and all $r \ge r_0$.

The difference between this statement and that of Theorem 1 is that there is no longer any dependence of $r_0$ on $k$; the above conjecture would give a sensible upper bound on the number of hyperplanes. It would also be very interesting to see what happens in even the smallest concrete rank-$4$ cases for which we don’t already have the answer:

Conjecture 3: Conjecture 1 holds for $r = 4, k = 3$ and $q = 3$.
Conjecture 4: Conjecture 1 holds for $r = 4, k = 2$ and $q = 7$.

Next time, I’ll be back talking about something other than growth rates. See you then!

References
[GN13] J. Geelen, P. Nelson, The number of lines in a matroid with no $U_{2,n}$-minor, arXiv:1306.2387 [math.CO]
[HK11] J. Huh, E. Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, arXiv:1104.2519 [math.CO]
[L11] M. Lenz, Matroids and log-concavity, arXiv:1106.2944 [math.CO]
[M72] J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem. In Combinatorics (eds. D. J. A. Welsh and D. R. Woodall), pp 207-220 (1972). Institute of Math. and its Applications, Southend-on-Sea. [15.2]
[N13] P. Nelson, The number of rank-$k$ flats in a matroid with no $U_{2,n}$-minor, arXiv:1306.0531 [math.CO].
[R71] G.-C. Rota, Combinatorial theory, old and new. In Proc. Internat. Cong. Math.<> (Nice, 1970), pp. 229-233. Gauthier-Villars, Paris (1971). [6.0,6.5,14.0,15.2].