In March Steve Noble came to the University of Western Australia for a few weeks and introduced me and Gordon to the <<add your favourite adjective here>> world of multimatroids. Multimatroids generalise matroids and even Delta matroids. Multimatroids were extensively studied by Bouchet in a series of papers (the first one being [B97]) and I will follow his terminology here.

Definitions

To define multimatroids we need a bit of setup. Let $K$ be a partition of a finite set $U$; in our context we call each class $k \in K$ a skew class and we say that two elements form a skew pair if they are contained in the same skew class. A subtransversal of $K$ is a subset of $U$ that contains at most one element from each skew class. A transversal is a maximal subtransversal (i.e. a subset of $U$ that contains exactly one element from each skew class). Denote by $\mathcal{S}(K)$ and $\mathcal{T}(K)$ the set of all subtransversals and transversals of $K$ respectively. Now let $r$ be a function from $\mathcal{S}(K) \rightarrow \mathbb{N}$ such that the following hold:

1. For every transversal $T$, the restriction of $r$ to $T$ induces a matroid on $T$.
2. For every subtransversal $S$ and any skew pair $\{x,y\}$ in a skew class disjoint from $S$, we have $r(S\cup x)-r(S)+r(S\cup y)-r(S)\geq 1$.

In other words, property 2. is saying that if we have a subtransversal $S$ and a skew class  $k$ not covered by $S$, then $r(S \cup x)=r(S)+1$ for all but possibly one $x \in k$.

Some properties and constructions

A multimatroid in which every skew class has size $p$ is called a $p$-matroid. From the definition it’s immediate that a 1-matroid is simply a matroid. There is another way of obtaining a multimatroid (in fact, a 2-matroid) from a matroid, as follows. Say that $N=(E,r)$ is a matroid and $N^*=(E,r^*)$ is its dual. Make two copies $E_1$ and $E_2$ of $E$, where, for every $e\in E$ we denote by $e_i$ the copy of $e$ in $E_i$ and similarly, for every subset $A \subseteq E$ we denote by $A_i$ the subset of $E_i$ corresponding to $A$ (and write $r(A_i)$ for $r(A)$, and similarly for $r^*$). Define a 2-matroid as follows: the ground set is $E_1 \cup E_2$, the skew classes are all pairs of the form $\{e_1,e_2\}$ for $e \in E$ and, for every subtransversal $S$, the rank of $S$ in the 2-matroid is $r(S\cap E_1) + r^*(S \cap E_2)$. Bouchet showed that, not only this is multimatroid, but in fact we can do a similar construction for any set of mutually orthogonal matroids $N_1,\ldots, N_n$. He also show that, conversely, if $T_1$ and $T_2$ are two disjoint transversals of a multimatroid $M$, then the matroids induced on $T_1$ and on $T_2$ are orthogonal (see [B98]).

Later in the post I’ll explain how Delta matroids correspond to 2-matroids, but first let’s talk about general multimatroids a bit more.

I defined multimatroids in terms of rank and as a matroid theorist the first question that pops to mind is whether we can talk about other matroid-like objects, such as independent sets, bases, etc. The answer is yes, but only while being extra careful. For example, we need to keep in mind that these terms only make sense when talking about subtransversals, not any subset of the ground set that you could think of. As one may expect, a subtransversal $S$ is independent if $r(S)=|S|$, otherwise it’s dependent. The bases of a multimatroid are the maximal independent sets and (by 2. above) if every skew class has size at least 2 then every base is a transversal. Finally a circuit is a minimal transversal that is not independent. In [B97] Bouchet gave equivalent definitions of multimatroids in terms of bases, independent sets and circuits.

One can also define minor operations for multimatroids, as in [B98], but here things are a bit different than for matroids: we don’t have a deletion and a contraction operation, but just a minor operation. Let $x$ by an element of a multimatroid $M=(U,K,r)$ and $k_x$ be the skew class containing $x$. Then the multimatroid $M|x$ has ground set $U’=U-k_x$, skew classes $K’=K-k_x$ and, for every subtransversal $S$ of $K’$ we have $r'(S)=r(S\cup x)-r(x)$. This looks a bit like contracting $x$ and deleting all other elements in $k_x$. In fact, if $M$ is the multimatroid obtained from a matroid $N$ and its dual as above, then $M|x_1$ is the multimatroid obtained from $N/x$ and its dual, while $M|x_2$ is the multimatroid obtained from $N\backslash x$ and its dual.

Delta matroids

