In this post I’m going to conclude my investigation of Coxeter matroids and related objects.

We can motivate the definition of Coxeter matroids by thinking about a geometrical problem in the Euclidean space $\mathbb{R}^{n}$. Recall that a (closed) half-space is a set of the form $\{\mathbf{v}\in \mathbb{R}^{n}\colon
\mathbf{v}\cdot \mathbf{a}\geq b\}$, where $\mathbf{a}$ is a fixed (non-zero) vector, $b$ is a real number, and the dot denotes the standard inner product. A polyhedron is an intersection of finitely many half-spaces. A polyhedron is a polytope if it is bounded, meaning that there there must be some ball of finite radius centred on the origin that contains every point of the polytope. A vertex of a polyhedron is a point $\mathbf{p}$ in the polyhedron with the property that some affine hyperplane intersects the polyhedron exactly in $\mathbf{p}$. Similarly, an edge of a polyhedron is a line segment, $l$, such that some affine hyperplane intersects the polyhedron exactly in $l$. The terminal points of an edge are always vertices of the polytope.

Now let $P$ be a polytope. For every edge $l$ of $P$, there is an affine hyperplane that is perpendicular to $l$ and that passes through the mid-point of $l$. This affine hyperplane determines an isometry (a distance-preserving transformation) of $\mathbb{R}^{n}$: namely, reflection through the hyperplane.

What can we say about the group of isometries generated by these reflections? As the composition of any reflection with itself is the identity, this group is a Coxeter group, since the definition of such a group is that it must have a set of generators each of which has order two. When will this Coxeter group be finite? It is easy to find examples of polytopes that lead to finite Coxeter groups: just take any regular polygon. In this case the reflections generate the dihedral group. On the other hand, consider the points with polar coordinates $(0,0)$, $(1,-\alpha)$, $(1,\alpha)$, and $(1,3\alpha)$, where $\alpha$ is an irrational fraction of a full rotation. The intersection of all half-spaces that contain these four points is a polytope. The reflections corresponding to the edges of the polytope include the reflection in the horizontal axis, and also the reflection in the line with an angle of $2\alpha$ from the horizontal. Between them, these reflections generate a rotation of $4\alpha$ around the origin. The way that we chose $\alpha$ means that no finite power of this rotation will ever be equal to the identity isometry. Therefore the generated Coxeter group is infinite. The definition of Coxeter matroids is motivated by a partial solution of this problem of determining whether this generated group of isometries will be finite or infinite.

We have said that any regular polygon gives rise to a finite Coxeter group of isometries.
Let us now develop another method for finding such polytopes. Let $W$ be a finite group of isometries of $\mathbb{R}^{n}$ and assume that $W$ is generated by a collection of reflections. We will show that there is a point that is fixed by every isometry in $W$. Indeed, if $\mathbf{v}\in \mathbb{R}^{n}$ is arbitrarily chosen, then the barycentre of the images of $\mathbf{v}$ is fixed by every isometry in $W$, because
\[
u\left(\frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})\right)
= \frac{1}{|W|}\sum_{w\in W}u(w(\mathbf{v}))
= \frac{1}{|W|}\sum_{w\in W}w(\mathbf{v})
\]
for every $u\in W$. Therefore, by translating, we might as well assume that the reflections that generate $W$ all fix the origin. For each reflection $r\in W$, choose two vectors, $\mathbf{v}_{r}$ and $-\mathbf{v}_{r}$ that are orthogonal to the $r$-invariant hyperplane. Thus $r(\pm\mathbf{v}_{r})=\mp\mathbf{v}_{r}$. We shall call the collection $R=\{\pm \mathbf{v}_{r}\colon r\ \text{is a reflection in}\ W\}$ a root system of $W$. Note that the vectors in $R$ correspond in a natural way to the reflections in $W$. We have given no consideration to the length of the vectors $\mathbf{v}_{r}$, which means that we are not using the standard definition of a root system. This diagram shows a possible root system in $2$ dimensions.

