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.

This post continues the discussion from my last post. I’m going to continue using the same notation: in particular, if $w$ is a permutation on the set $[n]=\{1,\ldots, n\}$, and $k\in \{0,\ldots, n\}$, then $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. Gale’s Theorem states that if $\mathcal{B}$ is a collection of $k$-element subsets of $[n]$, then $\mathcal{B}$ is the collection of bases of a matroid if and only if, for every permutation, $w$, of $[n]$, there exists a subset $B\in\mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.

Symplectic matroids

Symplectic matroids can be seen as a generalization of ordinary matroids obtained by removing the full symmetric group that implicitly appears in Gale’s Theorem, and replacing it with another group, namely the hyperoctahedral group, $BC_{n}$. This group consists of permutations of the set $\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$. Let $J$ denote this set. The permutation $w$ belongs $BC_{n}$ if and only if $w(-i)=-w(i)$, for every $i \in J$. We can see $BC_{n}$ as the group of symmetries of the hypercube in $\mathbb{R}^{n}$. The hypercube is the set of vectors $\mathbf{v}\in\mathbb{R}^{n}$ where every entry of $\mathbf{v}$ lies in the interval $[-1,1]$. The vertices of the hypercube are the vectors having every entry equal to $1$ or $-1$. Thus, for every $i\in\{1,\ldots, n\}$, $BC_{n}$ contains the reflection through the hyperplane consisting of all vectors with the $i$th entry equal to zero. We may also apply an arbitrary permutation of the entries. In fact, permutations of these two types generate the entire hyperoctahedral group. You might recognise that this means that $BC_{n}$ is the wreath product of the full symmetric group $\mathrm{Sym}(n)$ and the group of order two, $\mathrm{Sym}(2)$.

With the group definition out of the way, let’s define symplectic matroids. A subset of $J=\{-n,-(n-1),\ldots,-1,1,\ldots,n-1,n\}$ is admissible if it does not contain $\{i,-i\}$ for any $i\in \{1,\ldots,n\}$. If $A$ and $B$ are admissible $k$-element subsets, and $w\in BC_{n}$, then we write $A\leq^{w} B$ if, for every $i$, the $i$th element of $A$ appears no later than the $i$th element of $B$ in the sequence $w(-n),\ldots, w(-1),w(1),\ldots,w(n)$. Let $\mathcal{B}$ be a collection of admissible $k$-element subsets of $J$. If, for every permutation $w\in BC_{n}$, there is a subset $B\in\mathcal{B}$ such that $A\leq^{w}B$ for every $A\in \mathcal{B}$, then we call the set system $(J,\mathcal{B})$ a symplectic matroid.

Example 1. This example comes from an exercise in the book Coxeter Matroids. Let $\mathcal{B}$ be a family of bases of an ordinary matroid on the ground set $[n]$. If we consider $\mathcal{B}$ as a family of subsets of $J=\{-n,\ldots,1,1,\ldots, n\}$, then $(J,\mathcal{B})$ is a symplectic matroid. To see this, let $w$ be an arbitrary permutation in $BC_{n}$. Let $a_{1},\ldots, a_{s}$ be the members of $[n]$ that are fixed by $w$, and let $b_{1},\ldots, b_{t}$ be the members that are taken to their negation, where $a_{1} < a_{2} < \cdots < a_{s}$ and $b_{1}< b_{2} <\cdots < b_{t}$. Now let $w'$ be the permutation of $[n]$ that takes $1,\ldots, n$ to $b_{t},b_{t-1},\ldots, b_{1},a_{1},a_{2},\ldots, a_{s}$. By Gale's Theorem, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w'} B$ for all $A\in \mathcal{B}$. It is not difficult to see that $A\leq^{w} B$ for all $A\in \mathcal{B}$, so $(J,\mathcal{B})$ is a symplectic matroid, as claimed. Example 2. Let $\mathcal{B}$ be the collection of bases of a matroid on the ground set $\{1,\ldots, n\}$. Add the elements $\{-n,\ldots, -1\}$ to this matroid in such a way that $-i$ is either a loop, or parallel to $i$, for every $i$. Let’s say that the resulting matroid is $M$. If $\mathcal{B}$ is the set of bases of $M$, then obviously every member of $\mathcal{B}$ is admissible, considered as a subset of $J$. Because every permutation in $BC_{n}$ is also a permutation in the symmetric group of $J$, Gale’s Theorem implies that $(J,\mathcal{B})$ is a symplectic matroid.

