Google Summer of Code is a program where Google pays students to work on open-source software during the summer.

Once again, SageMath has been selected as a mentoring organization for the Google Summer of Code. We’ve had students work on aspects of the Matroid Theory functionality for the past four years. Maybe this year, YOU can join those illustrious ranks! Check out the call for proposals and ideas list. Read the instructions on both pages carefully. Applications open on March 12, so it’s a good idea to start talking to potential mentors and begin writing your proposal!

]]>In the summer, I have extended the SAGE code base for matroids for Google Summer of Code. This post shows a few example of it’s new capabilities.

Let $M$ be a matroid with groundset $E$ and rank function $r$. A partition of the groundset $\{E_1,E_2\}$ is a $m$-separation if $|E_1|,|E_2|\geq m$ and $r(E_1)+r(E_2)-r(E)\leq m-1$. $M$ is called $k$-connected if there is no $m$-separation for any $m < k$. The Fano matroid is an example of $3$-connected matroid.

The Fano matroid is not $4$-connected. Using the `certificate=True`

field, we can also output a certificate that verify its not-$4$-connectness. The certificate is a $m$-separation where $m < 4$. Since we know Fano matroid is $3$-connected, we know the output should be a $3$-separation.

We also have a method for deciding $k$-connectivity, and returning a certificate.

There are 3 algorithms for $3$-connectivity. One can pass it as a string to the `algorithm`

field of `is_3connected`

.

`"bridges"`

: The $3$-connectivity algorithm Bixby and Cunningham. [BC79]`"intersection"`

: the matroid intersection based algorithm`"shifting"`

: the shifting algorithm. [Raj87]

The default algorithm is the bridges based algorithm.

The following is an example to compare the running time of each approach.

The new bridges based algorithm is much faster than the previous algorithm in SAGE.

For $4$-connectivity, we tried to use the shifting approach, which has an running time of $O(n^{4.5}\sqrt{\log n})$, where $n$ is the size of the groundset. The intuitive idea is fixing some elements and tries to grow a separator. In theory, the shifting algorithm should be fast if the graph is not $4$-connected, as we can be lucky and find a separator quickly. In practice, it is still slower than the optimized matroid intersection based algorithm, which have a worst case $O(n^5)$ running time. There might be two reasons: the matroid intersection actually avoids the worst case running time in practice, and the shifting algorithm is not well optimized.

There is a new implementation of matroid intersection algorithm based on Cunningham’s paper [Cun86]. For people who are familiar with blocking flow algorithms for maximum flows, this is the matroid version. The running time is $O(\sqrt{p}rn)$, where $p$ is the size of the maximum common independent set, $r$ is the rank, and $n$ is the size of the groundset. Here is an example of taking matroid intersection between two randomly generated linear matroids.

Using matroid intersection, we have preliminary support for matroid union and matroid sum. Both construction takes a list of matroids.

The matroid sum operation takes disjoint union of the groundsets. Hence the new ground set will have the first coordinate indicating which matroid it comes from, and second coordinate indicate the element in the matroid.

Here is an example of matroid union of two copies of uniform matroid $U(1,5)$ and $U(2,5)$. The output is isomorphic to $U(4,5)$.

One of the application of matroid union is matroid partitioning, which partitions the groundset of the matroid to minimum number of independent sets. Here is an example that partitions the edges of a graph to minimum number of forests.

I would like to thank my mentors Stefan van Zwam and Michael Welsh for helping me with the project. I also like to thank Rudi Pendavingh, who have made various valuable suggestions and implemented many optimizations himself.

[BC79] R.E Bixby, W.H Cunningham. *Matroids, graphs and 3-connectivity*, J.A Bondy, U.S.R Murty (Eds.), Graph Theory and Related Topics, Academic Press, New York (1979), pp. 91-103.

[Raj87] Rajan, A. (1987). *Algorithmic applications of connectivity and related topics in matroid theory*. Northwestern university.

[Cun86] William H Cunningham. 1986. *Improved bounds for matroid partition and intersection algorithms*. SIAM J. Comput. 15, 4 (November 1986), 948-957.

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.

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.

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.

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.

]]>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

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

]]>Once again, the code examples can be run, as well as edited. The cells are linked together, so execute them in order.

