Jim Geelen

A generalization of the Grid Theorem

A graph has tree-width at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums. We refine this definition by, for each non-negative integer $θ$ , defining the $θ$ -tree-width of a graph to be at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums on cliques of size less than $θ$ . We find the unavoidable minors for the graphs with large $θ$ -tree-width and we obtain Robertson and Seymour's Grid Theorem as a corollary.

Explicit bounds for graph minors

Let $Σ$ be a surface with boundary $b(Σ)$ , $\mathcal{L}$ be a collection of $k$ disjoint $b(Σ)$ -paths in $Σ$ , and $P$ be a non-separating $b(Σ)$ -path in $Σ$ . We prove that there is a homeomorphism $ϕ: Σ\to Σ$ that fixes each point of $b(Σ)$ and such that $ϕ(\mathcal{L})$ meets $P$ at most $2k$ times. With this theorem, we derive explicit constants in the graph minor algorithms of Robertson and Seymour. We reprove a result concerning redundant vertices for graphs on surfaces, but with explicit bounds. That is, we prove that there exists a computable integer $t:=t(Σ,k)$ such that if $v$ is a ' $t$ -protected' vertex in a surface $Σ$ , then $v$ is redundant with respect to any $k$ -linkage.

Matroids denser than a clique

The growth-rate function for a minor-closed class $\mathcal{M}$ of matroids is the function $h$ where, for each non-negative integer $r$ , $h(r)$ is the maximum number of elements of a simple matroid in $\mathcal{M}$ with rank at most $r$ . The Growth-Rate Theorem of Geelen, Kabell, Kung, and Whittle shows, essentially, that the growth-rate function is always either linear, quadratic, exponential, or infinite. Morover, if the growth-rate function is quadratic, then $h(r)\ge \binom{r+1}{2}$ , with the lower bound coming from the fact that such classes necessarily contain all graphic matroids. We characterise the classes that satisfy $h(r) = \binom{r+1}{2}$ for all sufficiently large $r$ .

The critical number of dense triangle-free binary matroids

We show that, for each real number $ε> 0$ there is an integer $c$ such that, if $M$ is a simple triangle-free binary matroid with $|M| \ge (\tfrac{1}{4} + ε) 2^{r(M)}$ , then $M$ has critical number at most $c$ . We also give a construction showing that no such result holds for any real number less than $\tfrac{1}{4}$ . This shows that the "critical threshold" for the triangle is $\tfrac 1 4$ . We extend the notion of critical threshold to every simple binary matroid $N$ and conjecture that, if $N$ has critical number $c\ge 3$ , then $N$ has critical threshold $1-i\cdot 2^{-c}$ for some $i\in \{2,3,4\}$ . We give some support for the conjecture by establishing lower bounds.

The structure of matroids with a spanning clique or projective geometry

Let $s,n \ge 2$ be integers. We give a qualitative structural description of every matroid $M$ that is spanned by a frame matroid of a complete graph and has no $U_{s,2s}$ -minor and no rank- $n$ projective geometry minor, showing that every such matroid is `close' to a frame matroid. We also give a similar description of every matroid $M$ with a spanning projective geometry over a field GF $(q)$ as a restriction and with no $U_{s,2s}$ -minor and no PG $(n,q')$ -minor for any $q' > q$ , showing that such an $M$ is `close' to a GF $(q)$ -representable matroid.

Computing girth and cogirth in perturbed graphic matroids

We give polynomial-time randomized algorithms for computing the girth and the cogirth of binary matroids that are low-rank perturbations of graphic matroids.

On Rota's Conjecture and nested separations in matroids

We prove that for each finite field $\mathbb F$ and integer $k\in \mathbb Z$ there exists $n\in \mathbb Z$ such that no excluded minor for the class of $\mathbb F$ -representable matroids has $n$ nested $k$ -separations.

On the structure of dense triangle-free binary matroids

We prove, by means of an exact structural description, that every simple triangle-free binary matroid $M$ with $|M| > \tfrac{33}{128}2^{r(M)}$ has critical number at most $2$ .

Representability of matroids with a large projective geometry minor

