Matroid Computation with Sage: comparing matroids

I’m back with more on matroid computation in Sage. Previous installments are here, here, and here. As in the previous post, clicking the “Evaluate” buttons below will execute the code and return the answer. The various computations are again linked, so execute them in the right order.

Today we will look at various ways to ask (and answer) the question “Are these two matroids equal?” There are some subtle aspects to this, since we had to balance efficiency of the code and mathematical interpretation. The result is that we have various ways to compare matroids.

Isomorphism

Matroids $M$ and $N$ are isomorphic if there is a bijection $\phi: E(M) \to E(N)$ mapping bases to bases and nonbases to nonbases. In Sage, we check this as follows:

In other words, every matroid in Sage has a method .is_isomorphic() taking another matroid as input and returning True or False. Currently there is no way to extract the actual isomorphism (it is on our wish list), but if you guessed one, you can check its correctness:

We defined $\phi$ using a dictionary: for instance, phi['c'] equals 2. If you defined your map differently (e.g. as a function or a permutation), Sage will probably understand that too.

Equality

Matroids $M$ and $N$ are equal if $E(M) = E(N)$ and the identity map is an isomorphism. We can check for equality as follows:

==

The standard way to compare two objects in Sage is through the comparison operator ==. For instance,

When writing the matroid code, we chose to interpret the question M == N to mean “Is the internal representation of the matroid $M$ equal to the internal representation of $N$?” This is a very restricted view: the only time M == N will return True is if

  • $M$ and $N$ have the same internal data structure (i.e. both are of type BasisMatroid or both are of type LinearMatroid or …)
  • $M$ and $N$ are equal as matroids
  • The internal representations are equivalent (this is at the moment only relevant for linear matroids).

Let’s consider a few examples:

So only matroids $M_1$, $M_2$, and $M_4$ pass the equality test. This is because they are all linear matroids over the field $\mathrm{GF}(2)$, have the same ground set, and the matrices are projectively equivalent: one can be turned into the other using only row operations and column scaling. Matrix $M_3$ is isomorphic to $M_1$ but not equal; matroid $M_5$ is represented over a different field; matroid $M_6$ is represented by a list of bases, and matroid $M_7$ is represented by a list of “circuit closures”.

This notion of equality has consequences for programming. In Python, a set is a data structure containing at most one copy of each element.

So $S$ actually contains $M_3, M_5, M_6, M_7$, and one copy of $M_1, M_2, M_4$.

This means, unfortunately, that you cannot rely on Python’s default filtering tools for sets if you want only matroidally equal objects, or only isomorphic objects. But those equality tests are way more expensive computationally, whereas in many applications the matroids in a set will be of the same type anyway.

Inequivalent representations

As mentioned above, each instance of the LinearMatroid class is considered a represented matroid. There are specialized methods for testing projective equivalence and projective isomorphism. Recall that matroids are projectively equivalent (in Sage’s terminology, field-equivalent) if the representation matrices are equal up to row operations and column scaling. So below, matroids $M_1$ and $M_3$ are field-equivalent; matroids $M_1$ and $M_4$ are field-isomorphic; and matroid $M_2$ has an inequivalent representation:

I probably caused a lot of confusion, so feel free to ask questions in the comments below. Also, the documentation for the functions discussed above gives more explanations and examples.

An advertisement

Hi everyone,

Since Jim’s entries have been on other topics, I thought I’d take advantage of his modesty and use this entry to direct people’s attention to what I consider a very important paper he recently wrote with Bert Gerards and Geoff Whittle:

‘The highly connected matroids in minor-closed classes’,

This paper will appear in the special issue of Annals of Combinatorics for James Oxley, but currently can be found at http://arxiv.org/abs/1312.5012 .

The paper is the first to put in writing some of the amazing structure theorems for $\mathrm{GF}(q)$-representable matroids that the authors have proved on their way to Rota’s conjecture. The theorems aren’t proved in the paper, nor stated in their full generality; however, they are stated for the important special cases of highly vertically connected matroids. Incredibly, the authors give (among other things) an exact structure theorem for all sufficiently highly connected matroids in an arbitrary minor-closed class of $\mathrm{GF}(q)$-representable matroids.

Even though the high connectivity simplifies the structure theorem statements enormously, there are still some technical aspects. Nonetheless, I think this paper should give the community an important head-start on proving some theorems, in a way I will try to explain by sketching a proof of a conjecture in the paper that Stefan van Zwam and I recently came up with. Our write-up is mostly done and should be on the arxiv in the next few weeks.