Now let $\mathbf{a}$ be a fixed and arbitrary vector, and let $R^{+}=\{\mathbf{u}\in R\colon \mathbf{u}\cdot\mathbf{a}>0\}$ be the set of positive roots. The positive roots generate the positive cone, consisting of all linear combinations of vectors in $R^{+}$ with all coefficients non-negative. This positive cone is a polyhedron. Those vectors in $R^{+}$ that are parallel with an edge of the positive cone form a simple system of roots. In the following diagram, we have chosen $\mathbf{a}$ to be the vector $(1,0)$. There are three positive roots, and they generate the shaded positive cone. The two vectors coloured red form the corresponding simple system.

Let $I$ be the simple system of roots, and let $J$ be a non-empty subset of $I$. The roots in $J$ correspond to a collection of reflections in $W$. Let $P$ be the subgroup of $W$ generated by these reflections. This subgroup is called a standard parabolic subgroup of $W$. In our example, let $P$ be the subgroup generated by the reflection along the line parallel to $(1,1)$, that is, the reflection corresponding to the blue vector in the diagram below. Let $\mathcal{M}$ be a collection of cosets of $P$. In our example, we will keep things simple, and just let $\mathcal{M}$ be the collection of all cosets. We choose a point $\mathbf{v}$ that is fixed by $P$. For every coset $wP$ in $\mathcal{M}$, we find the image of $\mathbf{v}$ under $w$. Note that this image is well-defined, in the sense that it does not depend on the representative $w$, since $\mathbf{v}$ will be fixed by every isometry in $P$. Now we have generated a collection of images of $\mathbf{v}$. We construct the convex hull of these images: that is, we take the polytope consisting of the intersection of all half-spaces that contain the images of $\mathbf{v}$. It turns out that the Coxeter group generated by the edges of this polytope is finite (a subgroup of $W$ in fact). In the diagram below, the vector $\mathbf{v}$ is marked. There are four images of $\mathbf{v}$ under cosets of $P$, and the convex hull of those images is the shaded square.

What is surprising about this construction, is that every polytope generating a finite Coxeter group can essentially be constructed in this way. This is a consequence of a theorem due to Gelfand and Serganova (details are in the book Coxeter matroids).
So far, the link to matroids is not at all obvious, so I will conclude by drawing a connection back to my first post. Let $w_{1},\ldots, w_{t}$ be the reflections in $W$ that correspond to the vectors in a simple root system. Then $W$ is generated by $w_{1},\ldots, w_{t}$, so every $u\in W$ can be expressed as a word in these reflections. Such a word is said to be reduced if it is as short as possible. Now for $u,v\in W$ we say that $v\leq u$ in the Bruhat ordering if there is a reduced word that represents $u$, with the property that I can obtain a word representing $v$ by deleting some characters. If $w\in W$, then we write $v\leq^{w} u$ to mean $w^{-1}v\leq w^{-1}u$. If $A$ and $B$ are cosets, then $A\leq^{w} B$ means that $v\leq^{w} u$ for some representatives $v\in A$ and $u\in B$. The connection to matroids comes from the collection $\mathcal{M}$ of cosets. In our construction, $\mathcal{M}$ has the following property: if $w$ is any reflection in $W$, then there is a coset $B\in \mathcal{M}$ with the property that $A\leq^{w} B$ for all $A\in \mathcal{M}$. Now the resemblance to matroids, as axiomatised via Gale’s Theorem, is quite striking. The cosets in $\mathcal{M}$ play the role of bases in Gale’s Theorem. Now we can finally give the definition of a Coxeter matroid, which is justified by this resemblance to Gale’s axiomatization. If $W$ is a Coxeter group with $P$ as a parabolic subgroup, and $\mathcal{M}$ is a collection of cosets, then $\mathcal{M}$ is a Coxeter matroid if, for every $w\in W$, there is a coset $B\in \mathcal{M}$ such that $A\leq^{w} B$ for all $A\in \mathcal{M}$.

Too dense to measure? 

I’m back, writing more about growth rates of matroids in minor-closed classes. In the last two posts, I’ve been talking about the growth rate function $h_{\mathcal{M}}$ of a class, which measures the maximum number of elements in a simple rank-$n$ matroid in the class, or (essentially) equivalently the maximum number of points in a rank-$n$ matroid of the class, which is not necessarily required to be simple. In this post I’ll stop using the ‘function’ notation and instead just state things more explicitly for individual matroids.

