$\\newcommand{\\PG}{\\text{PG}}$<\/p>\n
Denser than a Geometry<\/strong><\/p>\n Hello everyone. In my\u00a0last post<\/a>,\u00a0I discussed an unavoidable minor theorem for large matroids of density greater than $\\binom{n+1}{2}$, which as a consequence characterised exactly the minor-closed classes of matroids that grow like the the graphic matroids. Today I’ll write about the exponential analogue of this problem; this appears in a paper of mine [2] available on\u00a0the arXiv<\/a>, and\u00a0I will also be speaking on this topic at the matroid session of the upcoming\u00a0CanaDAM<\/a>\u00a0conference in Saskatchewan.<\/p>\n I’ll first state a nice theorem of Kung, specialized to prime powers:<\/p>\n Theorem:\u00a0<\/strong>If $q$ is a prime power, and $M$ is a simple rank-$n$ matroid with $|M| > \\frac{q^n-1}{q-1}$, then $M$ has a $U_{2,q+2}$-minor.<\/p>\n This is certainly an important theorem – it says that if $M$ has too many elements to be a projective geometry over GF$(q)$, then $M$ has a rank-$2$ minor with the same property. However, if $n$ is large then this is somewhat unsatisfying, as the $U_{2,q+2}$-minor has constant size, and does not really ‘explain’ why $M$ is so dense. We would like a similar theorem that, instead of finding a $U_{2,q+2}$-minor, finds an unavoidable minor whose size grows with $n$.<\/p>\n What should such a minor be? That is, what are the large matroids that are ‘canonically’ denser than a projective geometry over GF$(q)$?<\/p>\n The first example is easy; rank-$2$ matroids can contain arbitrarily many elements, so the uniform matroid $U_{2,t}$ for some large $t$ must appear as an outcome. The direct sum of $U_{2,q^n}$ and $U_{n-2,n-2}$, for example, is a rank-$n$ matroid with more elements than $\\PG(n-1,q)$, and essentially no more interesting structure.<\/p>\n Another matroid denser than $\\PG(n-1,q)$ is simply a projective geometry $\\PG(t-1,q’)$ over finite field GF$(q’)$.with $q’ > q$. This is our second outcome.<\/p>\n The next two outcomes are more interesting. An obvious way to construct a matroid denser than $\\PG(n-1,q)$ is to perform a single-element extension. By modularity, every extension of\u00a0$\\PG(n-1,q)$\u00a0consists of adding a point freely to some flat $F$. The smallest simple case is where $F$\u00a0is a line: we write $\\PG^{\\mathrm{line}}(n-1,q)$ for the matroid formed by adding a point freely to a line of $\\PG(n-1,q)$. The ‘largest’ case is when $F$ is the entire ground set, so the extension is free. We write $\\PG^{\\mathrm{free}}(n-1,q)$ for this matroid. The matroids $\\PG^{\\mathrm{line}}(m-1,q)$ and $\\PG^{\\mathrm{free}}(n-1,q)$ coincide for $n = m = 2$, but are not minors of eachother for any $m,n \\ge 3$; they will thus occur as separate outcomes in our theorem. On the other hand, it is not hard to show that any simple extension of $\\PG(2n-1,q)$ has one of $\\PG^{\\mathrm{line}}(n-1,q)$ or $\\PG^{\\mathrm{free}}(n-1,q)$ as a minor; thus, no further single-element extensions are needed as outcomes. Here is the theorem.<\/p>\n Theorem 1 [2]:\u00a0<\/strong>For every prime power $q$ and all $t \\ge 3$, there exists $n \\in \\mathbb{Z}$ so that, if $M$ is a simple matroid with rank at least $n$ and $|M| > \\frac{q^{r(M)}-1}{q-1}$, then $M$ has a minor isomorphic to one of the following:<\/p>\n Like in the quadratic case, we can apply this theorem to identify minor-closed classes that grow no faster than the GF$(q)$-representable matroids. For instance, if $q’$ is the next prime power after $q$, and $\\ell$ is an integer so that $q \\le \\ell < q’$, then, for $t = \\ell+2$, all four of the above minors can be shown to contain a $U_{2,\\ell}$-minor. We thus have the following:<\/p>\n Corollary 1: <\/b>Let\u00a0$q$ and $q’$ be consecutive prime powers and $\\ell$ be an integer so that $q \\le \\ell < q’$. If $M$ is\u00a0a simple matroid with sufficiently large rank and no $U_{2, \\ell+2}$-minor, then $|M| \\le \\frac{q^{r(M)}-1}{q-1}$.<\/p>\n Spikes and Swirls<\/strong><\/p>\n Let $X = \\{x_1,\\dotsc,x_t\\}$ and $Y = \\{y_1, \\dotsc, y_t\\}$ be disjoint $t$-element sets. A rank-$t$\u00a0free spike\u00a0<\/em>is the matroid $\\Lambda_t$ with ground set $X \\cup Y$ whose non-spanning circuits are exactly the four-element sets of the form $\\{x_i,x_j,y_i,y_j\\}$ for $i \u00a0\\ne j$. The rank-$t$\u00a0free swirl <\/em>is the matroid $\\Delta_t$ with ground set $X \\cup Y$ whose non-spanning circuits are exactly the four-element sets $\\{x_i,x_{i+1},y_i,y_{i+1}\\}$, where addition is modulo $t$.\u00a0\u00a0Both free spikes and free swirls arise as pathologies in matroid representation theory.<\/p>\n Let $q \\ge 3$ be a prime power and let $t \\ge 3$. One can show (see [1]) that<\/p>\n Using this, one can hunt for free spikes and swirls in the list of unavoidable minors in Theorem 1. There is a bit of case analysis to see what theorems fall out, but we get a few different corollaries that give upper bounds on the densities of matroids with out line-, spike-, and\/or swirl-minors. All of the upper bounds in these corollaries are the densities of projective geometries, and are best-possible because the geometries themselves are tight examples.<\/p>\n Corollary 2:\u00a0<\/strong>Let $\\ell \\ge 2$ and $t \\ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\\ell+2}$-minor and no $\\Lambda_t$-minor, then $|M| \\le \\frac{p^{r(M)}-1}{p-1}$.<\/p>\n Corollary 3:\u00a0<\/strong>Let $\\ell \\ge 3$ and $t \\ge 3$ be integers. If $M$ is a matroid of sufficiently large rank with no $U_{2,\\ell+2}$-minor, no $\\Lambda_t$-minor and no $\\Delta_t$-minor, then $|M| \\le \\tfrac{1}{2}(3^{r(M)}-1)$.<\/p>\n The next corollary mostly tells you how dense a matroid can be if you exclude a line and a free swirl has a minor. However, it weirdly fails to apply to some $\\ell$ because of the oddness of representation of free swirls. The only fields that can’t represent free swirls\u00a0are are the ones of order $2^p$, where $2^p-1$ is prime. A prime of the form $2^p-1$ for another prime $p$, like $2^3 – 1 = 7, 2^5 – 1 = 31$ or $2^7 – 1 = 127$, is a\u00a0Mersenne prime;\u00a0<\/em>it is not even known if there are infinitely many.<\/p>\n Corollary 4:\u00a0<\/strong>Let $2^p-1$ and $2^{p’}-1$ be consecutive Mersenne primes, and let $k$ and $\\ell$ be integers so that $2^p \\le \\ell < \\min(2^{2p} + 2^p, 2^{p’})$ and $k \\ge \\max(3,2^p-2)$. If $M$ is a simple matroid of sufficiently large rank with no $U_{2,\\ell+2}$ or $\\Delta_k$-minor, then $|M| \\le \\frac{2^{pr(M)}-1}{2^p-1}$.<\/p>\n This fails to apply to some $\\ell$, but only if $\\ell$ is (roughly) greater than the square of a Mersenne prime but smaller than the next Mersenne primes. The first pair of Mersenne primes this far apart are $2^{127}-1$ and $2^{521}-1$, so for some $\\ell$ around this size, the above corollary says nothing. The actual fact of the matter depends on the very poorly understood distribution of the Mersenne primes, so I don’t expect much improvement there in the near future.<\/p>\n Thanks, and see you next time!<\/p>\n [1] J Geelen, J.G. Oxley, D. Vertigan, G. Whittle, Totally free expansions of matroids, J. Combin. Theory. Ser. B 84 (2002), 130-179.<\/p>\n [2] P. Nelson, \u00a0Matroids denser than a projective geometry, to appear, SIAM Journal on Discrete Mathematics.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" $\\newcommand{\\PG}{\\text{PG}}$ Denser than a Geometry Hello everyone. In my\u00a0last post,\u00a0I discussed an unavoidable minor theorem for large matroids of density greater than $\\binom{n+1}{2}$, which as a consequence characterised exactly the minor-closed classes of matroids that grow like the the graphic … Continue reading \n
\n