The discussion in this post won’t use the ‘exact’ results stated in section 4, merely the more digestible ‘qualitative’ ones in section 3. First, here is Theorem 3.1 in the paper, stated for binary matroids. (We’ll stick with binary in this post.)

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

Here, a rank-$(\le t)$ perturbation of a binary matroid $N$ means a matroid of the form $M(A + T)$, where $A$ and $T$ are binary matrices such that $M(A) \equiv N$ and $T$ has rank at most $t$.

To get a feel for this theorem, consider the class of regular matroids, where it holds for $k = 5$ and $t = 0$; ie. the vertically $5$-connected regular matroids are either graphic or cographic. For general classes, the highly connected matroids are a bounded perturbation of graphic or cographic (as opposed to exactly (co)graphic), but this is often good enough to prove theorems.

The result we will prove is Conjecture 6.1 from the paper.. In the paper we’re writing, we have to make a bit of a song and dance about the exact correspondence between linear codes and matroids, but I’ll make this as brief as possible, just talking in terms of matroids.

We say a class $\mathcal{M}$ of binary matroids is asymptotically good if there exists $\delta > 0$ and a sequence $M_1,M_2, \dotsc, $ of matroids in $\mathcal{M}$ of increasing size such that for each $i$ the matroid $M_u$ satisfies $|M_i| \ge (1+\delta)r(M_i)$ and has no circuit of size less than $\delta |M_i|$. (Loosely, in coding theory terms, this corresponds to a sequence of codes of increasing size, all having reasonably large rate and minimum distance). The class of all binary codes is asymptotically good; choosing each $M_n$ to correspond to a random $n \times n$ binary matrix will work. On the other hand, Kashyap [3] proved the following:

Theorem 2: The classes of graphic and cographic matroids are not asymptotically good.

Our result generalises this to all proper minor-closed classes.

Theorem 3: No proper minor-closed class of binary matroids is asymptotically good.

Proving Theorem 3

Our goal is to prove Theorem 3 from Theorem 1. We do this in three steps, which together are a broad template for using the structure theorems in other ways, even though what I am discussing is going towards a specific result. The basic idea is this: suppose that we want to to prove that all large matroids in a proper minor-closed classes of binary matroids have property P. For all integers $t$ and $k$, we do the following:

  1. Prove that it suffices to prove Theorem X for the subclass of vertically $k$-connected matroids in $\mathcal{M}$.
  2. Prove a strong version of Theorem X for graphic and cographic matroids; call this Theorem Y.
  3. Using Theorem Y, prove that Theorem X holds for the rank-$(\le t)$ perturbations of graphic and cographic matroids.

Together with Theorem 1, these steps imply that Theorem X holds for $\mathcal{M}$. – I’ll leave that deduction as an exercise. In our case, Theorem X is the statement that the class $\mathcal{M}$ is asymptotically good.

Step 1: Connectivity reduction
First, we bootstrap our way up to vertical $k$-connectivity via the following Lemma.

Lemma 4: Let $k$ be an integer. If $\mathcal{M}$ is asymptotically good, then so is the class of vertically $k$-connected matroids in $\mathcal{M}$.

This involves thinking about how very small separations in a matroid interact with small circuits. Like with most of these things, the numbers are fiddly, but in the end small vertical separations ought not to show up in a ‘best’ sequence certifying asymptotic goodness of $\mathcal{M}$, and the numbers bear this out. Now on to the next step…

Step 2: Graphic and Cographic

We saw earlier that Kashyap proved that the graphic and cographic matroids are not asymptotically good classes. We need something stronger, though: a result that can survive a perturbation. What we prove is the following:

Lemma 5: If $M$ is a graphic or cographic matroid with $|M| \ge (1+\delta)r(M)$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X| – 2t$ and $|X| = O(\log r(M))$.

The cographic case is very easy (the associated graph has constant average degree, so just take the union of a collection of small stars). The graphic case follows from a result of Alon, Hoory and Linial [1] which finds a single circuit of logarithmic size – if we apply this $(2t+1)$ times after removing the circuits successively, we get our required set. Finally…

Step 3: Surviving a perturbation

We constructed Lemma 5 to still give us a result when $M$ is perturbed. The following is an easy exercise:

Lemma 6: If $M$ is a rank-$(\le t )$ perturbation of $M’$, then $|r_M(X) – r_{M’}(X)| \le 2t$ for each $X \subseteq E(M)$.

From this and Lemma 5 (and a tiny bit of fudging with changing the rank of the matroid), we get what we want:

Lemma 7: If $M$ is a rank-$(\le t)$ perturbation of a graphic or cographic matroid and $|M| \ge (1+ \delta)|M|$, then there is a set $X \subseteq E(M)$ with $r_M(X) < |X|$ and $|X| = O(\log r(M))$.