A linear matroid is easily defined from a representation matrix:

Ok, so this matroid is over the field $\mathbb{Q}$. What if I want a different field? There are two places to specify that, either in the Matroid() or in the Matrix() function:

Even more concise, we can squeeze the matrix definition into the matroid definition. The second line prints the representation, along with column labels.

Like last time, let’s start by generating all linear extensions:

Note that, different from last time, we immediately get a list of matroids, instead of a generator. That might change in the future, though! Let’s examine our list of extensions a little.

There are a few options built into the method to restrict the output. First, we can request only simple extensions:

Second, we can request only extensions that are spanned by a specific subset $F$:

Our third option deserves its own heading.

A while a go, I started writing about partial fields. Sage has support for them built in, with some caveats: fields of fractions are very unreliable (because of hashing reasons). This will be fixed in some future release of Sage, see this bug report. We will use a partial field that’s safe, the *dyadic* partial field. For a number of others, you can use the product ring code I listed here (with a more advanced version, supporting loading and saving, in a forthcoming technical report that’s currently on hold on arXiv.org).

The key to the world of partial fields in sage is the set of *fundamental elements*: given a partial field $\mathbb{P} = (R, G)$, the set of fundamental elements is $\{1\} \cup \{x \in G : 1 – x \in G\}$. These can be used to generate $\mathbb{P}$-matrices (I’ll talk about the theory some other time) as follows:

We can test whether each of these is a valid dyadic matroid, as follows:

Sometimes you may not want to see the matroids, but rather just the new vectors that define the extensions. Sage can give you those!

Read this as follows: if the chain is $\{a: 1, b: 2, d:1\}$, the new column is obtained by adding $1$ times the column labeled by $a$, $2$ times the column labeled by $b$, and $1$ times the column labeled by $d$. The advantage of this representation, rather than just a vector, is that it is independent of row operations on the representation matrix.

To convert a chain, or just a column vector, into an extension, use the linear_extension method:

To get all linear matroid over a specific field or partial field, we can easily modify the code from the last post. Two caveats:

- We replace is_isomorphic by is_field_isomorphic. That way we get one representative of each representation of the matroid. Of course, this isn’t an issue until $\text{GF}(4)$. To get non isomorphic matroids, you’ll have to post-process the resulting list.
- The method we used for canonical ordering is not available for linear matroids. Instead, we use a method called _weak_partition, and check if the new element is in the last part.

And this prints the counts (in a slightly different form from last time — each line lists the number matroids of a fixed size, broken down by rank):

- Modify the above to generate all dyadic matroids.
- Find out the dual version of all methods discussed above. Try to understand what a cochain is.

The topic for today is matroid extensions.

It is very straightforward to generate all extensions of a fixed matroid. In this example, we specified the name of the new element to be ‘x’. If we hadn’t done that, the code would have chosen an arbitrary, previously unused, name for the new element.

**Aside: **The output looks strange; this is because we are provided with an *iterator*. This is a very nice feature of the Python language on which Sage was built: it is possible for code to construct the next item in a list of items only when that item is requested. This can have serious memory benefits. Suppose there are two billion gizmos, but you’re only interested in the 753 green ones. If you first generate the list of all gizmos, and then filter out the ones you need, you’ll have two billion of them stored in your computer’s memory halfway through the computation. If, instead, you generate them one by one and only keep the ones you want, you’ll never have more than 754 of them in memory.

In this case, the list of extensions is quite manageable, so let’s keep them all. I’ll recycle the variable name `S`

.

Let’s filter the list. Suppose we are only interested in the extensions that are simple:

Next, suppose we are only interested in the pairwise nonisomorphic matroids in this set. This is, in fact, such a common request that Sage has a built-in function for it. To get it, we import the advanced functionality:

This answer makes sense: we can place the new element ‘x’ either freely in the span of $F_7$, or freely on one of the lines of $F_7$. Note that each of these has a 5-point line minor:

In view of Peter’s posts on growth rates, it makes sense to investigate matroids with no long line minors. As it happens, Sage has an option for that:

A basic algorithm to generate all matroids of rank $r$ and corank at most $c$ is the following:

Let’s see how much time it costs to generate all matroids of up to 7 elements:

If we generate all matroids up to 8 elements in this way, it will take about 25 seconds, and you’d better not attempt 9 elements. The real time-killer here is the `get_nonisomorphic_matroids`

function, which does a number of isomorphism tests that is quadratic in the length of its input. In the generation of combinatorial objects, we often try to cut down on this by way of a **canonical labeling**. For each matroid extension, we compute a matroid invariant in which some elements are distinguished. Suppose $M$ is a single-element extension of $N$. If the new element $e$ of $M$ is not distinguished, then we know that there exists a different matroid, $N’$, such that an extension of $N’$ is isomorphic to $M$, and has been (or will be) generated in another stage of the algorithm. In that case we need not even add $M$ to the temporary list!

There is a slight complication: if $M$ contains coloops, then the only distinguished elements are the coloops! To get all matroids, then, we must change the order of generation. The matroids of rank $r$ and corank $c$ are created by adding a coloop to each matroid of rank $r-1$ and corank $c$, and by extending the matroids of rank $r$ and corank $c-1$.

In fact, this code is fast enough to generate all matroids up to 8 elements. On the Sage cell server, this should take under 7 seconds; the entry in position $(r,c)$ of the table is the number of nonisomorphic matroids of rank $r$ and corank $c$.

If you want 9 elements, be prepared to wait for much, much longer (2 days should do it). I advise you to run it from your own computer, and then save the result to disk through the command `save(MM, "/path/to/filename.sobj")`

. Next time you need them, just load them back through `MM = load("/path/to/filename.sobj")`

.

That’s all I want to say about general extensions for now. Sage has more advanced functionality in the `sage.matroids.extension`

package; some documentation is here. A more optimized algorithm to find all matroids can be found in this file (time to build all matroids up to 9 elements: about half an hour).

Suppose, next, that you don’t want just any extension, but you have more information. This information could be of the form “the new element needs to be in the span of the following subsets”. If so, you’re in luck: Sage has support for that. In the next example, since $a,b$ are in the closure of both specified subsets (as can be checked), every extension, such that $i$ is in the closure of each specified set, must place $i$ on the line through $a$ and $b$.

How does this work? Well, extensions are defined by modular cuts. The set of hyperplanes of a modular cut is called a *linear subclass*, and internally Sage works with linear subclasses. When you provide a collection of subsets, Sage will find all modular cuts containing the closures of these sets, and work from there. You can compute the smallest modular cut generated by these sets as follows:

Let me conclude this blog post with some homework. I think I’ve presented pretty much all necessary ingredients above.

**Exercise: ** Write a function to generate all frame matroids of specified rank and maximum size.

Next time, I plan to look at linear extensions and partial fields.

]]>This is the culmination of 2 1/2 years of work by Rudi Pendavingh and myself, with further help from Michael Welsh and Gordon Royle. In this post I’m going to demonstrate why you should be as excited as we are.

From the Sage homepage:

Mission: *Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab*.

There are several ways to interact with Sage:

- Download and install it on your own computer
*.*There are plenty of installation instructions available. - Use Sage online, through the Sage Notebook
*(runs version 5.11, without the matroids, and is down at the time of writing).* - Use Sage online, through the SageMathCloud
*.*

The third option is the fastest way to get started. To get an idea what Sage is capable of, look at the considerable documentation on the Sage website (including a tour, a tutorial, and much more).

Matroid computation is not new. I have a list of previous efforts on these slides, and currently the most widely used software is Petr Hliněný’s MACEK. It is very powerful when it can already do what you want, but its functionality has its bounds, and it is very hard to teach it new tricks. Moreover, the original author no longer supports it.

To avoid ending up with the same fate, we wanted to tie our efforts in with other open-source software. GAP and Sage were the obvious candidates, with Sage winning out because 1) it *includes *GAP, and 2) Sage appeared to have a more suitable programming language.

Sage gives us a big developer community, regular updates that are tested on many different systems, a bug tracker, a question-and-answer site (be sure to add the “matroid” tag to your questions), a support newsgroup, and did I mention extensive documentation? Like the Matroid Theory part of the Reference Manual.