First let me define what Delta matroids are. A Delta matroid is a pair $(E,\mathcal{F})$ where $E$ is a finite set and $\mathcal{F}$ is a nonempty family of subsets of $E$ (called feasible sets) satisfying the following property: if $F,F’\in \mathcal{F}$ and $x \in F\Delta F’$, then there exists $y \in F \Delta F’$ such that $F\Delta \{x,y\} \in \mathcal{F}$. Here $x$ could be equal to $y$, though if that doesn’t happen what we get is an even Delta matroid. The terminology is a bit unfortunate here, but basically a Delta matroid is even if all feasible sets have the same parity.

Now say that $(E,\mathcal{F})$ is a Delta matroid. As before, make two copies $E_1$ and $E_2$ of $E$ and define a 2-matroid as follows: the ground set is $E_1 \cup E_2$, the skew classes are all pairs of the form $\{e_1,e_2\}$ for $e \in E$ and the set of bases of the 2-matroid is $\{F_1 \cup (E_2-F_2) :  F \in \mathcal{F}\}$. Then what we get is a 2-matroid and in fact all 2-matroids may be obtained this way from Delta matroids.

References

[B97] A. Bouchet, Multimatroids I. Coverings by independent sets.  SIAM J. Discrete Math 10 (1997) 626-646.

[B98] A. Bouchet, Multimatroids II. Orthogonality, minors and connectivity.  Electron. J. Combinatorics 5 (1998) R8.

In this week-late post I will talk some more about results and conjectures concerning chromatic polynomials of graphs and matroids. As the title suggests, this is a continuation from my April post on the same topic. At the end of that post I said that I would discuss complex chromatic roots of graphs, but here I’ve decided to talk about matroids instead.

The chromatic polynomial of graphs is defined in terms of number of colourings with a given number of colours; this definition does not extend to matroids for obvious reasons. However, the Recipe Theorem by Oxley and Welsh in [OW79] tells us that a function on graphs or matroids satisfying a deletion-contraction recursion is essentially an evaluation of the Tutte polynomial. Now the chromatic polynomial does satisfy this type of recursion, and in fact Tutte’s polynomial was first called by Tutte the dichromatic polynomial, since he saw it as a generalisation of the chromatic polynomial of a graph. If $T_G(x,y)$ denotes the Tutte polynomial of a graph $G$, then \[P(G,q)=(-1)^{|V(G)-k(G)}q^{k(G)}T_G(1-q,0).\]

This definition can easily be extended to matroids. However, the equivalent of the chromatic polynomial for matroids is called the characteristic polynomial, and it is very slightly different (in that is has a missing power of $q$ factor). The characteristic polynomial of a matroid $M$ is denoted as $C(M,q)$ and may be defined as \[C(M,q)=(-1)^{r(M)}T_M(1-q,0).\]

So if $G$ is a graph with $k(G)$ components and $M=M(G)$, then $C(M,q)=q^{-k(G)}P(G,q)$, which for our purposes means that the chromatic polynomial of a graph $G$ and the characteristic polynomial of its graphic matroid $M(G)$ are essentially the same. I’m not sure why this terminology was adopted, since the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix, hence has nothing to do with the characteristic polynomial of its graphic matroid. Anyway, let’s see what we can say about real chromatic roots of matroids. We can still talk about root-free intervals and upper root-free intervals in the same way as for graphs.

Just to recap, a real interval $(a,b)$ is a root-free interval for a family of matroids $\mathcal{M}$ if no matroid in  $\mathcal{M}$ has a chromatic root (i.e. a root of its characteristic polynomial) in the interval $(a,b)$, while $\mathcal{M}$ has an upper root-free interval if there is a real number $a$ such that no matroid in $\mathcal{M}$ has a real root larger than $a$. The class of all matroids does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from graphs). Many of the results I mentioned for graphs in my previous post generalise to matroids. In particular, if $M$ is a loopless connected matroid, then:

• $C(M,q)$ is an alternating polynomial with degree $r(M)$,
• $C(M,q)$ is non-zero with sign $(-1)^{r(E)}$ for $q\in (-\infty,0)$,
• $C(M,q)$ has a simple zero at $q=1$, and
• $C(M,q)$ is non-zero with sign $(-1)^{r(E)+1}$ for $q\in (0,\frac{32}{27})$.

As for graphs, the first three results are easy to see if you write the chromatic polynomial in the right form. Namely

\[C(M,q)=\sum_{X\subseteq E(M)}(-1)^{|X|}q^{r(E)-r(X)}.\]

The fourth result above was proved for matroids by Edwards, Hierons and Jackson [EHJ98]. So the magic number $\frac{32}{27}$ is still magic for matroids.

If a class of matroids contains all graphic matroids, then it has no upper root-free interval (because of cliques). What about minor-closed classes of matroids not containing all graphs?