We prove that for each prime power $q$ there is an integer $n$ such that if $M$ is a $3$ -connected, representable matroid with a PG $(n-1,q)$ -minor and no $U_{2,q^2+1}$ -minor, then $M$ is representable over GF $(q)$ . We also show that for $\ell >= 2$ , if $M$ is a $3$ -connected, representable matroid of sufficiently high rank with no $U_{2,\ell+2}$ -minor and $|E(M)| \geq (4\ell)^{r(M)/2}$ , then $M$ is representable over a field of order at most $\ell$ .

The Highly Connected Matroids in Minor-closed Classes

For any minor-closed class of matroids over a fixed finite field, we state an exact structural characterization for the sufficiently connected matroids in the class. We also state a number of conjectures that might be approachable using the structural characterization.

A geometric version of the Andrasfai-Erdos-Sos theorem

For each odd integer $k\ge 5$ , we prove that, if $M$ is a simple rank- $r$ binary matroid with no odd circuit of length less than $k$ and with $|M| > k 2^{r-k+1}$ , then $M$ is isomorphic to a restriction of the rank- $r$ binary affine geometry; this bound is tight for all $r\ge k-1$ . We use this to give a simpler proof of the following result of Govaerts and Storme: for each integer $n\ge 2$ , if $M$ is a simple rank- $r$ binary matroid with no $PG(n-1,2)$ -restriction and with $|M| > \left(1-\frac{11}{2^{n+2}}\right) 2^r$ , then $M$ has critical number at most $n-1$ . That result is a geometric analogue of a theorem of Andrasfai, Erdos, and Sos in extremal graph theory.

Matroid 3-connectivity and branch width

We prove that, for each nonnegative integer k and each matroid N, if M is a 3-connected matroid containing N as a minor, and the the branch width of M is sufficiently large, then there is a k-element subset X of E(M) such that one of M\X and M/X is 3-connected and contains N as a minor.

Odd circuits in dense binary matroids

We show that, for each real number $α> 0$ and odd integer $k\ge 5$ there is an integer $c$ such that, if $M$ is a simple binary matroid with $|M| \ge α2^{r(M)}$ and with no $k$ -element circuit, then $M$ has critical number at most $c$ . The result is an easy application of a regularity lemma for finite abelian groups due to Green.

The densest matroids in minor-closed classes with exponential growth rate

The $\mathit{growth\ rate\ function}$ for a nonempty minor-closed class of matroids $\mathcal{M}$ is the function $h_{\mathcal{M}}(n)$ whose value at an integer $n \ge 0$ is defined to be the maximum number of elements in a simple matroid in $\mathcal{M}$ of rank at most $n$ . Geelen, Kabell, Kung and Whittle showed that, whenever $h_{\mathcal{M}}(2)$ is finite, the function $h_{\mathcal{M}}$ grows linearly, quadratically or exponentially in $n$ (with base equal to a prime power $q$ ), up to a constant factor. We prove that in the exponential case, there are nonnegative integers $k$ and $d \le \tfrac{q^{2k}-1}{q-1}$ such that $h_{\mathcal{M}}(n) = \frac{q^{n+k}-1}{q-1} - qd$ for all sufficiently large $n$ , and we characterise which matroids attain the growth rate function for large $n$ . We also show that if $\mathcal{M}$ is specified in a certain `natural' way (by intersections of classes of matroids representable over different finite fields and/or by excluding a finite set of minors), then the constants $k$ and $d$ , as well as the point that `sufficiently large' begins to apply to $n$ , can be determined by a finite computation.

preprint2013arXiv

Representation of matroids with a modular plane

We prove that if M is a vertically 4-connected matroid with a modular flat X of rank at least three, then every representation of M | X over a finite field F extends to a unique F-representation of M. A corollary is that when F has order q, any vertically 4-connected matroid with a PG(2, F)-restriction is either F-representable or has a U_{2, q^2+1}-minor. We also show that no excluded minor for the class of F-representable matroids has a PG(2, F)-restriction.

preprint2013arXiv

The number of lines in a matroid with no $U_{2,n}$ -minor

We show that, if $q$ is a prime power at most 5, then every rank- $r$ matroid with no $U_{2,q+2}$ -minor has no more lines than a rank- $r$ projective geometry over GF $(q)$ . We also give examples showing that for every other prime power this bound does not hold.

preprint2012arXiv