The best way to get to work with the software is to “get your hands dirty”: install it, run it, and experiment, with the Reference Manual at hand. To get you going, I include a few examples of the capabilities below. Lines starting with “sage: ” or “….:” are input, and other lines are output. Anything from a # symbol to the end of the line is a comment. Let’s get started with a theorem:

**Theorem. **The Fano matroid, $F_7$, is a splitter for the class of matroids with no $U_{2,5}$-, $U_{3,5}$-, and $F_7^*$-minors.

*Proof. *By Seymour’s Splitter Theorem, we only need to inspect the single-element extensions and coextensions. And since $F_7$ is 3-connected, a single-element extension is 3-connected if and only if it is simple, and a single-element coextension is 3-connected if and only if it is cosimple.

sage: F7 = matroids.named_matroids.Fano() sage: U25 = matroids.Uniform(2,5) sage: U35 = matroids.Uniform(3,5) sage: F7d = F7.dual() sage: S = [U25, U35, F7d] sage: Ext = F7.extensions() sage: print [M for M in Ext if M.is_simple() and not ....: any(M.has_minor(N) for N in S)] [] sage: CoExt = F7.coextensions() sage: print [M for M in CoExt if M.is_cosimple() and not ....: any(M.has_minor(N) for N in S)] []

The two lines containing “[ ]” are output. They show that the lists we just constructed are empty, and the result is proved. $\square$

What happened here? In the first three lines, we assigned easy names to several built-in matroids. To get to the built-in matroids, you can type “matroids.” in Sage (note the dot), and hit the TAB key. Likewise, typing “matroids.named_matroids.” and hitting TAB will bring up the list of named matroids. For help, you can always type the name of an object or function followed by “?”, and hit the TAB key (note: in all these examples, do not hit ENTER at any point). For instance, typing

F7?

will print this section of the reference manual.

Each matroid has many methods associated with it. For instance, in the fourth line of our example, we compute the dual of $F_7$. And in the sixth line we compute the single-element extensions. Similar to before, to get a list of all methods you can type

F7.<TAB>

and to get help for any method, type

F7.contract?<TAB>

Easy! The remaining lines show off some aspects of the programming language underlying Sage, Python. It has a very pleasant, mathematical syntax, with excellent support for working with lists and sets of objects.

Let’s look at some more examples. At this point, there is no built-in method to compute the lattice of flats of a matroid. But it is very straightforward to implement this (I spent more time hunting through the documentation on Sage’s posets than on writing the code):

sage: def lattice_of_flats(M): ....: F = [] ....: for i in range(M.rank()+1): ....: F.extend([frozenset(X) for X in M.flats(i)]) ....: P = Poset((F, lambda x, y: x <= y)) ....: return P ....: sage: lattice_of_flats(F7).plot()

This will yield the following picture (which could be improved, of course):

The first line of this code indicates that we are defining a function with one input, $M$. We use that “M.flats(i)” returns the set of all flats of a matroid $M$ rank $i$. By calling this method for each $i$, doing a little conversion on the output, and gluing the resulting list onto the end of $F$, we make $F$ equal to the list of *all *flats of $M$. Then we create a poset with a custom partial order, using that Python’s built-in “frozenset” type uses set inclusion as the interpretation of its “<=” operator. The “lambda” notation means we have an inline function taking two inputs, $x$ and $y$. This is another standard Python feature.

Finally, let’s verify for one example that the weight enumerator of a linear code is an evaluation of the Tutte polynomial:

For linear codes, the Weight Enumerator is an evaluation of the Tutte Polynomial of the corresponding matroid. Example:

sage: C = HammingCode(3, GF(3)) sage: x, y = var('x,y') sage: p = C.weight_enumerator('xy') sage: M = matroids.PG(2,3).dual() sage: t = M.tutte_polynomial(x,y) sage: u = t.substitute({x: 3*y/(x-y)+1, ....: y: (x-y)/y+1 }) * y^3 * (x-y)^10 sage: q = u.full_simplify() sage: p - q 0

This example also shows Sage’s capabilities for symbolic math. The two variables $x$, $y$ are declared as symbols, and we can use them in polynomials and other functions.

