I’ve been on the road: three Canadian provinces and six states (five American, one Australian) in the last two months. My body-clock has no idea what it should be set to, and this morning I found myself utterly befuddled when I woke up in my own bedroom for the first time in months — but the upside is that I’ve been to a couple of really enjoyable meetings.

Combinatorial Potlatch

The Combinatorial Potlatch is a British Columbian/Pacific North-West institution. The word Potlatch refers to a gift-giving festival practised by the indigenous inhabitants of the area, and it was chosen to reflect the informal and hospitable nature of the workshop. I really like the way the meeting is run: it lasts only one day, there are only two or three speakers, and the day ends in the pub. Nobody speaks more than once in the series, ensuring that new people to the area are given a chance to participate. Judging by this year’s meeting, there is also an emphasis on inviting early-career mathematicians. In fact I had the slightly unsettling experience of being the oldest of the speakers: the first time this has happened to me, but probably not the last (if I can be presumptuous enough to expect further invitations).

In its recent incarnation, the Potlatch is organised by Nancy Neudauer and Rob Beezer, both of whom I know from a short course on matroid theory that Nancy ran during the 2011 joint meeting of the AMS and MAA. Every year a university from the region is tapped to host the meeting, and in 2013 it was the turn of Victoria University, the namesake of my own institution. The name of this Victoria is slightly more obvious, as it resides in the town of Victoria, provincial capital of British Columbia, and largest urban area on Vancouver Island. I had been in Vancouver immediately before the meeting, so I caught the ferry, which dodges islands in the Juan De Fuca Strait.

The island is also beautiful. While I was there I got to see some spawning salmon:

Of course, you don’t get to spawn without breaking some fish:

All part of life’s cycle, but it does make for a fairly pungent atmosphere.

I enjoyed the two talks that I got to see at the Potlatch. Richard Hoshino gave an interesting and personal talk about some of his career choices; in particular, his decision to emphasise education and real-world optimisation over pure research that is unlikely to be appreciated or noticed by more than a handful. Speaking for myself, it doesn’t bother me too much that my research will only ever be read by specialists. I think it’s legitimate for artists and pure mathematicians alike to gain satisfaction from doing the best work they can, while letting the audience take care of itself — the number of people who appreciate a piece of work isn’t necessarily the best indication of its quality anyway. But I certainly understand that not everyone feels as I do.

Jérémie Lumbroso gave an attractive talk on an idea that I hadn’t encountered before: if we have a generating function that enumerates a class of combinatorial objects, then we can use that generating function to construct a parameterised random algorithm that will select one of those objects. The choice of parameter will influence the size of the object chosen by the algorithm. Therefore, if we want to randomly select a rooted binary tree embedded in the plane with 20 vertices (say), then we adjust our parameter so that the algorithm will deliver a tree of the right size with reasonable probability, and we let it run until it produces an output with 20 vertices. This process chooses trees of 20 vertices with uniform probability. Jérémie showed us the code that he used to implement the algorithm, and it was remarkably simple: just a couple of lines of Mathematica code.

37ACCMCC

Soon after the Potlatch, it was time for me to head to Perth for the 37th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing. Matroidunion.org’s own Irene Pivotto was a member of the organising committee, and Gordon Royle from SymOmega lead the committee. It was an extremely well-run meeting; so much so, in fact, that you can only feel sorry for the organiser of the 38th conference, given the high standards that he or she will have to live up to. (Expect to see more posts about 38ACCMCC sometime soon.)

I enjoyed many talks at the ACCMCC, so I will mention only the ones with significant amounts of matroid content. Nick Brettell spoke about an algorithm for constructing a $k$-tree of a matroid; Ben Clark talked about a project that myself and Stefan are involved in: the attempt to find excluded minors for the matroids representable over the partial field $\mathbb{H}_{5}$; Rong Chen talked about an inductive connectivity theorem for $k$-coherent matroids; Darryl Funk described work on the excluded minors for the class of frame matroids; Songbao Mo talked about a polymatroidal characterisation of abstract connectivity functions; Peter Nelson’s presentation covered some of the same material as his most recent post; Irene Pivotto spoke about some work she has done with Rong on a class of matroids arising from bias graphs; Michael Welsh described work on a conjecture of Steven Archer on maximum-sized golden-mean matroids. I think that covers everyone, so apologies if I have missed anyone.

