$\newcommand{\mcsigned}{\mathcal{G}^{\mathrm{sg}}}
\newcommand{\mcevencycle}{\mathcal{G}^{\mathrm{ec}}}
\newcommand{\mcfree}{\mathcal{G}^{\mathrm{tr}}}$
Hi everyone, happy new year and sorry for my recent absence/lateness!

Today I am going to say some things about growth rates of minor-closed classes, but in more concrete cases that I’ve been writing about previously. To recap on a definition that has come up many times on this blog, the growth rate function of a minor-closed class of matroids is the definition capturing the answer to a question that Joseph Kung called the ‘primary concern’ of extremal matroid theory: given a minor-closed class $\mathcal{M}$ of matroids, what is the maximum number of elements that a simple rank-$r$ matroid in $\mathcal{M}$ can have? For each nonnegative integer $n$, the growth rate function for $\mathcal{M}$ at $n$ is defined as follows:

$h_{\mathcal{M}}(n) = \max\{|M|: M \in \mathcal{M} \text{ simple}, r(M) \le n\}$.

For instance, for the class $\mathcal{G}$ is the class of graphic matroids we have $h_{\mathcal{G}}(n) = \binom{n+1}{2}$. In fact, the growth rate theorem [GKW09] says that every minor-closed class of matroids with finite growth rate function either has growth rate function in $O(n)$, or contains the graphic matroids (and therefore has growth rate function at least $\binom{n+1}{2}$ for all $n$). Thus, the graphic matroids have the smallest possible growth rate function that is not just linear in $n$.

There are other classes of matroids with growth rate function exactly $\binom{n+1}{2}$ for all $n$, or for all but a few $n$. They necessarily contain the graphic matroids, but can be strictly larger. Several were mentioned in a post by Irene last year; they include the regular matroids, and the class $\mathrm{Ex}(\mathrm{AG}(3,2))$ of binary matroids with no $\mathrm{AG}(3,2)$-minor. The former result was shown by Heller [H57] and the latter by Kung et al [KMPR13]. Given this (and Irene asked a question along these lines in her post), it is natural to ask for a characterisation of exactly which classes of matroids grow like the graphic ones:

Problem 1: Characterise the minor-closed classes of matroids $\mathcal{M}$ that satisfy $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

or, more concretely, we could ask to characterise the minors whose exclusion gives such a class:

Problem 2: Let $\mathcal{O}$ be a finite set of simple matroids and let $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$ be the class of matroids with no minor in $\mathcal{O}$. Characterise when $\mathcal{M}$ satisfies $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all but finitely many $n$.

Nice Classes

This post will answer both these questions. Before I state the theorem that does this, I’ll give three examples of minor-closed classes that do grow faster than the graphic matroids.

• The class $\mcevencycle$ of even cycle matroids having a signed graph representation with a blocking pair (that is, a pair of vertices through which all negative cycles pass). This class contains only binary matroids and has growth rate function $\binom{n+2}{3}-3$.
• The class $\mcsigned$ of signed-graphic matroids having a signed graph representation with a vertex that is contained in every nonloop negative cycle. This class contains matroids representable over every field of odd order, and has growth rate function $\binom{n+2}{2}-2$
• The class $\mcfree$ that is the union of the class of graphic matroids and the class of truncations of graphic matroids. There is no finite field over which every matroid in this class is representable, and it has growth rate function $\binom{n+2}{2}$.

The superscripts stand for ‘even cycle’, ‘signed graphic’ and ‘truncation’ respectively.  These are three ‘nice’ classes of matroids that are a bit bigger than the graphic matroids, all arising from well-known classes and constructions. The following theorem resolves Problem 1, and will also be enough to resolve 2.

Theorem 1 [GN14]: Let $\mathcal{M}$ be a minor-closed class of matroids with growth rate function in $\Theta(n^2)$. Either

• $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$, or
• $\mathcal{M}$ contains one of $\mcevencycle$, $\mcsigned$, or $\mcfree$.

Note that this ‘or’ is really an ‘exclusive or’, since the latter outcome implies that $h_{\mathcal{M}}(n) \ge \binom{n+2}{2}-3$ for all $n \ge 4$ and therefore that the former outcome does not hold. This theorem gives a very nice answer for problem 1; the classes that grow like the graphic matroids are exactly those that do not contain any of three particular classes that are all too big.