Unfortunately, it also shows that Sage, because it is so big and has so many developers, does not always have a consistent interface. The syntax for the weight enumerator differs from that of the Tutte polynomial.

I didn’t show off the powerful isomorphism tests, the additional capabilities that linear matroids bring to the table, or how to define your own matroids. The latter is pretty easy. In most cases, just use the “Matroid” function, which accepts a variety of inputs:

sage: G = graphs.PetersenGraph() sage: M = Matroid(G) sage: M Regular matroid of rank 9 on 15 elements with 2000 bases

I invite you to give Sage, and its matroid functionality in particular, a try! Make sure to let us know what you accomplish with the code, and what you would like to see added. As for me, together with Carolyn, Deb, and Dillon, I hope to finish a first research paper that uses Sage computations in the next few weeks.

*edited on October 15 to reflect that SageMathCloud runs Sage 5.12 now.*

Henry featured prominently in the early history of matroid theory, and his name will be familiar to those acquainted with matroid enumeration. He, along with coauthors John Blackburn and Denis Higgs, was the first to use a computer to count and catalogue matroids. Their article, published in 1973, describes a catalogue of all 1095 simple matroids with up to eight points. Incidentally, my proudest mathematical possession, given to me by Dominic Welsh, is a copy of the technical report by Henry and his coauthors. The cover is a thing of intricate beauty:

In case you can’t see, this is actually a piece of text. It says ‘The Henry Crapo Group presents the incredible catalogue of 8 point geometries: see single element extensions grow before your eyes’.

Henry now lives in the small French village of La Vacquerie-et-Saint-Martin-de-Castries, about an hour’s drive north of Montpellier. His house is a large villa, which he has fitted out with all the equipment needed for a small mathematics workshop. In the last week of June, about a dozen matroid theorists descended. As was the case in 2011, when he held his last meeting, Henry delved deep into his wine cellar, and brought in his friend Samuel to provide two home-cooked meals a day. When describing this arrangement to friends and family, it’s hard not to detect a note of envy (resentment, even?). What they don’t realise is that, although we may be averaging ten courses of food and one bottle of wine per person per day, we manage to get a fair bit of mathematics done.

In between picnics, of course.

Now that I reread Gordon Royle’s description of Henry’s 2011 meeting, I see he had the same experience that we did while driving in central Montpellier. Online maps seem to ignore one-way markings (which are ubiquitous), and also indicate the existence of many streets that, in the off-line world, are solely the reserve of trams. We had a merry time getting to our hotel. Stick to public transport is my recommendation.

One of the major themes of the 2013 meeting was the ongoing sage-matroids project, appropriately enough, given Henry’s position in the history of matroid computation. The project was initiated after a meeting in Wellington in 2010, and has been steaming along since. Rudi Pendavingh and Stefan van Zwam (with contributions from Gordon Royle and Michael Welsh) have done a massive amount of work on an addition to the open-source mathematics package sage. The package is now very useable; I regularly rely on it in my research. No doubt Stefan will have more to say about the package in a future post.

I will attach slides from some of the talks at the end of this post, but let me mention one seminar that quite nicely relates to Henry’s role in the development of matroid theory. Rudi Pendavingh, alongside Nikhil Bansal and Jorn van der Pol, has been working on improving bounds on the number of matroids with a given number of points. They have produced a significant decrease in the best upper bound, so that it now quite closely resembles the best known lower bound (although, unfortunately, we have to apply logarithms twice in order to really see the resemblance!). The lower bound is due to Knuth, and provides a lower bound on the number of matroids by explicitly finding families of sparse paving matroids. Thus Rudi and his coauthors have provided some more circumstantial evidence supporting the conjecture that sparse paving matroids dominate the collection of all matroids. This conjecture seems to date back to Dominic Welsh, and was inspired by… the catalogue produced by Blackburn, Crapo, and Higgs!

Dillon Mayhew — Inequivalent representations over GF(7)

Mike Newman —Yes, the missing axiom of matroid theory is lost forever

Rudi Pendavingh — Counting matroids, entropy, and compression

Irene Pivotto — Seymour’s 1-flowing conjecture

Gordon Royle — Matroids and MYSQL: What to do with big data sets?

Michael Welsh — Maximum-sized golden-mean-graphic matroids

]]>