The talks I gave at the two conferences were basically isomorphic (so apologies to the two people who were in the audience for both). In the first half I introduced matroids, and talked about excluded-minor characterizations, both exisiting and those still in progress. The second half was dedicated to work I have been doing with Mike Newman and Geoff Whittle on the impossibility of using matroid axioms to capture representability. Here are my slides.

Postscript

Attending these conferences made me think again about a small peeve of mine. I can’t understand the practice of abbreviating one’s own name to an initial when listing the authors of a theorem. You will no doubt know what I mean:

Theorem (M., Newman, Whittle — 2013)

instead of

Theorem (Mayhew, Newman, Whittle — 2013).

Can anyone tell me why we do this? It makes no sense to me. Slides usually have enough room to list names in full, so it can’t be a space constraint. Perhaps it comes from some sense of humility, as if we don’t want to lay too much of a claim to our own work lest we appear immodest? If that’s the case, then we seem to be saying that writing one’s own name above a theorem that we helped prove is an unbearable act of self-aggrandisement, and I can’t agree with that. I think it’s probably more likely that the custom just started years ago, and now people do it because it is what everyone does. But that’s not a good enough reason to continue a tradition. Unless somebody gives a masterful argument in favour of the practice in the comments, then I am going to write my own name in full on my slides, and I think others should do the same.

$\newcommand{\elem}{\varepsilon}$
Time for more growth rates. For a matroid $M$ we’ve looked at $\elem(M)$, the number of points in $M$, as a simple density parameter that is bounded as a function of $\ell$ and $r$ whenever we exclude $U_{2,\ell+2}$ as a minor. Then, as a way to talk about density when excluding a uniform minor of larger rank than $2$, we generalised this to $\tau_a(M)$, defined to be the number of rank-$a$ flats required to cover $\elem(M)$, which turned out to be the right notion of density to think about when excluding a rank-$(a+1)$ uniform matroid as a minor. As far as excluding different uniform minors is concerned, $\tau_a$ is the generalisation of $\elem$ that we need. However, there is another natural way to generalise $\elem(M)$ to ‘higher rank’, which is what this post is about.

For a matroid $M$ and a nonnegative integer $k$, we let $W_k(M)$ denote the number of rank-$k$ flats in $M$. This parameter, known as the $k$th Whitney number of the second kind, is clearly of interest when thinking about the lattice of flats of $M$. A 1971 conjecture of Rota [R71] is that the sequence $W_0(M),W_1(M), \dotsc, W_r(M)$ is unimodal; that is, that $W_k(M) \ge \min(W_{k-1}(M),W_{k+1}(M))$ for each $k$. From what I can see in the published literature, this conjecture is still open, although Huh, Katz and Lenz [HK11,L11] have recently used sophisticated algebraic techniques to make real progress on similar conjectures in the representable case. In fact, Mason [M72] conjectured a few strengthenings of this conjecture; the first and weakest is that the sequence of Whitney numbers is log-concave (which is itself stronger than unimodality).

