Rota’s Conjecture proved!

Posted on August 22, 2013 by Stefan van Zwam

The Twitterverse has been abuzz recently with the news that Rota’s Conjecture has been proved by Jim Geelen, Bert Gerards, and Geoff Whittle! See press releases here and here (with an interview of Geoff at the bottom) and here. This news was known, by word of mouth, to people in the community close to the sources for a while, but let me take this opportunity to try to explain to the non-experts what this conjecture is all about. I will build up in a few steps from a small class of objects to bigger and bigger classes. For the experts, this survey by Geelen, Gerards, and Whittle might be better reading. Continue reading →

Growth Rates I

Posted on August 20, 2013 by Peter Nelson

$\newcommand{\cG}{\mathcal{G}}$ $\newcommand{\cM}{\mathcal{M}}$ $\newcommand{\elem}{\varepsilon}$ $\newcommand{\con}{/}$ $\newcommand{\del}{\!\backslash\!}$

I’m going to give what is hopefully a less frenetically paced exposition of what many readers have probably seen me talk about more that once – the growth rates of matroids in minor-closed classes. I’ll try to cover things from the ground up in order to motivate the subject, as well as provide some short proofs. The traditional starting point, from which I won’t deviate, is a theorem of Mader [Mader67]:

Theorem 1. If $\mathcal{G}$ is a proper minor-closed class of graphs, then $|E(G)| \le c_{\mathcal{G}}|V(G)|$ for each simple graph $G$ in $\cG$.

Here, `proper’ means that $\cG$ isn’t the class of all graphs, and $c_{\mathcal{G}}$ is a positive real constant depending only on $\cG$. Note that this theorem fails if we allow $\mathcal{G}$ to be the class of all graphs; the complete graph $K_t$ has $\binom{t}{2}$ edges and $t$ vertices, and the ratio $\binom{t}{2}$ is not bounded above by any linear function of $t$. With this fact in mind, what is interesting is the dichotomy; either $\cG$ is the class of all graphs and the densest simple graphs in $\mathcal{G}$ (the cliques) have a number of edges that is quadratic in their number of vertices, or $\mathcal{G}$ is not the class of all graphs and this bound is linear. This is not just a curiosity – we know now that it reflects the structure proved by Robertson and Seymour in the graph minors structure theorem – the graphs in a proper minor-closed class are at most linearly dense because they are `almost’ embeddable on a fixed surface. Of course we didn’t know this in 1967, so it presented a question rather than a corroboration.

Moving on to matroids, we first define some convenient notation. For a matroid $M$, we write $\elem(M)$ for $|\mathrm{si}(M)|$ (equivalently the number of rank-$1$ flats of $M$); this stops us having to awkwardly talk about simple matroids all the time. For a minor-closed class $\cM$, we use $h_{\cM}(n)$ to denote the function whose value at an integer $n$ is the maximum of $\elem(M)$ over all matroids $M \in \cM$ whose rank is at most $n$. Some people call this the size function but I’ll call in the growth rate function. We allow $h_{\cM}(n) = \infty$ – indeed any class that contains $U_{2,k}$ for all $k$ will satisfy this for all $n \ge 2$. In the interesting cases this function is monotonely increasing without bound. For example, for the class $\cM$ of graphic matroids has growth rate function $h_{\cM}(n) = \binom{n+1}{2}$, and by Theorem 1 above, all of its proper subclasses have growth rate function at most linear in $n$.