Actually, a converse to the previous example holds. If $(J,\mathcal{B})$ is a symplectic matroid, and $\mathcal{B}$ is also the family of bases of an ordinary matroid with ground set $J=\{-n,\ldots, -1,1,\ldots, n\}$, then every basis is admissible, which means that no basis can contain a set of the form $\{i,-i\}$. Thus every set $\{i,-i\}$ is dependent, so if a symplectic matroid is also an ordinary matroid, then it arises from that ordinary matroid in the way illustrated by Example 2.

Example 3. How about an example of a symplectic matroid that can not be interpreted as a matroid? Let $J$ be $\{-2,-1,1,2\}$, and let $\mathcal{B}$ be the admissible collection $\{\{1,-2\},\{2,-1\},\{-1,-2\}\}$. This is not the set of bases of a matroid; if it were, then $\{1,2\}$ and $\{1,-1\}$ would be parallel pairs, and $\{2,-1\}$ would be a basis. Next we check that $\mathcal{B}$ is the set of bases of a symplectic matroid. Let $w$ be an arbitrary permutation of $\{-2,-1,1,2\}$ from $BC_{2}$ and consider $\{w(1),w(2)\}$. It must be one of the sets $\{1,2\}$, $\{1,-2\}$, $\{2,-1\}$, or $\{-1,-2\}$. Since $A\leq^{w}\{w(1),w(2)\}$ for every $2$-element admissible subset $A$, we are done if $\{w(1),w(2)\}$ is in $\mathcal{B}$. Therefore let us assume that $\{w(1),w(2)\}=\{1,2\}$. Now $w(-1)=-w(1)$, so $\{w(-1),w(2)\}$ is in $\mathcal{B}$, and $A\leq^{w}\{w(-1),w(2)\}$ for every $A\in \mathcal{B}$. Therefore $(\{-2,-1,1,2\},\mathcal{B})$ is a symplectic matroid, as claimed.

The authors of Coxeter Matroids define a Lagrangian matroid to be a symplectic matroid on $\{-n,\ldots,-1,1,\ldots,n\}$ consisting of $n$-element subsets. So Example 3 gave an instance of a Lagrangian matroid. In that example, $\{-1,-2\}$ is an $n$-element admissible set. The intersections of $\{-1,2,\}$ with the members of $\mathcal{B}$ are $\{\}$, $\{-1,2\}$, and $\{-1\}$. If we complete this collection downwards, by including all subsets of those listed, then we generate the family of independent sets of a matroid. This is a particular case of a theorem that appears in Coxeter Matroids: if $\mathcal{B}$ is a collection of $n$-element admissible subsets, then the set system $(J,\mathcal{B})$ is a Lagrangian matroid if and only if, for every $n$-element admissible set, $T$, the downwards completion
\[\{I\subseteq J\mid \text{there exists}\ B\in \mathcal{B}\ \text{such that}\ I\subseteq T\cap B\}\]
is the family of independent subsets of an ordinary matroid. The proof of this equivalence only seems to appear in hard-to-find sources, so I’m not sure how complicated it is. It would be interesting to see a proof; I wonder if the equivalence holds when we relax the constraint that $(J, \mathcal{B})$ is a Lagrangian matroid, and instead ask only that it is a symplectic matroid.

Next time I’ll wrap up by talking about Coxeter matroids and their connections to algebraic geometry.