What I’m considering today relates more to previous posts than the above conjectures: bounding $W_k(M)$ above by a function of $\ell$ and $r(M)$ when excluding a $U_{2,\ell+2}$ (when excluding a larger uniform minor it is not hard to argue that no such bound is possible). This has quite a different flavour to the conjecture above; we know that in many ways excluding a uniform minor gives classes whose extremal members resemble projective geometries, so we’d hope that the bounds we get are similar or equal to those we get for geometries. The number of rank-$k$ flats in a geometry PG$(n-1,q)$ is a nice number which we denote ${n \brack k}_q$. More explicitly,
\[ W_k(\mathrm{PG}(n-1,q) = {n \brack k}_q = \frac{(q^n-1)(q^{n-1}-1)\dotsc(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\dotsc(q-1)}\]
This is known as the Gaussian binomial coefficient for $n,k$ and $q$. We already know by Kung’s theorem that a rank-$r$ matroid with no $U_{2,q+2}$-minor has at most ${r \brack 1}_q = \frac{q^r-1}{q-1}$ rank-$1$ flats. The natural generalisation of this statement was conjectured by Bonin:

Conjecture 1: If $q$ is a prime power and $M$ is a rank-$r$ matroid with no $U_{2,q+2}$-minor, then $W_k(M) \le {r \brack k}_q$ for each integer $k$.

Unfortunately, this conjecture is false – I’ll get to the counterexample in a minute. In [N13] I proved this conjecture whenever $r$ is large compared to $k$ and $q$. In fact, as with our generalisation of Kung’s theorem in our first post, I get the projective geometry bound for excluding an arbitrary rank-$2$ uniform minor, not just one corresponding to a prime power.

Theorem 1: For all integers $\ell \ge 2$ and $k \ge 0$ there is an integer $r_0$ such that, if $M$ is a matroid with no $U_{2,\ell+2}$-minor and $r(M) \ge r_0$, then $W_k(M) \le {r(M) \brack k}_q$, where $q$ is the largest prime power not exceeding $\ell$.

It is good to know this. However, this theorem doesn’t tell us everything. For many reasons, it would be very nice to have a good upper bound on the number of hyperplanes of a matroid with no $U_{2,q+2}$-minor; the above theorem says nothing when $k = r-1$, only when $r$ is huge compared to $k$. One can obtain a crude upper bound on the number of hyperplanes by bounding the number of points and observing that each hyperplane is spanned by $r-1$ points, but this bound, roughly $q^{q^2}$, is likely dramatically wrong.

Conjecture 1 would imply that the correct upper bound for the number of hyperplanes when excluding $U_{2,q+2}$ is $\frac{q^r-1}{q-1}$. I don’t have any good ideas for how to prove this, and in fact this is where the conjecture fails – the next theorem follows from a construction communicated to me by Blokhuis.

Theorem 2: For each prime power $q$ there is a rank-$3$ matroid $M_q$ with no $U_{2,2q}$-minor such that $W_2(M_q) = q^2 + (q+1)\binom{q}{2}$.

For large $q$, this is too many lines for Conjecture 1 to hold! There are issues with the precise numbers, but essentially Conjecture 1 would state that $W_2(M) \le q^2 + q+ 1$ for any matroid $M$ with no $U_{2,q+2}$-minor; this is quadratic in $q$, but $W_2(M_q)$ is cubic in $q$. The factor of $2$ in the length of the line that $W_2(M_q)$ omits is unimportant in the face of this qualitative difference. It is fairly easy to use Theorem 2 to find counterexamples to Conjecture 1 for all $q \ge 128$; Using a variation on the construction and a bit of work for small $q$, Jim and I [GN13] proved the following:

Theorem 3: When $r = 3$ and $k = 2$, Conjecture 1 holds if and only if $q \le 5$. On the other hand, when $q \in \{2,3,4\}$, and $k = 2$, Conjecture 1 holds for all $r$.

The first part of this is unfortunate, as Conjecture 1 is pretty. What I would hope is that the examples in Theorem 2 are a result of rank-$3$ sporadicity of the same sort that makes projective planes so hard to classify for finite geometers. It’s quite possible that Conjecture 1 holds for all $r \ge 4$, but I would settle for the following.

Conjecture 2: For all $q$ there is an integer $r_0$ such that Conjecture 1 holds for $q$, all $k$ and all $r \ge r_0$.

The difference between this statement and that of Theorem 1 is that there is no longer any dependence of $r_0$ on $k$; the above conjecture would give a sensible upper bound on the number of hyperplanes. It would also be very interesting to see what happens in even the smallest concrete rank-$4$ cases for which we don’t already have the answer:

Conjecture 3: Conjecture 1 holds for $r = 4, k = 3$ and $q = 3$.
Conjecture 4: Conjecture 1 holds for $r = 4, k = 2$ and $q = 7$.

Next time, I’ll be back talking about something other than growth rates. See you then!

References
[GN13] J. Geelen, P. Nelson, The number of lines in a matroid with no $U_{2,n}$-minor, arXiv:1306.2387 [math.CO]
[HK11] J. Huh, E. Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, arXiv:1104.2519 [math.CO]
[L11] M. Lenz, Matroids and log-concavity, arXiv:1106.2944 [math.CO]
[M72] J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem. In Combinatorics (eds. D. J. A. Welsh and D. R. Woodall), pp 207-220 (1972). Institute of Math. and its Applications, Southend-on-Sea. [15.2]
[N13] P. Nelson, The number of rank-$k$ flats in a matroid with no $U_{2,n}$-minor, arXiv:1306.0531 [math.CO].
[R71] G.-C. Rota, Combinatorial theory, old and new. In Proc. Internat. Cong. Math.<> (Nice, 1970), pp. 229-233. Gauthier-Villars, Paris (1971). [6.0,6.5,14.0,15.2].

In this post I’ll discuss a way of constructing matroids from other matroids. A simpler form of this construction was first introduced by Rado. I will follow partly Matt DeVos’ notes on Rado matroids and partly [Oxley11, Sections 11.1-11.3].

Let $G$ be a bipartite graph, with bipartition $(X,Y)$. Denote by $N(S)$ the set of neighbours of vertices in $S$ that are in $V(G)-S$. Suppose that $M$ is a matroid on ground set $Y$ with rank function $r$. Let $t$ be any integer and define $\mathcal{C}$ to be the set of minimal non-empty subsets of $X$ satisfying $|S|>r(N(S))+t$. With this definition we have the following proposition. The proof is short, so I’ll include it.

Proposition 1: $\mathcal{C}$ is the set of circuits of a matroid on $X$.

proof: From the definition we immediately have that the first two circuit axioms are satisfied. Now consider distinct $C_1, C_2 \in \mathcal{C}$ and an element $e \in C_1 \cap C_2$. Using (in the last inequality) the fact that $C_1\cap C_2$ does not contain any member of $\mathcal{C}$, we have that $\\|C_1 \cup C_2| + |C_1 \cap C_2| = |C_1| + |C_2|\\ \geq r(N(C_1))+r(N(C_2))+2t+2\\ \geq r(N(C_1)\cup N(C_2)) + r(N(C_1) \cap N(C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+r(N(C_1 \cap C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+|C_1 \cap C_2|-t +2t +2$.

Therefore $r(N(C_1 \cup C_2)) \leq |C_1 \cup C_2|-t-2$. Let $C’=(C_1 \cup C_2)-e$.

Then $r(N(C))\leq kr(N(C_1 \cup C_2))\leq |C_1 \cup C_2|-t-2=|C|-t-1$. Hence $r(N(C))< |C|-t$, so $C$ contains an element of $\mathcal{C}$. $\hspace{2 cm} \Box$

I’ll call a matroid defined this way a Rado matroid. Rado defined these matroids for $t=0$, so in this case I will call the matroid a standard Rado matroid. We may make the definition above more general by adding a parameter $k \geq 1$ and defining $\mathcal{C}$ to be the minimal non-empty sets satisfying $|S|>kr(N(S))+t$. Then the proposition above still holds (with the same proof). However, all the examples I’m going to introduce here have $k=1$, so I will stick to the simpler definition.

Note that, strictly speaking, every matroid is a Rado matroid: if $N$ is any matroid on ground set $E$, then we can obtain it as a standard Rado matroid on $G$ with bipartition $(E,E)$, where every vertex is adjacent to its copy (and the matroid on $Y=E$ is $N$). However, seeing a matroid as a Rado matroid is sometimes useful, for example in the case of the hypergraphic matroids (which I will define later).

Lots of matroids may be constructed as Rado matroids (in a non-trivial way). Since there are many objects involved in the definition of a Rado matroid and I’m a bit lazy, in the following examples I will always assume that $G, X, Y, M$ and $t$ are as above and I’ll denote just by $R$ the Rado matroid.

• If $t \leq -r(M)$, then $R=U_{0,n}$.
• If $t \geq |Y|$, then $R=U_{n,n}$.
• If $M$ is a free matroid, then the standard Rado matroid is a transversal matroid (with respect to the sets $N(v)$ for $v \in X$).
• If $H$ is a graph and $G$ has bipartition $(E(H),V(H))$, where $e \in E(H)$ is adjacent to $v \in V(H)$ if $v \in e$, and $M$ is a free matroid, then the standard Rado matroid is the bicircular matroid of $H$. Thus we see that bicircular matroids are transversal matroids [Mat77].
• Define $G$ from $H$ as above and let $M$ be a free matroid again. If now we choose $t=-1$ we obtain as a Rado matroid the graphic matroid of $H$.

We can generalise the construction above to hypergraphs. Suppose that $H=(V,F)$ is a hypergraph and define $G$ as the graph with bipartition $(F,V)$, where $f \in F$ is adjacent to $v \in V$ if $v \in f$. Let $M$ be a free matroid and set $t=-1$. Then $R$ is the hypergraphic matroid, defined by Lorea [Lor75]. We can also see hypergraphic matroids as standard Rado matroids, with this alternative definition. Our starting hypergraph is still $H=(V,F)$. We define the bipartition of $G$ to be $(F,E)$, where $E$ is the edge set of $K_V$, the complete graph on $V$. For $f \in F$ and $e=uv \in E$, we set $e$ to be adjacent to $f$ if $u,v \in f$. Now if we choose $M$ to be the graphic matroid on $K_V$ then the standard Rado matroid is again the hypergraphic matroid of $H$. The advantage of this alternative definition is that Rado [Rado42] proved the following result for standard Rado matroids (where again $G, X, Y$ and $M$ are as in definition above). Call a matching independent if the set of vertices it covers in $Y$ is independent in $M$.

Theorem 2: If $R$ is a standard Rado matroid then a set $S \subseteq X$ is independent in $R$ if and only if there is an independent matching in $G$ covering $S$ (i.e. $S$ may be matched to an independent set of $M$).

From the definition of standard Rado matroids, we immediately have that a set $S \subseteq X$ is independent in $R$ exactly when $|S’|\leq r(N(S’))$ for every $S’$ contained in $S$. Thus Rado’s theorem is saying that this condition is satisfied exactly when $S$ may be matched to an independent set of $M$. This result looks suspiciously similar to P. Hall’s marriage theorem [Hall35]: in fact we obtain Hall’s marriage theorem from Theorem 2 when $M$ is a free matroid. A proof of Theorem 2 may be found, for example, in Matt DeVos’ notes on Rado matroids. In the same notes you may also find a proof of the following generalisation of König’s Theorem for bipartite graphs.

Theorem 3: There exists $A$ contained in $X$ such that the size of the largest independent matching is equal to $|X-A|+r(N(A))$.

Corollary 4: In a standard Rado matroid, the rank of $S\subseteq X$ is equal to $$min_{A \subseteq S} \{|S-A|+r(N(A))\}.$$

Going back to our definition of a hypergraphic matroid as a standard Rado matroid, Theorem 2 tells us that a set of hyperedges $I$ is independent in this matroid if and only if we may replace every $f \in I$ with an edge $uv$, for $u,v \in f$, so that the resulting graph is a forest. This result was proved in [FKK03] (using the first definition of hypergraphic matroids).

Another interesting application of Rado’s construction is that we may obtain the Matroid Union Theorem (so relevant to our blog) as a consequence.  In fact, let $N_1,\ldots,N_k$ be matroids on a common ground set $E$, and let $M$ be the direct sum of $N_1,\ldots,N_k$. Define a bipartite graph $G$ with bipartitions $E$ and $E_1\cup \cdots\cup E_k$, where each $E_i$ is a copy of $E$ (seen as the ground set of $N_i$). Any element $e \in E$ is adjacent to each of its copies in $E_1,\ldots,E_k$. Then the standard Rado matroid is just the union matroid $N_1 \vee \cdots \vee N_k$, first introduced by Nash-Williams [N-W66]. As expected, Corollary 4 implies that the rank of a set $S$ in $N_1 \vee \cdots \vee N_k$ is $$min_{A \subseteq S} \{|S-A|+r_1(A)+\cdots +r_k(A)\},$$ where $r_i(A)$ is the rank of $A$ in $N_i$.

I was first introduced to Rado matroids while working on a paper [DMP13] with Matt DeVos and Jessica McDonald. Another nice theorem that we used in that paper is a result by Király, Lau and Singh [KLS08]. Basically this theorem says that, if $M$ has a fractional basis satisfying some constraints, then it has an actual basis almost satisfying those constraints. This theorem has nothing to do with Rado matroids, but I think it’s a nice result so I’m going to go ahead and end my post on it. First let me define what I mean by a fractional basis.

Let $M$ be a matroid on $E$ with rank function $r$ and let $x \in \mathbb{R}^E$ be a vector satisfying the following three constraints:

1. $0 \leq x(e) \leq 1$, for every $e \in E$.
2. $x(S) \leq r(S)$, for every $S \subseteq E$.
3. $x(E)=r(E)$.

Then we say that $x$ is a fractional basis of $M$. The name is justified by the following result of Edmonds’ [Edm69].

Theorem 5: If a vector $x$ satisfies 1. and 2. above, then $x$ is a convex combination of incidence vectors of independent sets of $M$.

Thus a fractional basis is a convex combination of incidence vectors of bases of $M$. The last result of this post (from [KLS08]) may be used, for example, to prove the existence of a bounded degree spanning tree in a graph if a bounded degree fractional spanning tree exists.

Theorem 6: Let $M$ be a matroid on $E$, let $x$ be a fractional basis of $M$, and let $\mathcal{F}$ be a collection of subsets of $E$ so that every $e \in E$ is contained in at most $d$ members of $\mathcal{F}$. Then $M$ has a basis $B$ such that every $F \in \mathcal{F}$ satisfies $|B \cap F| \leq \lceil x(F) \rceil +d -1$.

References

[DMP13] M. DeVos, J. McDonald, I. Pivotto, Packing Steiner trees, submitted. (available on the ArXiv)

[Edm69] J. Edmonds, Submodular functions, matroids and certain polyhedra, Com- binatorial structures and their applications (Proc. Calgary Internat. Conf. 1969), 69-87. Gordon and Breach, New York.

[FKK03] A. Frank, T. Király, and M. Kriesell, On decomposing a hypergraph into $k$ connected sub-hypergraphs, Discrete Appl. Math. 131 (2003), 373-383.

[Hall35] P. Hall, On representatives of subsets, Quart. J. London Math. Soc. 10 (1935), 26-30.

[KLS08] T. Király, L. C. Lau, and M. Singh, Degree bounded matroids and submodular flows, Proceedings of 13th International Conference IPCO 2008, LNCS 5035 (2008), 259-272.

[Lor75] M. Lorea, Hypergraphes et matroides, Cahiers Centre Etud. Rech. Oper. 17 (1975), 289-291.

[Mat77] L.R. Matthews, Bicircular Matroids, Quart. J. Math. Oxford (2), 28 (1977), 213-228.

[N-W66] C. St. J. A, Nash-Williams, An application of matroids to graph theory, In Theory of Graphs (Internat. Sympos. Rome) (1966), 263-265. Dunod, Paris

[Oxley11] J. Oxley, Matroid Theory, Oxford University Press, New York (2011).

[Rado42] R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89.