A Density Hales-Jewett Theorem for matroids

We show that, if $α> 0$ is a real number, $n \ge 2$ and $\ell \ge 2$ are integers, and $q$ is a prime power, then every simple matroid $M$ of sufficiently large rank, with no $U_{2,\ell}$ -minor, no rank- $n$ projective geometry minor over a larger field than $\GF(q)$, and satisfying $|M| \ge αq^{r(M)}$ , has a rank- $n$ affine geometry restriction over $\GF(q)$. This result can be viewed as an analogue of the Multidimensional Density Hales-Jewett Theorem for matroids.

preprint2012arXiv

An analogue of the Erdős-Stone theorem for finite geometries

For a set $G$ of points in $\PG(m-1,q)$, let $\ex_q(G;n)$, denote the maximum size of a collection of points in $\PG(n-1,q)$ not containing a copy of $G$ , up to projective equivalence. We show that \[\lim_{n\rightarrow \infty} \frac{\ex_q(G;n)}{|\PG(n-1,q)|} = 1-q^{1-c},\] where $c$ is the smallest integer such that there is a rank- $(m-c)$ flat in $\PG(m-1,q)$ that is disjoint from $G$ . The result is an elementary application of the density version of the Hales-Jewett Theorem.

preprint2012arXiv

Projective geometries in exponentially dense matroids. I

We show for each positive integer $a$ that, if $\cM$ is a minor-closed class of matroids not containing all rank- $(a+1)$ uniform matroids, then there exists an integer $n$ such that either every rank- $r$ matroid in $\cM$ can be covered by at most $r^n$ sets of rank at most $a$ , or $\cM$ contains the $\GF(q)$-representable matroids for some prime power $q$ , and every rank- $r$ matroid in $\cM$ can be covered by at most $r^nq^r$ sets of rank at most $a$ . This determines the maximum density of the matroids in $\cM$ up to a polynomial factor.

Certifying Non-representability of Matroids Over Prime Fields

It is proved that, for a prime number $p$ , showing that an $n$ -element matroid is not representable over $GF(p)$ requires only $O(n^2)$ rank evaluations.

Inequivalent Representations of Matroids over Prime Fields

It is proved that for each prime field $GF(p)$ , there is an integer $f(p)$ such that a 4-connected matroid has at most $f(p)$ inequivalent representations over $GF(p)$ . We also prove a stronger theorem that obtains the same conclusion for matroids satisfying a connectivity condition, intermediate between 3-connectivity and 4-connectivity that we term " $k$ -coherence". We obtain a variety of other results on inequivalent representations including the following curious one. For a prime power $q$ , let ${\mathcal R}(q)$ denote the set of matroids representable over all fields with at least $q$ elements. Then there are infinitely many Mersenne primes if and only if, for each prime power $q$ , there is an integer $m_q$ such that a 3-connected member of ${\mathcal R}(q)$ has at most $m_q$ inequivalent GF(7)-representations. The theorems on inequivalent representations of matroids are consequences of structural results that do not rely on representability. The bulk of this paper is devoted to proving such results.

On minor-closed classes of matroids with exponential growth rate

Let $\cM$ be a minor-closed class of matroids that does not contain arbitrarily long lines. The growth rate function, $h:\bN\rightarrow \bN$ of $\cM$ is given by $$h(n) = \max(|M|\, : \, M\in \cM, simple, rank-$n$).$$ The Growth Rate Theorem shows that there is an integer $c$ such that either: $h(n)\le c\, n$ , or ${n+1 \choose 2} \le h(n)\le c\, n^2$ , or there is a prime-power $q$ such that $\frac{q^n-1}{q-1} \le h(n) \le c\, q^n$ ; this separates classes into those of linear density, quadratic density, and base- $q$ exponential density. For classes of base- $q$ exponential density that contain no $(q^2+1)$ -point line, we prove that $h(n) =\frac{q^n-1}{q-1}$ for all sufficiently large $n$ . We also prove that, for classes of base- $q$ exponential density that contain no $(q^2+q+1)$ -point line, there exists $k\in\bN$ such that $h(n) = \frac{q^{n+k}-1}{q-1} - q\frac{q^{2k}-1}{q^2-1}$ for all sufficiently large $n$ .