If you recall, Woodall and Thomassen proved independently that if $\mathcal{G}$ is a proper minor-closed family of graphs, then $(d(\mathcal{G}),\infty)$ is an upper root-free interval for $\mathcal{G}$, where $d(\mathcal{G})$ is the minimum number such that every graph in $\mathcal{G}$ has a vertex of degree at most $d$ (this is finite by a theorem of Mader). The surprising fact is that this result was published in 1997, while it is in fact implied by a more general and quite a bit older result for matroids. In 1978 Oxley proved the following.

Theorem 1: Let $D=\{x_1,\ldots,x_k\}$ be a cocircuit of a matroid $M$. Then \[C(M,q)=(q-k)C(M\backslash D,q)+\sum_{j=2}^{k}\sum_{i=1}^{j-1} C(M\backslash x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{j-1}/x_i,x_j, q).\]

This looks a bit complicated, but by induction it implies the following.

Corollary 2: If all minors of a matroid $M$ have a cocircuit of size at most $k$, then $C(M,q)>0$ for all $q \geq k$.

Corollary 2 in turns implies that any proper minor-closed class of graphs has an upper root-free interval (i.e. the result of Woodall and Thomassen). It also implies the same result for matroids of bounded branch width. Unfortunately, minor-closed classes of matroids may not have bounded minimum cocircuit size, even if they don’t contain all graphic matroids, so the following is still wide open.

Conjecture 3: Every minor closed class of matroids that does not contain all graphic matroids has an upper root-free interval.

A very special but still very difficult case of this conjecture is the following.

Conjecture 4: The class of cographic matroids has an upper root-free interval.

Conjecture 4 has been studied quite a bit, since it is in fact a question on flows in graphs (the characteristic polynomial of a matroid is the flow polynomial of its dual). I’ll conclude the post with a bit of history on this problem.

Welsh conjecture that $(4,\infty)$ is an upper root-free interval for cographic matroids. For planar graphs this would imply the Birkoff-Lewis conjecture. However, Gordon Royle found counterexamples to this conjecture by looking at a family of graphs called generalised Petersen graphs. Based on the examples he found for which he could calculate the real roots, he modified Welsh’s conjecture, changing the 4 to a 5, as “$(5,\infty)$ is an upper root-free interval for cographic matroids”. However, this conjecture turned out to also be false, as proved by Jesus Salas and Jesper Jacobsen, who managed to show that some large generalised Petersen graph has real flow roots slightly over 5. Incidentally, in July I went to Royal Holloway to attend the Workshop on New Directions for the Tutte Polynomial and I saw Jesus Salas give a talk on this. You can have a look at his slides on the conference page. So now the question remains of whether cographic matroids do have an upper root-free interval, and if so, what the interval is.

References

At the beginning of this year I started a new postdoc, still at the University of Western Australia and still with Gordon Royle, but on a new project, which is titled “Real chromatic roots of graphs and matroids”. That is, real roots of the chromatic polynomial of graphs and matroids. Since its first definition by Birkhoff in 1912, the chromatic polynomial has received much attention, not only by the mathematical community, but also, for example, by physicists. There are lots of interesting results and yet more interesting open problems in the area, and since I’m now navigating the extensive literature I decided to write a series of posts on the subject. I will mostly follow the notation of Gordon Royle’s excellent survey on chromatic and flow roots [R09].

Let’s start with a bit of history and some basic definitions. The chromatic polynomial (for planar graphs) was first defined by Birkhoff in an attempt to find an algebraic proof of the then open four-colour problem. The chromatic polynomial $P(G,q)$ of a graph $G$ counts, for every positive integer $q$, the number of proper colouring of the vertices of $G$ with $q$ colours. One can easily check that, if $e$ is an edge of $G$, then \[P(G, q)=P(G\backslash e, q)-P(G/e, q).\] In fact, the number of $q$-colouring of $G$ is equal to the number of $q$-colouring of $G\backslash e$ where the endpoints of $e$ receive distinct colours and $P(G/e,q)$ counts the number of $q$-colourings of $G \backslash e$ where the endpoints of $e$ receive the same colour. The above formula is called the deletion-contraction formula and from it one can easily deduce that $P(G,q)$ is indeed a polynomial. One can also see that this is the case by showing directly that $P(G,q)$ is a sum of polynomials, as in the next lemma.

Lemma 1: For every graph $G$, \[P(G,q)=\sum_{X\subseteq E(G)}(-1)^{|X|}q^{k(X)},\] where $k(X)$ is the number of components of the graph induced by $X$.

proof: Let us consider colourings (not necessarily proper ones) of $V(G)$ with $q$ colours; there are $q^{|V(G)|}$ of them. For every $e \in E(G)$, denote by $B_e$ the set of colourings where the endpoints of $e$ receive the same colour. Then \[P(G,q)=q^{|V(G)|}-|\cup_{e\in E(G)}B_e|.\] Also note that \[|\cap_{e\in X}B_e|=q^{k(X)}.\] Now the result follows from applying the inclusion-exclusion principle to the first equality and using the second equality.$\qquad \Box$