The reason for this is that I’ll be writing this time about matroids whose growth rate function is infinite, but still seem ‘sparse’ compared to random matroids.  The easiest example of this is the class of bicircular matroids, which are the graph-like matroids obtained by starting from a basis B and freely extending lines spanned by pairs of elements of B any number of times. (Technically we have to close under minors also). These are the same class as the matroids having a real-representation where each column contains at most two nonzero entries and all nonzero entries are algebraically independent.

An easy observation is that a rank-$n$ bicircular matroid can have arbitrarily many points, as you can keep adding new points on any line between a pair of basis elements and stay bicircular. Therefore the class of bicircular matroids contains all simple rank-$2$ matroids and there is no bound on its growth rate function. The reason this seems like a problem, though, isn’t that we’re unhappy with matroids having unbounded numbers of points, it’s that the bicircular matroids seem intuitively quite sparse.

To make this concrete, we can make the easy observation that every rank-$n$ bicircular matroid is the union of at most $\binom{n}{2}$ rank-$2$ sets. This is an unusual property that dramatically separates bicircular matroids from random matroids, and it’s how we’ll talk about the more general notion of density this post is about.

Covering Number

If $M$ is a matroid (of rank at least $a$) and $a$ is a positive integer, then $\tau_a(M)$ will denote the minimum size of a collection of rank-$a$ sets with union $E(M)$. We call this the $a$-covering number of $M$. It is not too hard to see that if $M \cong \mathrm{PG}(n-1,q)$ then $\tau_a(M)$ is roughly $\frac{q^r-1}{q^a-1}$ and that if $M \cong M(K_n)$ then $\tau_a(M)$ is roughly $\binom{n+1}{2}/\binom{a+1}{2}$, so $\tau_a$ behaves pretty similarly to counting points for nice matroids like cliques and projective geometries. However, unlike the ‘number of points’ parameter, covering number enables us to say the bicircular matroids are only quadratically dense; if $M$ is a rank-$n$ bicircular matroid then $\tau_2(M) \le \binom{n}{2}$. This seems to do much better justice to their structure.

Given an $a$, it is still easy to construct fixed-rank matroids for which $\tau_a$ is arbitrarily large. The easiest construction is just the uniform matroid $U_{a+1,b}$. In covering such a matroid with rank-$a$ sets there isn’t anything clever you can do; all the rank-$a$ sets have just $a$ elements and in the end you need $\tau_a(U_{a+1,b}) = \left\lceil\frac{b}{a}\right\rceil$ sets to do the job. However, there is a beautiful partial converse to this statement due to Geelen and Kabell [gk09], who also introduced the parameter.

Theorem 1: If $r \ge a$ and $M$ is a rank-$r$ matroid with no $U_{a+1,b}$-minor then $\tau_a(M) \le \binom{b-1}{a}^{r-a}$.

Just like Kung’s theorem did for counting points  (see my first entry), this result provides a perfect description of which minor-closed classes have the property that $\tau_a$ is bounded above by a function of rank; they are exactly those that do not contain all rank-$(a+1)$ uniform matroids. Jim Geelen conjectured much more than this, though, in his excellent paper [g08] on excluding a uniform matroid as a minor. He postulated that the growth rate theorem almost survives the generalisation to $\tau_a$ unchanged:

Conjecture 1: If $a$ is an integer and $\mathcal{M}$ is a minor-closed class of matroids, then either

1. $\tau_a(M) \le c r(M)$ for all $M \in \mathcal{M}$;
2. $\tau_a(M) \le c r(M)^2$ for all $M \in \mathcal{M}$ and $\mathcal{M}$ contains all bicircular matroids or all graphic matroids;
3. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
4. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This conjecture, which is very probably true, is quite striking; it would tell us that  $\tau_a$-density is ‘controlled’ by geometry- or graph-like matroids in any minor-closed class for which it is not a useless measure of density. The only classes left to worry about would be the ones that contain all uniform matroids of every rank, and those are much easier than the bicircular matroids to dismiss as truly ‘wild’ or ‘infinitely dense’ classes.

Jim and I made some progress [gn12,n13] towards Conjecture 1, proving the following:

Theorem 2: Let $a$ be an integer and $\mathcal{M}$ be a minor-closed class of matroids. Either

1. $\tau_a(M) \le r(M)^c$ for all $M \in \mathcal{M}$;
2. there is a prime power $q$ so that $\tau_a(M) \le c q^{r(M)}$ for all $M \in \mathcal{M}$, and $\mathcal{M}$ contains all GF$(q)$-representable matroids; or
3. $\mathcal{M}$ contains all rank-$(a+1)$ uniform matroids.