And now we’re done – here’s the argument. Suppose that $\mathcal{M}$ is an asymptotically good minor-closed class of binary matroids. Let $k$ and $t$ be the integers given by Theorem 1. By Lemma 4, the class of vertically $k$-connected matroids in $M$ is asymptotically good. By Theorem 1, every such matroid is a rank-$(\le t)$ perturbation of graphic or cographic. By Lemma 7, any such matroid with $|M| \ge (1+ \delta)r(M)$ contains a dependent set of logarithmic size; this contradicts the definition of asymptotic goodness.

I hope this post has given you some idea of the power of the structure theorems in this paper. Being able to apply our knowledge of graphic and cographic matroids to arbitrary minor-closed classes of binary matroids is a huge boon, one that certainly deserves our attention. I haven’t even discussed nonbinary matroids or the exact structural results – maybe I’ll get to the latter in my next post. Until then, I’ll see you round!

[1] N. Alon, S. Hoory and N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18 (2001), 53-57.

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

[3] N. Kashyap, A decomposition theory for binary linear codes, IEEE Transactions on Information Theory 54 (2008), 3035-3038.

Which biased graphs are group-labelled graphs?

This post is mainly about results that I proved together with Matt DeVos and Daryl Funk, partly while they were visiting the University of Western Australia after the 37ACCMCC (Dillon talked about this conference in his blog post on December 16, 2013).

First, let me remind you of what a biased graph is (more details can be found in my introductory post). A biased graph is a pair $(G,\mathcal{B})$, where $G$ is a graph and $\mathcal{B}$ is a set of cycles of $G$ satisfying the theta-property: there is no theta subgraph of $G$ that contains exactly two cycles in $\mathcal{B}$. Cycles in $\mathcal{B}$ are called balanced, while the other cycles of $G$ are unbalanced.

A quite general way of constructing biased graphs is via group-labelled graphs. Pick your favourite (say multiplicative) group $\Gamma$ and graph $G$, and assign to each edge $e$ of $G$ an orientation and a value $\phi(e)$ from $\Gamma$: then what you have is a group-labelled graph. Now consider any walk $W$ in $G$, with edge sequence $e_1,e_2,\ldots,e_k$ and extend $\phi$ as

$\phi(W)=\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}$,

where $\textrm{dir}(e_i)$ is 1 if $e_i$ is forward in $W$, and -1 otherwise. Then we define a cycle $C$ of $G$ to be balanced if a simple closed walk $W$ around $C$ has $\phi(W)=1$. It’s easy to see that this definition is independent of the choice for $W$, and in this way we get, indeed, a biased graph. In this case we identify the group-labelled graph with the associated biased graph. If a biased graph can be constructed in this way from a group $\Gamma$, then we say that such a biased graph is $\Gamma$-labellable. If a biased graph is $\Gamma$-labellable for some group $\Gamma$, then we say that the biased graph is group-labellable. Not all biased graphs are group-labellable, hence the question that is the title of this post. As it turned out, there is a nice topological answer to this question.

Theorem 1: Let $(G,\mathcal{B})$ be a biased graph; construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for every $C \in \mathcal{B}$. Then the following are equivalent:

  1. $(G,\mathcal{B})$ is group-labellable.
  2. $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
  3. Every unbalanced cycle of $G$ is noncontractible in $K$.

Before I explain a bit how the proof works, let me discuss some nice constructions that we derived using this theorem. For any group $\Gamma$, the class of $\Gamma$-labellable graphs is closed under minors, for both definition of minors given in my second post on biased graphs. Using Theorem 1, we proved that if $\Gamma$ is an infinite group then there are infinitely many excluded minors to the class of $\Gamma$-labellable biased graphs. In fact, we proved something stronger, namely that there is an infinite list of excluded minors on $n$ vertices for every $n \geq 3$.

Theorem 2: For every $n \geq 3$ and $\ell$ there exists a biased graph $(G,\mathcal{B})$ with the following properties:

  • $G$ is a graph on $n$ vertices and every pair of vertices is joined by at least $\ell$ edges.
  • $(G,\mathcal{B})$ is not group-labellable.
  • For every infinite group $\Gamma$, every proper minor of $(G,\mathcal{B})$ is $\Gamma$-labellable.

For a group $\Gamma$, let $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ denote the class of frame and lift matroids respectively that arise from $\Gamma$-labelled graphs. From Theorem 2 (and a one-page argument) we also show that