Since the chromatic polynomial can be evaluated at real and complex values, Birkhoff hoped to use analytic methods to prove the 4-colour conjecture. In fact, the four-colour Theorem is equivalent to stating that $P(G,4)>0$ for all planar graphs $G$, i.e. 4 is not a chromatic root of any planar graph. As we know, such an analytic proof was never found, but Birkhoff and Lewis [BL46] did show that if $G$ is planar then $P(G,q)>0$ for all real $q\geq 5$. They conjectured that 5 could be changed to 4, and almost 70 years later their conjecture is still open.

Conjecture 2 (Birkhoff-Lewis, 1946). If $G$ is a planar graph, then $P(G,q)>0$ for all real $q \geq 4$.

The Birkhoff-Lewis conjecture motivated the study of real chromatic roots of graphs, with special attention to finding lower and upper bounds on them. A real interval $(a,b)$ is a root-free interval for a family of graphs $\mathcal{G}$ if no graph in $\mathcal{G}$ has a chromatic root (i.e. a root of its chromatic polynomial) in the interval $(a,b)$.

The chromatic polynomial of a graph $G$ with $n$ vertices may be expressed as \[P(G,q)=\sum_{i=1}^n (-1)^{n-i}h_iq^i,\] where $h_i \in \mathbb{N}$ for all $i=1,\ldots,n$ and $h_n=1$. From this one can easily deduce that $(-1)^nP(G,q)>0$ for all real $q<0$, thus the interval $(-\infty,0)$ is a root-free interval for all graphs. With a bit more work (considering forests first, then using induction and the deletion-contraction formula) one can also show that $(-1)^{n-k(G)}P(G,q)>0$ for all real $q \in (0,1)$. A much less trivial result, due to Jackson [J93] gives the following surprising root-free interval.

Theorem 3 (Jackson [J93]). Let $G$ be a connected graph with $n\geq 2$ vertices and $b$ blocks. Then $(-1)^{n+b+1}P(G,q)>0$ for all real $q \in (1,32/27]$.

What is especially surprising about this result is the fact that this interval is best possible, in  the following sense.

Theorem 4 (Thomassen, [T97]). For all real numbers $a,b$ with $32/27<a<b$, there exists a graph $G$ that has a chromatic root in $[a,b]$.

What about largest real roots? A family of graphs $\mathcal{G}$ has an upper root-free interval if there is a real number $a$ such that no graph in $\mathcal{G}$ has a real root larger than $a$. The class of all graphs does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from cliques). Restricting our attention to bipartite graphs, the situation does not improve.

Theorem 5 (Woodall [W77]). If $n$ is sufficiently large compared to $m$, then the complete bipartite graph $K_{m,n}$ has real chromatic roots arbitrarily close to all integers in $[2,m/2]$.

However, the situation is quite different when we consider proper minor-closed classes of graphs instead. This is because graphs in a proper minor-closed class must have a vertex of “small” degree. 

Theorem 6 (Mader [M67]). For every $k \in \mathbb{N}$ there exists an integer $f(k)$ such that any graph with minimum degree at least $f(k)$ has a $K_k$-minor.

It follows that, for every proper minor-closed family of graphs $\mathcal{G}$, there exists a smallest integer $d=d(\mathcal{G})$ such that every graph in $\mathcal{G}$ has a vertex of degree at most $d$. Woodall and Thomassen proved the next result independently.

Theorem 7 (Thomassen [T97], Woodall [W97]). If $\mathcal{G}$ is a proper minor-closed family of graphs, then $(d(\mathcal{G}),\infty)$ is an upper root-free interval for $\mathcal{G}$.

In the next post I’ll talk about complex chromatic roots and then move on to matroids.

References:

[BL46] G.D. Birkhoff, D.C. Lewis, Chromatic polynomials. Trans. Amer. Math. Soc. 60, (1946). 355–451.

[J93] B. Jackson, A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 (1993), no. 3, 325–336.

[R09] G.F. Royle, Recent results on chromatic and flow roots of graphs and matroids. Surveys in combinatorics 2009, 289–327, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009.

[T97] Thomassen, Carsten, The zero-free intervals for chromatic polynomials of graphs. Combin. Probab. Comput. 6 (1997), no. 4, 497–506.

[W77] D.R. Woodall, Zeros of chromatic polynomials. Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway College, Egham, 1977), pp. 199–223. Academic Press, London, 1977.

[W97] D.R. Woodall, The largest real zero of the chromatic polynomial. Discrete Math. 172 (1997), no. 1-3, 141–153.

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.