This separates the ‘exponential’ classes from the polynomial ones. We’d really like to know more, though; the quadratic and linear part of the conjecture seems quite a lot harder.

In the meantime, it would still be great to understand the parameter $\tau_a$ in more specific settings. Here is a very concrete problem:

Problem 1: Let $M$ be a rank-$r$ $\mathbb{R}$-representable matroid with no $U_{3,6}$-minor. Find an upper bound on $\tau_2(M)$ in terms of $r$.

Theorem 1 gives an upper bound of $10^{r-2}$ and, since projective geometries are not real-representable, Theorem 2 gives $\tau_2(M) \le r^c$ for some constant $c$, but neither of these are particularly satisfactory. If Conjecture 1 holds then the answer should be quadratic in $r$, but it would be nice for it to be a quadratic with reasonable coefficients.

I also believe that, despite the non-committal constants in Theorem 2, the way that $\tau_a$ behaves in exponentially dense classes is somewhat reasonable. There are some issues when computing $\tau_a(\mathrm{PG}(r-1,q)$ when the geometry doesn’t partition neatly into nice rank-$a$ flats (the answer still turns out to be equal to the obvious lower bound), but modulo a small multiplicative factor, something like the following should be true, and possibly quite approachable by the same kind of techniques that were used in the setting of excluding a rank-$2$ minor:

Conjecture 2: If $\epsilon > 0$ and $M$ is a matroid with no $U_{a+1,b}$-minor and of sufficiently large rank, then $\tau_a(M) \le (1 + \epsilon)\tau_a(\mathrm{PG}(r(M)-1,q))$, where $q$ is the largest prime power so that $U_{a+1,b}$-is GF$(q)$-representable.

In other words, the matroids with no $U_{a+1,b}$-minor should be asymptotically no denser than the projective geometries with no $U_{a+1,b}$-minor.

See you next time!

References

[g08] J. Geelen, Some open problems on excluding a uniform matroid. Adv. in Appl. Math., 41(4):628-637, 2008.

[gk09] J. Geelen, K. Kabell, the Erdos-Posa property for matroid circuits. J Combin. Theory Ser. B, 99(2):407-419, 2009.

[gn12] J. Geelen, P. Nelson, Projective geometries in exponentially dense matroids. I,  arXiv:1209.1496 [math.CO]

[n13] P. Nelson, Projective geometries in exponentially dense matroids. II, arXiv:1306.0244 [math.CO]

Here I am again, discussing frame and lift matroids. As in my previous post, I’ll denote by $FM(\Omega)$ and $LM(\Omega)$ respectively the frame and lift matroid of $\Omega$.

Following on Jim Geelen’s post on framework matroids, I’ll discuss recognition algorithms (or lack thereof) for some classes of lift and frame matroids. Jim’s post starts with Seymour’s beautiful theorem (in [S81], Theorem 1 in Jim’s post) which, for a given matroid $M$ and graph $G$, allows one to check whether $M=M(G)$ in polynomial time. In [G92], del Greco proved the following analogue to Seymour’s theorem for frame matroids. (In the next theorem, the star of a vertex $v$ is the set of edges incident with $v$ which are not balanced loops.)

Theorem 1: Let M be a matroid and let $\Omega=(G,\mathcal{C})$ be a biased graph where $G$ is connected and has at least two vertices. Then $M=FM(\Omega)$ if and only if the following hold:

1. the star of every vertex of $G$ is a union of cocircuits of $M$,
2. every vertex-disjoint union of unbalanced cycles of $\Omega$ is not a circuit of $M$,
3. no balanced cycle of $\Omega$ is properly contained in a circuit of $M$, and
4. $r(M)\leq r(FM(\Omega))$.

Unfortunately, this theorem doesn’t lead to a polynomial time algorithm for checking if $M=FM(\Omega)$, since the number of cycles in a graph may be exponential in the number of edges. This seems to support Conjectures 1 and 2 in Jim’s post.

One may hope that the recognition algorithm problem may be more tractable when turning our attention to specific classes of frame and lift matroids. Alas, even for the well behaved class of bicircular matroids, a polynomial-time recognition algorithm does not exist, unless $P=NP$. In fact it is shown in [CCW85] that it is NP-hard to determine whether a matroid $M$ is bicircular, even if $M$ is representable and a matrix representation is given. I couldn’t actually get hold of this reference, but a strengthening of this result may be found in [CGW93]. This paper also contains a polynomial-time algorithm to determine whether a matroid (given as an independence set oracle) is the bicircular matroid of a graph that belongs to a certain family of graphs.

Rudi Pendavingh and Stefan van Zwam have devised a recognition algorithm for a special class of signed-graphic matroids. This is the class of sixth-roots-of-unity graphic matroids, i.e. matroids representable by a sixth-roots-of-unity matrix with at most two nonzero entries per column. This corresponds to the class of signed graphs with no $-K_4$- and no $\pm K_3$-minor (where $-K_4$ is $K_4$ with all cycles unbalanced and $\pm K_3$ is a $K_3$ with all edges doubled, where every pair of parallel edges forms an unbalanced cycle). Musitelli’s algorithm for recognizing binet matrices  [M07] “almost” works for the whole class of signed-graphic matroids. That is, given a real matrix representation of a matroid $M$, Musitelli’s algorithm would recognize if $M$ is signed graphic as long as the columns of the matrix have already been scaled correctly, so only row operations are needed to get a matrix with two nonzeroes entries per column (these entries being $\pm 1$).

Aside from graphic matroids, I don’t know of any other polynomial-time recognition algorithm for classes of frame matroids. The situation is just as bad for lift matroids. This lack of algorithms suggests some obvious open problems:

Problem 1: find a polynomial-time algorithm that, given a binary matroid $M$, determines whether $M$ is an even cycle matroid.

Problem 2: find a polynomial-time algorithm that, given a ternary matroid $M$, determines whether $M$ is a signed-graphic matroid.

By “given a matroid $M$” I mean that $M$ is given as a rank oracle, or a matrix or pretty much in any reasonable form. Even though I believe these problems may be solved, I’m certainly not claiming that such algorithms would be easy to find, or to implement. Let me  elaborate a bit.

Since both these classes of matroids have a finite list of excluded minors (as implied by the Matroid Minor Project), one may think of using the excluded minors to solve Problems 1 and 2. However, finding the excluded minors for these classes seems an even harder problem than finding a recognition algorithm. What about a more direct approach?

Say that you want to decide whether a given matroid $M$ is an even cycle matroid. Maybe you’d like to decompose $M$ into smaller, 3-connected pieces (as for graphic or regular matroids). Here is the first difficulty: even cycle matroids are not even closed under 1-sums. It seems reasonable to restrict our attention to 3-connected matroids, since most algorithms for recognising graphic matroids work because a 3-connected graphic matroid has only one graphical representation. This is very much not the case for even cycle and signed-graphic matroids. Thus the need for some new ideas.

One approach could be the following:

1. take a small minor $N$ of $M$;
2. since $N$ is small we can check if it is an even cycle matroid and find all of its signed graph representations;
3. we can try to “grow” each of these graphical representations of $N$ into representations of $M$.

Step 3. is not hard, as long as you keep track of the deletions and contractions to go from $M$ to $N$. The problem is that this algorithm is not polynomial in the size of $M$. The reason is that in general we cannot bound the number of signed graph representations of an even cycle matroid, so starting from the few representations of $N$ we may grow into a lot of representations of an intermediate matroid. This happens when some signed graph representation of $N$ has blocking pairs, i.e. sets of two vertices intersecting every unbalanced cycle. More precisely, suppose that $N’$ is a one-element coextension of $N$ and $N$ has a signed-graph representation $\Omega$ with a blocking pair. Then it is possible that $(G,S)$ grows into signed graphs $\Omega_1$ and $\Omega_2$ which are both representations of $M$ (by “grows into” I mean that contracting the edge in $E(N’)-E(N)$ in any of these two signed graphs produces $\Omega$). When this happens, the two new signed graphs still have blocking pairs, so this doubling of representations may happen over and over again. Similar problems arise when trying this approach on signed-graphic matroids.

References

[CCW85] V. Chandru, C.R. Coullard, and D.K. Wagner, On the complexity of recognizing a class of generalized networks, Oper. Lett. 4 (1985), 75-78.