Square
Math Building
Jim Geelen
$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\cM}{\mathcal{M}}$ $\newcommand{\bF}{\mathbb{F}}$

This section gives highlights of my recent research. I assume that the reader is familiar with standard terminology in matroid theory such as representation, minors, duality, and connectivity. Introductions to matroid theory can be found on Wikipedia or in the following survey paper by James Oxley.

This section is arranged by topic:

  1. Matroid Minors Project
  2. Rota's Conjecture
  3. Inequivalent representations of matroids
  4. Growth rates of minor-closed classes
  5. Extremal matroid theory (this page)


Extremal matroid theory

The Erdos-Posa Theorem for graphs says that, for each integer $k$ there exists an integer $t$ such that, any graph $G$ either has $k$ edge-disjoint circuits, or has a set $X$ of at most $t$ edges such that $G-X$ is acyclic. This can be restated as, for each integer $k$, if $M$ is a cographic matroid with sufficiently large rank, then $M$ has $k$ disjoint cocircuits.

We say that a class $\cM$ of matroids has the Erdos-Posa property if, for each integer $k$, if $M\in\cM$ has sufficiently large rank, then $M$ has $k$ disjoint cocircuits. Thus the class of cographic matroids has the Erdos-Posa property. It is easy to check that none of the following three classes has the Erdos-Posa property: the uniform matroids, the graphic matroids, and the bicircular matroids. In joint work with Kasper Kabell, we proved that, in some sense, these three classes are the only obstructions; this extends earlier results of this form that I had proved with Bert Gerards and Geoff Whittle.

Erdos-Posa Theorem for Matroid Cocircuits. For any minor-closed class $\cM$ of matroids either

  • $\cM$ has the Erdos-Posa property,
  • $\cM$ contains all uniform matroids,
  • $\cM$ contains all graphic matroids, or
  • $\cM$ contains all bicircular matroids.

Extensions of the Geometric Density Hales-Jewett Theorem

The Density Hales-Jewett Theorem, proved by Furstenberg and Katznelson in 1991, is one of the most celebrated results in Ramsey Theory. The following geometric version, which was also proved by Furstenberg and Katznelson, pre-dates the Density Hales-Jewett Theorem by $6$ years. The gist of the result is that, if we take a fixed fraction of all points in a sufficiently large projective geometry, the chosen points will contain a copy of any fixed affine geometry.

Geometric Density Hales-Jewett Theorem. Let $\bF$ be a finite field of order $q$, let $m$ be an integer, and let $\alpha>0$ be a real number. Then, for any sufficiently large integer $n$, if $M$ is a simple rank-$n$ $\bF$-representable matroid with $|M|> \alpha q^n$, then $M$ has an AG$(m-1,\bF)$-restriction.

In joint work with Peter Nelson, we have generalized the Geometric Density Hales-Jewett Theorem in two fundamental ways. In the first result we extend it from the class of $\bF$-representable matroids to any base-$q$ exponentially dense class.

Theorem 1. Let $\cM$ be a base-$q$ exponentially-dense minor-closed class of matroids, let $m$ be an integer, and let $\alpha>0$ be a real number. Then, for any sufficiently large integer $n$, if $M$ is a simple rank-$n$ matroid in $\cM$ with $|M|> \alpha q^n$, then $M$ has an AG$(m-1,\bF)$-restriction.

The second result is even more striking; it is an analogue of the Erdos-Stone Theorem for graphs. Let $\bF$ be a finite field of order $q$. For a simple $\bF$-representable matroid $N$ and an integer $n$, we let $ex_q(N;n)$ denote the maximum number of elements in a simple rank-$n$ matroid that does not contain an $N$-restriction. The result shows that the extremal behaviour of $ex_q(N;n)$ is controlled by the "critical exponent" of $N$.

The critical exponent of $N$ is the minimum $c$ such that there is a partition $(X_1,\ldots,X_c)$ of $E(N)$ such that each $N|X_i$ is a restriction of an affine geometry over $\bF$.

Theorem 2. Let $\bF$ be a finite field of order $q$ and let $N$ be a simple $\bF$-representable matroid with critical exponent $c>0$, then $$ \lim_{n\rightarrow \infty} \frac{ ex_q(N;n) }{|PG(n-1,q)|} = 1-q^{1-c} . $$

Note that, when $c=1$ the right hand side is $0$; this special case is the Geometric Density Hales-Jewett Theorem.

Combinatorics and Optimization
University of Waterloo