The next few theorems will combine to divide minor-closed classes of matroids into four types, just as Theorem 1 divides classes of graphs into two. These theorems all concern `dichotomies’ in growth rate functions. The first, due to Kung [Kung91] distinguishes classes with finite growth rate functions from those with infinite growth rate function. We’ll even prove it, since the proof is so nice.

Theorem 2. If $\cM$ is a minor-closed class of matroids, then either

$h_{\cM}(n) = \infty$ for all $n \ge 2$, or
there is some $\ell \ge 2$ such that $U_{2,\ell+2} \notin \cM$ and $h_{\cM}(n) \le \frac{\ell^n-1}{\ell-1}$ for all $n$.

Proof: If $U_{2,\ell+2} \in \cM$ for all $\ell \ge 2$ then the first outcome holds, so we may assume that $U_{2,\ell+2} \notin \cM$ for some $\ell \ge 2$, and will show that $\elem(M) \le \frac{\ell^r-1}{\ell-1}$ for each integer $r$. Let $M \in \cM$ be a rank-$r$ matroid and $e$ be a nonloop of $M$. Inductively we may assume that $\elem(M \con e) \le \frac{\ell^{r-1}-1}{\ell-1}$, and we know $M$ has $\elem(M \con e)$ lines containing $e$. Since $M$ has no $U_{2,\ell+2}$-minor, each of these lines has at most $\ell$ points other than $e$, so $\elem(M) \le \ell \elem(M \con e) + 1 \le \ell\frac{\ell^{r-1}-1}{\ell-1}+ 1 \le \frac{\ell^r-1}{\ell-1}$, as required.

This theorem tells us that there is no minor-closed class with finite growth rate function greater than exponential in $n$, and cleanly divides growth rate functions into the infinite and the finite. In fact, there is much more to the story than this; we’ll finish by stating the theorem that will be the focus of my next post. This theorem was conjectured by Kung [Kung91] and stated in [GKW09] as a consequence of various theorems of Geelen, Kabell, Kung and Whittle.

Growth Rate Theorem. If $\cM$ is a minor-closed class of matroids, then either

$h_{\cM}(n) \le c_{\cM}n$ for all $n$,
$\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$ and $\cM$ contains all graphic matroids,
there is a prime power $q$ such that $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n$ and $\cM$ contains all GF$(q)$-representable matroids, or
$h_{\cM}(n) = \infty$ for all $n \ge 2$ and $\cM$ contains all simple rank-$2$ matroids.

Again $c_{\cM}$ is always a real constant depending only on $\cM$. In other words, up to a constant, there are just four possible qualitative behaviours for growth rate functions: linear, quadratic, exponential and infinite. This is dramatic behaviour and deserves more consideration. See you next time!

References

[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.
[Kung91] J. P. S. Kung. Extremal matroid theory. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 21–61. Amer. Math. Soc., Providence, RI, 1993.
[Mader67] W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Mathematische Annalen, 174:265–268, 1967. 10.1007/BF01364272.

Connectivity-related matroids

Posted on August 12, 2013 by Stefan van Zwam

In this post I’d like to discuss three families of matroids that arise in the study of connectivity. The first is well-known and extensively studied; the other two are more recent and appear as lemmas buried in papers with a different main focus. I will focus on a few open problems for each of these families.

1. Gammoids

The matroid $Q_6$, represented as geometry (right) and as gammoid (left)

For our first example, consider a directed graph $D = (V,A)$. Let $S, T \subseteq V$, and define a function $\rho$ mapping subsets of $S$ to integers, defined as

$\rho(X) = $ the maximum number of vertex-disjoint $X-T$ paths.

Theorem 1. The function $\rho$ is the rank function of a matroid on ground set $S$.

We say that a matroid $M$ is a gammoid if there exist a digraph $D$ and sets $S, T$ such that the matroid defined above is isomorphic to $M$. If $S = V$ then the gammoid is said to be strict.

There is a beautiful and unexpected proof of this result, due to Ingleton and Piff [IP73], which takes a detour through transversal matroids. It reveals a beautiful duality relation between Menger’s and König’s theorems from graph theory. The proof can be found in Section 2.4 of [Oxl11]. A consequence is:

Theorem 2. The set of gammoids is precisely the set of transversal matroids and their contractions.

The question of representability of transversal matroids, and therefore of gammoids, has received some attention. Piff and Welsh first proved that they are representable over any sufficiently large field, and Atkin [Atk72] gave the following explicit bound:

Theorem 3. Let $M$ be a transversal matroid of rank $r$ on $n$ elements. Then $M$ is representable over every field $\mathbb{F}$ satisfying

$$ |\mathbb{F}| \geq n + {n \choose r – 1} $$

One problem that, to my knowledge, hasn’t received attention so far is the following:

Problem 1. Find a good upper bound on the size of the digraph needed to represent a gammoid. Concretely, find a function $f: \mathbb{N} \to \mathbb{N}$ such that every gammoid on $n$ elements can be realized in a digraph with at most $f(n)$ vertices.

In the variant where $D$ is an undirected graph, a result by Tony Huynh and me [HZ13] can be used to derive some function $f$, but it’s really bad: a tower of twos, i.e.

$$2^{2^{2^\cdots}},$$

of height $2^{n}$.

2. Linkage matroids

Tutte’s Linking Theorem is a generalization of Menger’s Theorem to arbitrary matroids. The two ingredients are the connectivity function of a matroid:

$$ \lambda(X) = r(X) + r(E – X) – r(M) $$

and Tutte’s connectivity function between $S$ and $T$:

$$ \kappa(S,T) = \min \{ \lambda(X) : S \subseteq X \subseteq E – T \}.$$

Tutte’s Linking Theorem [Tut65] is the following:

Theorem 4. The function $\kappa(S,T)$ equals the maximum, over all minors $N$ of $M$ with $E(N) = S \cup T$, of $\lambda_N(S)$.

See Section 8.5 of [Oxl11] for more on this important theorem. It was observed by Geelen, Gerards, and Whittle [GGW07, Lemma 4.6] that Tutte’s connectivity function can be used to define a matroid in much the same way as a gammoid:

Theorem 5. Let $T$ be a set of elements of the matroid $M$ with ground set $E$. For each $X \subseteq E – T$, define

$$\psi(X) = \kappa(X, T).$$

Then $\psi$ is the rank function of a matroid on E – T.

Proof. We verify the rank axioms. Monotonicity and unit increase are easily verified. To show submodularity, we use the fact that $\lambda$ is submodular. Pick $X_1, X_2 \subseteq E – T$. By definition there exist sets $A_1, A_2$ such that $X_i \subseteq A_i \subseteq E – T$ and $\lambda(A_i) = \kappa(X_i, T)$. Note that $X_1\cap X_2 \subseteq A_1\cap A_2$ and $X_1\cup X_2 \subseteq A_1\cup A_2$, so $\kappa(X_1\cap X_2, T) \leq \lambda(A_1\cap A_2)$ and $\kappa(X_1\cup X_2, T) \leq \lambda(A_1\cup A_2)$. Now

$$ \psi(X_1) + \psi(X_2) = \lambda(A_1) + \lambda(A_2) \geq \lambda(A_1\cap A_2) + \lambda(A_1\cup A_2) \geq \\
\kappa(X_1\cap X_2, T) + \kappa(X_1\cup X_2, T) = \psi(X_1\cap X_2) + \psi(X_1\cup X_2). \square$$

To the best of my knowledge, not much more is known about these matroids (let’s call them connectivity matroids for now). I’m listing one easy consequence and three problems:

Proposition 1. The connectivity matroid of $M^*$ with respect to $T$ equals the connectivity matroid of $M$ with respect to $T$.

Problem 2. Characterize the contractions of connectivity matroids.

Problem 3. Characterize the duals of connectivity matroids.

Problem 4. Is each connectivity matroid representable over every sufficiently large field?

3. Tangle matroids

For our third family of matroids we abstract away from the subset $T$ that appeared in the previous two. Instead, we go for a more general notion of “where the interesting part of the matroid lies”, called a tangle.

Definition 1. Let $M$ be a matroid, $k$ an integer, and $\mathcal{T}$ a collection of subsets of $M$ such that

For each $X \in \mathcal{T}$, $\lambda(X) < k$;
For each separation $(X,Y)$ with $\lambda(X) < k$, either $X$ or $Y$ is in $\mathcal{T}$;
If $X, Y, Z \in \mathcal{T}$ then $X\cup Y \cup Z \neq E(M)$;
For each element $e$, $E(M) – \{e\} \not\in \mathcal{T}$.

Then $\mathcal{T}$ is a tangle of $M$ of order $k$.

The members of $\mathcal{T}$ are called small. Intuitively, for each small set $X$, the important part of the matroid (such as a big grid minor or big projective geometry minor) is for the most part contained in the complement of $X$. Note that a matroid can have many different tangles (just as it can have many different grid minors).

Now we can define the tangle matroid, introduced by Geelen, Gerards, Robertson and Whittle [GGRW06, Lemma 4.3]:

Theorem 6. Let $M$ be a matroid, $\mathcal{T}$ a tangle of $M$ of order $k$, and define a function $\phi$ by

$$\phi(X) = \begin{cases}
\min \{ \lambda(Y) : X \subseteq Y \text{ and } Y \in \mathcal{T} \} & \text{if } Y \text{ exists;}\\
k & \text{otherwise.}
\end{cases}$$

Then $\phi$ is the rank function of a matroid on $E(M)$ called the tangle matroid and denoted by $M(\mathcal{T})$.

The proof is very similar to that of Theorem 5.

The tangle matroid is a very useful object in the study of tangles, since it summarizes connectivity information in a geometric manner: 3-separations correspond to lines, 4-separations to planes, and so on. One nagging problem is the following:

Problem 5. Let $M$ be a matroid representable over a (finite) field $\mathbb{F}$, and let $\mathcal{T}$ be a tangle of $M$. Is it true that $M(\mathcal{T})$ is representable over an extension field of $\mathbb{F}$?

It is problematic that $M(\mathcal{T})$ can have arbitrarily large projective geometry minors, so it won’t be representable over any sufficiently large field. Hopefully it is still sufficient to go to a sufficiently large extension field.

References

[Atk72] A. O. L. Atkin, Remark on a paper of Piff and Welsh, J. Combinatorial Theory Ser. B 13 (1972), 179–182.

[GGRW06] J.Geelen,B.Gerards,N.Robertson,andG.Whittle, Obstructions to branch-decomposition of matroids, J. Combin. Theory Ser. B 96 (2006), no. 4, 560–570.

[GGW07] Jim Geelen, Bert Gerards, and Geoff Whittle, Excluding a planar graph from GF(q)-representable matroids, J. Combin. Theory Ser. B 97 (2007), no. 6, 971–998.

[HZ13] T. Huynh and S. H. M. van Zwam, Intertwining connectivities for representable matroids, Submitted. Preprint at arXiv:1304.6488.

[IP73] A. W. Ingleton and M. J. Piff, Gammoids and transversal matroids, J. Combinatorial Theory Ser. B 15 (1973), 51–68.

[Oxl11] J. Oxley, Matroid theory, second edition, Oxford University Press, 2011.

[Tut65] W. T. Tutte, Menger’s theorem for matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 49–53.

Matroids at La Vacquerie – 2013

Posted on August 6, 2013 by Dillon Mayhew

Stefan and I (and others) have been idly talking about putting together a matroid blog for some time, and it was at a workshop of Henry Crapo’s that we finally put the plan into action, so I thought that I would devote my inaugural post to writing a little about the meeting.

Henry featured prominently in the early history of matroid theory, and his name will be familiar to those acquainted with matroid enumeration. He, along with coauthors John Blackburn and Denis Higgs, was the first to use a computer to count and catalogue matroids. Their article, published in 1973, describes a catalogue of all 1095 simple matroids with up to eight points. Incidentally, my proudest mathematical possession, given to me by Dominic Welsh, is a copy of the technical report by Henry and his coauthors. The cover is a thing of intricate beauty:

In case you can’t see, this is actually a piece of text. It says ‘The Henry Crapo Group presents the incredible catalogue of 8 point geometries: see single element extensions grow before your eyes’.

Henry now lives in the small French village of La Vacquerie-et-Saint-Martin-de-Castries, about an hour’s drive north of Montpellier. His house is a large villa, which he has fitted out with all the equipment needed for a small mathematics workshop. In the last week of June, about a dozen matroid theorists descended. As was the case in 2011, when he held his last meeting, Henry delved deep into his wine cellar, and brought in his friend Samuel to provide two home-cooked meals a day. When describing this arrangement to friends and family, it’s hard not to detect a note of envy (resentment, even?). What they don’t realise is that, although we may be averaging ten courses of food and one bottle of wine per person per day, we manage to get a fair bit of mathematics done.

In between picnics, of course.

Now that I reread Gordon Royle’s description of Henry’s 2011 meeting, I see he had the same experience that we did while driving in central Montpellier. Online maps seem to ignore one-way markings (which are ubiquitous), and also indicate the existence of many streets that, in the off-line world, are solely the reserve of trams. We had a merry time getting to our hotel. Stick to public transport is my recommendation.

One of the major themes of the 2013 meeting was the ongoing sage-matroids project, appropriately enough, given Henry’s position in the history of matroid computation. The project was initiated after a meeting in Wellington in 2010, and has been steaming along since. Rudi Pendavingh and Stefan van Zwam (with contributions from Gordon Royle and Michael Welsh) have done a massive amount of work on an addition to the open-source mathematics package sage. The package is now very useable; I regularly rely on it in my research. No doubt Stefan will have more to say about the package in a future post.

I will attach slides from some of the talks at the end of this post, but let me mention one seminar that quite nicely relates to Henry’s role in the development of matroid theory. Rudi Pendavingh, alongside Nikhil Bansal and Jorn van der Pol, has been working on improving bounds on the number of matroids with a given number of points. They have produced a significant decrease in the best upper bound, so that it now quite closely resembles the best known lower bound (although, unfortunately, we have to apply logarithms twice in order to really see the resemblance!). The lower bound is due to Knuth, and provides a lower bound on the number of matroids by explicitly finding families of sparse paving matroids. Thus Rudi and his coauthors have provided some more circumstantial evidence supporting the conjecture that sparse paving matroids dominate the collection of all matroids. This conjecture seems to date back to Dominic Welsh, and was inspired by… the catalogue produced by Blackburn, Crapo, and Higgs!