To deal with Problem 2, we just need to understand which minors that $\mathcal{O}$ must contain in order that $\mathrm{Ex}(\mathcal{O})$ does not contain any of $\mcevencycle$, $\mcsigned$ or $\mcfree$. This is just saying that $\mathcal{O}$ should contain a matroid from each of these classes. The classes actually intersect, so a single matroid in $\mathcal{O}$ could serve a dual purpose. For $\mathrm{Ex}(\mathcal{O})$ to be quadratically dense, it is also necessary to have some rank-$2$ uniform matroid in $\mathcal{O}$ and no graphic matroid in $\mathcal{O}$. The answer to Problem 2 is therefore in the following corollary:

Corollary 1: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M} = \mathrm{Ex}(\mathcal{O})$, then the following two statements are equivalent:

1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
2. $\mathcal{M}$ contains a rank-$2$ uniform matroid, contains no graphic matroids, and contains a matroid from each of $\mcevencycle$, $\mcsigned$ and $\mcfree$.

This solves the problem in general. We can also obtain specialisations to particular fields. The binary case (that is, where $U_{2,4} \in \mathcal{O}$) says the following:

Corollary 2: If $\mathcal{O}$ is a finite set of simple matroids and $\mathcal{M}$ is the set of binary matroids with no minor in $\mathcal{O}$, then the following two statements are equivalent:

1. $h_{\mathcal{M}}(n) = \binom{n+1}{2}$ for all sufficiently large $n$.
2. $\mathcal{O}$ contains no graphic matroids, and contains a nongraphic matroid in $\mcevencycle$.

When $\mathcal{O} = \{\mathrm{AG}(3,2)\}$ we get (for large $n$) the aforementioned result of Kung et al. There is also a similar corollary for matroids over any fixed odd-order finite field, where $\mcevencycle$ is replaced by $\mcsigned$.

Future Work

Theorem 1 should just be the beginning of an effort to characterise quadratic growth rate functions completely. It would be really nice to answer the following question:

Problem 3: Which functions in $\Theta(n^2)$ can occur as growth rate functions?

It follows from Theorem 1 that any function strictly between $\binom{n+1}{2}$ and $\binom{n+2}{2}-3$ cannot. In general, a conjecture of Geelen, Gerards and Whittle [GGW14] suggests that all such functions are quadratic polynomials with half-integral leading coefficient. Matroid structure theory in [GGW14] should (with enough work) give the answer for classes over any fixed finite field, but I would love to know what can be done without appeals to structure theory, since we are probably a long way off full structure theorems for general matroids.

[H57] I. Heller, On linear systems with integral valued solutions, Pacific J. Math. 7 (1957), 1351-1364.

[GGW14] J. Geelen, B. Gerards and G. Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5102.

