$\\newcommand{\\elem}{\\varepsilon}$
\nTime 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.<\/p>\n
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\u00a0Lenz [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).<\/p>\n
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, Conjecture 1:<\/strong> 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$.<\/p>\n 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.<\/p>\n Theorem 1:<\/strong> 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$.<\/p>\n 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. <\/p>\n 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.<\/p>\n Theorem 2:<\/strong> 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}$.<\/p>\n 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:<\/p>\n Theorem 3:<\/strong> 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$.<\/p>\n 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.<\/p>\n Conjecture 2:<\/strong> For all $q$ there is an integer $r_0$ such that Conjecture 1 holds for $q$, all $k$ and all $r \\ge r_0$.<\/p>\n 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:<\/p>\n Conjecture 3:<\/strong> Conjecture 1 holds for $r = 4, k = 3$ and $q = 3$. Next time, I’ll be back talking about something other than growth rates. See you then!<\/p>\n References<\/strong> $\\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 … Continue reading
\n\\[ 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)}\\]
\nThis is known as the Gaussian binomial coefficient\u00a0<\/em>for $n,k$ and $q$.\u00a0We 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:<\/p>\n
\nConjecture 4:<\/strong> Conjecture 1 holds for $r = 4, k = 2$ and $q = 7$.<\/p>\n
\n[GN13] J. Geelen, P. Nelson, The number of lines in a matroid with no $U_{2,n}$-minor<\/em>, arXiv:1306.2387 [math.CO]
\n[HK11] J. Huh, E. Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids<\/em>, arXiv:1104.2519 [math.CO]
\n[L11] M. Lenz, Matroids and log-concavity<\/em>, arXiv:1106.2944 [math.CO]
\n[M72] J. H. Mason,\u00a0Matroids: unimodal conjectures and Motzkin’s theorem.\u00a0<\/em>In\u00a0Combinatorics <\/em>(eds. D. J. A. Welsh and D. R. Woodall), pp 207-220 (1972). Institute of Math. and its Applications, Southend-on-Sea. [15.2]
\n[N13] P. Nelson, The number of rank-$k$ flats in a matroid with no $U_{2,n}$-minor,\u00a0<\/em>arXiv:1306.0531 [math.CO].
\n[R71] G.-C. Rota, Combinatorial theory, old and new.<\/em> In Proc. Internat. Cong. Math.<<\/em>> (Nice, 1970), pp. 229-233. Gauthier-Villars, Paris (1971). [6.0,6.5,14.0,15.2].<\/p>\n","protected":false},"excerpt":{"rendered":"