Theorem 3: For every infinite group $\Gamma$ and every $n \geq 3$ the classes $\mathcal{F}_{\Gamma}$ and $\mathcal{L}_{\Gamma}$ have infinitely many excluded minors of rank $n$.

Theorem 3 implies in particular that frame and lift matroids are not well-quasi ordered. This was already known, since swirls and spikes form infinite antichains of, respectively, frame and lift matroids (see [GGW02] and [M05]). As far as I know, however, it wasn’t known that there are infinite antichains of frame and lift matroids all of the same rank.

I’ll conclude the post by mentioning the two main ingredients for the proof of Theorem 1. The first main part of the proof consists of expressing $\pi_1(K)$ in the appropriate way. Let $\gamma_e$ be a variable associated with every edge in $G$. We use an application of Van Kampen’s Theorem (see Hatcher’s book on algebraic topology), to express $\pi_1(K)$ as the group presented by the generating set $\{\gamma_e | e \in E(G)\}$, with the relations given by setting

$\prod_{i=1}^{k}\phi(e_i)^{\textrm{dir}(e_i)}=1$,

for each balanced cycle $C$ and any closed walk $W$ around $C$ with edge sequence $e_1,\ldots,e_k$. This allows us to show that (3) implies (2).

The second ingredient of the proof involves reroutings. Consider a closed walk $W$ containing a path $P$, and a balanced cycle $C$ containing $P$. Let $P’$ be the complement of $P$ in $C$; then the walk $W’$ obtained by from $W$ by replacing $P$ with $P’$ is obtained by rerouting along the balanced cycle $C$. If in the previous definition $W$ and $W’$ are both simple walks around a cycle, then the theta property implies that $W$ is balanced if and only if $W’$ is balanced. However, if we start with a simple closed walk $W_1$ around a cycle, we do a series of reroutings and we end with a simple closed walk $W_k$ around a cycle, then knowing the bias of $W_1$ doesn’t tell us anything about the bias of $W_k$, since the intermediate closed walks in the sequence of reroutings may not be simple closed walks around a cycle. However, things are different for group-labelled graphs.

Suppose that $(G,\mathcal{B})$ is a group-labelled graph (so every edge $e$ of $G$ has an orientation and a value $\phi(e)$ from some group $\Gamma$). Consider the extension of $\phi$ to closed walks of $G$, as above. If a closed walk $W’$ is obtained from a closed walk $W$ by rerouting along a balanced cycle, then $\phi(W)=\phi(W’)$ (because $C$ is balanced, so $\phi(P)=\phi(P’)$ in the definition of rerouting). So if $(G,\mathcal{B})$  is group-labelled, then we can never start from a simple closed walk around a balanced cycle and obtain (via reroutings) a simple closed walk around an unbalanced cycle. That is, any biased graph $(G,\mathcal{B})$ that is group-labellable satisfies the following:

4. There does not exist a sequence $W_1,W_2,\ldots,W_k$ of closed walks such that each $W_{i+1}$ is obtained from $W_i$ by rerouting along a balanced cycle and $W_1$ is a simple walk around a balanced cycle and $W_k$ is a simple walk around an unbalanced cycle.

By the argument above, (1) in Theorem 1 implies (4). Using the fundamental group of $K$ we can show that if (3) fail then (4) fails (so (4) implies (3)).

References

[GGW02] J. Geelen, A.M.H. Gerards, and G. Whittle, Branch-Width and Well-Quasi-Ordering in Matroids and Graphs, J. Combin. Theory Ser. B 84 (2002), 270-290.

[M05] D. Mayhew, Inequivalent Representations of Bias Matroids, Combinatorics, Probability and Computing 14 (2005) 567-583.

Google Summer of Code 2014

Google’s Summer of Code is an annual event in which Google will pay a bunch of students to spend the summer writing code for open-source projects.

As last year, Sage is one of the mentoring organizations, and as last year, we are hoping to have one of about 4 students work on Sage’s matroid capabilities. We are looking for an undergraduate or graduate student who

  • Knows a bit of matroid theory (some possible topics require more knowledge than others)
  • Has some programming experience, preferably in Python
  • Wants to work on building exciting mathematics software for 3 months during the summer
  • Would like the word “Google” on his or her CV
  • Is interested in earning 5500 US dollars and a t-shirt

On the ideas page, a list of possible features to work on can be found. Students must produce a detailed proposal including a timeline with milestones. Early interaction with the mentors is important: we want to know you’re serious about this, and able to deliver. The place for this is the sage-gsoc Google group.

If you know an interested student, send her or him to this post. If you are an interested student, study the links above to figure out the requirements, timeline, etc. One important date: applications must be in on

MARCH 21

and we’d like to start working on the proposal with you well before then.