[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

[GN14] J. Geelen, P. Nelson, Matroids denser than a clique, arXiv:1409.0777

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, and G. Royle, Maximum size binary matroids with no AG(3,2)-minor are graphic, arXiv:1304.2448.

This year the ACCMCC (“short” for Australasian Conference in Combinatorial Mathematics and Combinatorial Computing) was organised by our own contributor Dillon Mayhew. This gave me the chance to go to beautiful Wellington to see excellent talks and hang out with many Australasian (and not) combinatorialists. Here’s a picture of most of the conference participants, which was taken by Michael Welsh and posted on the conference website.

Not only were there many talks focused on matroids, our favourite combinatorial objects were also mentioned in several other talks, a sign of the increasing popularity of matroid theory.

We had nine excellent plenary talks, starting Monday morning with Mike Atkinson, who talked about permutation patterns: permutations may be seen as a set of points in the plane, a setting which gives a natural order on permutations. Then one may look at classes of permutations that are downclosed under this partial order and study the minimal obstructions to membership of a class. One can start with a class and look for the minimal obstructions or start from minimal obstructions and determine the class. Does this sound familiar?

On Monday afternoon the plenary was by another of our bloggers, Stefan van Zwam. Stefan talked about partial fields in disguise, starting by introducing totally unimodular matrices and then moving on to generalisations of this idea (namely, dyadic, near regular, and golden ratio matrices). Stefan presented beautiful results, in terms of representability, excluded minors and decompositions, and then introduced some recent results on fragile matroids. It was a very pleasant tour of important results and open problems in the area.

The Tuesday morning plenary talk was on finite geometry. Simeon Ball talked about sets of lines in affine geometry. These sets of lines had restrictions on them: a Kakeya set of lines has the property that every line has a different direction, while a Bourgain set has few lines on any given plane. The speaker gave results on these types of sets and proofs using a combination of combinatorial methods and algebraic methods, in particular from algebraic geometry.

Tuesday afternoon we got to enjoy a talk by Andrew Thomason on hypergraph containers. These are a powerful tool in studying various combinatorial problems, such as counting $H$-free graphs, sparse arithmetic progressions and so on. The idea is that, instead of dealing with independent sets (i.e. sets of vertices not containing any hyperedge) in a hypergraph – of which there may be exponentially many – we consider these sets, aptly named containers, with the property that each independent set is contained in a container. An amazing theorem shows that in an $r$-uniform hypergraph we can find a relatively small collection of containers, each one not too large. The talk contained a proof of this result, using a prune and build algorithm.

The Wednesday session opened with Sergey Norine, who told us about a recent result on densities of graphs, an analogue of matroid growth rates. Using deep results from the Graph Minor Project, the speaker showed that the density of any minor-closed class of graphs is a rational number. This is proved by showing that one may obtain a sequence of graphs achieving the maximal density by gluing together smaller graphs. This is somewhat in line with the conjecture that the maximum sized matroids in a minor-closed class with linear growth rate may be constructed by sums of a finite set of small rank extremal examples.

Wednesday afternoon was dedicated to the conference excursion, so the next plenary talk was on Thursday morning, when Alice Devillers told us about buildings. This are complicated but very useful objects that were first defined and studied by Jacques Tits. We were given an example of buildings, arising from projective spaces, and then the classical definition, followed by a more modern combinatorial definition. Buildings are very much related to Coxeter groups and are a useful tool when working with algebraic groups.

The Thursday session opened with another matroid talk, by James Oxley. The first result presented in the talk was a chain theorem for internally 4-connected binary matroids. Tutte proved that if a matroid is 3-connected and is not a wheel or a whirl, then there it has an element whose deletion or contraction leaves the matroid 3-connected. Oxley presented the analogous result for internally 4-connected binary matroids. In this case the matroids playing the role of wheels are planar and Möbius triadic ladders and a specific 16 element matroid (the terrahawk). The theorem also involves more than one move, i.e. it is not sufficient to delete or contract one element at the time to maintain internal 4-connectivity, but up to three moves may be required. The second result of the talk was a splitter theorem for internally 4-connected binary matroids. Here some special moves are required to dispose of “bits” of ladders that create complications.

The conference closed on Friday 5 December, after two more excellent plenary talks. In the morning Jaroslav Nešetřil presented a notion of density in graphs that turns out to be extremely effective. Namely, he introduced the dichotomy between nowhere dense graphs and somewhere dense graphs. This dichotomy can be characterised using many invariants, such that independence number, chromatic number, and clique number to name a few.

The last plenary talk of the conference was delivered by Mark Wilson, who talked about multivariate generating functions. While univariate generating functions are well understood, many difficulties arise when dealing with multivariate ones. Hence the need to systematise the theory for of asymptotic coefficient extraction from multivariate generating functions.

I only discussed the plenary talks in this post, but there were lots of really interesting contributed talks as well. I’m certainly looking forward to the next edition of this conference, the 39th ACCMCC, at University of Queensland, 7-11 December 2015.

Guest Post by Rohan Kapadia. 

Two popular invariants in graph theory are the girth of graph (the size of its smallest cycle) and its edge-connectivity. Given a graph, both can be easily computed. In fact, if $e$ is an edge and $s$ and $t$ are its ends, then finding the shortest cycle or smallest edge-cut containing $e$ can be done by finding a shortest $s,t$-path or a minimum $s,t$-cut, both easy problems.

Can we generalize the problem of computing these invariants to matroids? Cycles and minimal edge-cuts in graphs correspond to circuits and cocircuits in their cycle matroids (as long as we count loops and pairs of parallel edges as cycles). So we know how to find a shortest circuit or cocircuit in a graphic matroid. Note that in the matroid world, these become just one problem, since computing the smallest size of a cocircuit is the same under duality as computing the girth of a matroid, the smallest size of a circuit.

In this post I will discuss computing the girth of a matroid. We will only consider binary matroids, since the problem is already intractable just for this class: Alexander Vardy [4] proved that it is NP-hard to compute the girth of a given binary matroid (he actually worked on an equivalent problem from coding theory, that of finding the minimum distance of a binary linear code).

But, we know that it is easy to compute the girth of two types of binary matroids, the graphic and cographic ones. Are there other subsets of the binary matroids where the problem is still tractable? The class of regular matroids is an obvious candidate to consider after the graphic and cographic. In fact, the regular matroid decomposition theorem of Paul Seymour says that any regular matroid can be built by repeated $1$-, $2$-, and $3$-sums of graphic matroids, cographic matroids, and one particular matroid called $R_{10}$. This means that for any regular matroid $M$, there is a tree $T$, each of whose vertices is either a graphic matroid, a cographic matroid, or a copy of $R_{10}$, and such that $M$ is built by $(\leq 3)$-sums from these smaller matroids, each sum corresponding to an edge of the tree. Computing the girth of regular matroids is easy if we have an algorithm to find such a tree. How to find it is beyond the scope of this post, but more information can be found in [3].

Now let’s see how to compute the girth of a regular matroid. It’s actually easier if we allow matroid elements to be weighted. If each element $e$ of a matroid $M$ has a non-negative weight $w(e)$, then we’ll say that the girth of $M$ is \[ \min\left\{\sum_{e \in C} w(e) : C \text{ is a circuit of } M\right\} . \] For graphic and cographic matroids, this introduces no difficulties since we can find minimum cuts and shortest paths even in weighted graphs.

Theorem 1. There is a polynomial-time algorithm to compute the girth of a given regular matroid $M$ with non-negative weights on its elements.

Proof. First, we need to get the tree $T$ mentioned above. If $T$ has one vertex, then $M$ is just graphic, cographic, or a copy of $R_{10}$, and the problem is easy. Otherwise, we pick any leaf of the tree, $v$. So $v$ corresponds to a matroid $M_1$ that is either graphic, cographic, or a copy of $R_{10}$. The tree $T – v$ corresponds to a regular matroid $M_2$, such that $M$ is a $(\leq 3)$-sum of $M_1$ and $M_2$. If $M$ is a $1$-sum of $M_1$ and $M_2$, then the girth of $M$ is the minimum of the girths of $M_1$ and $M_2$, so we can find it by induction.

Otherwise, suppose that $M$ is a $2$-sum of $M_1$ and $M_2$. Denote by $e$ the common element in $E(M_1)$ and $E(M_2)$. We give each element of $M_1$ and of $M_2$ the same weight as it had in $M$, and we give $e$ a weight of zero in $M_1$. We will assign the weight of $e$ in $M_2$ later. Since $M_1$ is either graphic, cographic, or a copy of $R_{10}$, we can find the following two things in polynomial time: the first is a minimum-weight circuit $C$ of $M_1 \backslash e$ and the second is a minimum-weight circuit $C’$ of $M_1$ containing $e$.

We now assign the value $\sum_{f \in C’} w(f)$ as the new weight of $e$ in $M_2$. It is not too hard to see that the girth of $M$ is the minimum of the weight of $C$ and the girth of $M_2$. We can therefore find it by induction.

The last case is when $M$ is a $3$-sum of $M_1$ and $M_2$. This is just a variant of the $2$-sum case but we need to find four circuits in $M_1$ instead of two; the details are omitted. $\square$

We have seen that computing girth is easy even in regular matroids, and the reason was that we can reduce them to graphic and cographic matroids. What about other classes of binary matroids? In an earlier entry on this blog, Peter Nelson talked about a theorem announced by Jim Geelen, Bert Gerards and Geoff Whittle [2] which gives a decomposition of binary matroids in any proper minor-closed class similar to that given by the decomposition theorem for regular matroids. The pieces in this decomposition are actually not that different from graphic and cographic matroids.

If $N$ is a binary matroid and $A$ is a matrix such that $N = M(A)$, then a rank-($\leq t$) perturbation of $N$ is a matroid of the form $M(A + T)$, where $T$ is a binary matrix with rank at most $t$.

Here is the statement of their theorem (Theorem 3.1 of [2]) from that earlier post:

Theorem 2. Let $\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist integers $k$ and $t$ so that every vertically $k$-connected matroid in $\mathcal{M}$ is a rank-($\leq t$) perturbation of a graphic or cographic matroid.

This means that, for any proper minor-closed class $\mathcal{M}$ of binary matroids, we can make an efficient algorithm to compute the girth of members of $\mathcal{M}$ if we can do two things efficiently:

1. Compute the girth of a given rank-($\leq t$) perturbation of a graphic or a cographic matroid, and
2. Reduce the problem of computing the girth of members of $\mathcal{M}$ to that of computing the girth of vertically $k$-connected members of $\mathcal{M}$.

We don’t yet know how to solve either of these two subproblems in polynomial time, though in joint work Jim Geelen and I have mostly solved the first one by finding randomized algorithms to do it, which run in polynomial time and work correctly with probability nearly 1 (I won’t say more about those algorithms in this post though).

When $\mathcal{M}$ is the class of regular matroids, Theorem 2 holds with $k = 4$ and $t = 0$ (ignoring the slight exception of $R_{10}$). We can thus compute girth in regular matroids by reducing to the easy case of graphic and cographic matroids.

Unfortunately, the trick we used to do this reduction for regular matroids does not work so easily for other classes. For regular matroids, we needed to be able to find a minimum-weight circuit in a graphic or cographic matroid that used a specified element. While this was easy, the requirement of using a specified element makes things trickier for perturbations.

In the remainder of this post, I will outline a way to compute girth only for one special type of perturbation of graphic matroids, known as the even-cut matroids. But since it’s the same problem under matroid duality, we’ll actually look at cogirth (the smallest size of a cocircuit) in the duals of even-cut matroids, which are projections of graphic matroids. A projection of a graphic matroid $M(G)$ means a matroid of the form $M(A) / e$, where $A$ is a binary matrix obtained by adding one new column, indexed by an element $e$, to the vertex-edge incidence matrix of a graph $G$. The cocircuits of this matroid are precisely the cocircuits of $M(A)$ disjoint from $e$. But we need a way to describe these cocircuits in terms of the graph $G$.

We can view the new column of $e$ that we added to the vertex-edge incidence matrix of $G$ as the characteristic vector of a set of vertices of $G$. So we can fully describe this matroid by the pair $(G, T)$ where $T$ is a subset of $V(G)$. We can assume that $|T|$ is even; if not, then $e$ is a coloop of $M(A)$ and so $M(A) / e$ is graphic and the problem becomes easy.

Now we can describe the cocircuits in terms of the graph: they are precisely the minimal edge-cutsets of the form $\delta(X)$ where $|X \cap T|$ is even. Let’s call such edge-cutsets $T$-even cuts. How can we find a minimum-size $T$-even cut and thereby compute the cogirth of this projection of a graphic matroid? Here is a solution from Barahona and Conforti [1].

Let’s say that $\delta(W)$ is a minimum $T$-even cut in the graph $G$, so we want to either find it, or find another one of equal size. We already know how to find a minimum cut in $G$ in poylnomial time, so we’ll find one of those and call it $\delta(U)$. If we are lucky and $|U \cap T|$ is even, then we’re done. Otherwise, $|U \cap T|$ is odd.

Now let’s look at the possible interactions between $W$ and $U$. Exactly one of the sets $|W \cap U \cap T|$ and $|(V(G) – W) \cap U \cap T|$ is odd and the other is even; by the symmetry between $W$ and $V(G) – W$, let’s say that $|W \cap U \cap T|$ is even. And since $|W \cap T|$ is even, the set $|W \cap (V(G) – U) \cap T|$ is also even.

That means that $\delta(W \cap U)$ and $\delta(W \cap (V(G) – U))$ are also $T$-even cuts! Unless they are empty. But they can’t both be empty, or $W$ would be empty. So suppose, by symmetry, that $\delta(W \cap U)$ is a non-empty $T$-even cut. Then we apply the submodularity inequality: \[ |\delta(W \cap U)| + |\delta(W \cup U)| \leq |\delta(U)| + |\delta(W)|. \] Since $\delta(U)$ is a minimum cut, we have $|\delta(U)| \leq |\delta(W \cup U)|$, which means that $|\delta(W \cap U)| \leq |\delta(W)|$ so $\delta(W \cap U)$ is actually a minimum $T$-even cut!

So we’ve shown that there is a minimum $T$-even cut of the form $\delta(W’)$, where $W’$ is either contained in $U$ or contained in $V(G) – U$. We construct two graphs: $G_1$ is obtained from $G$ by identifying all vertices in $U$ to a single vertex, and $G_1$ is obtained by identifying all vertices in $V(G) – U$ to a single vertex. In both cases, we add the new vertex to the set $T$. We can check that every $T$-even cut of $G_1$ or of $G_2$ is also a $T$-even cut of $G$. But in addition, our desired cut $\delta(W’)$ is definitely a $T$-even cut in either $G_1$ or $G_2$. So we finish by recursively solving the problem for these two smaller graphs.

References

[1] Francisco Barahona and Michele Conforti, A construction for binary matroids, Discrete Math. 66 (1987), 213-218.

[2] Jim Geelen, Bert Gerards and Geoff Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5012 [math.CO].

[3] K. Truemper, Matroid Decomposition, Leibniz, Plano, Texas, 1998.

[4] Alexander Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997), 1757-1766.