# Matroid Computation with Sage: Linear Extensions

I’ll continue my exploration of Sage’s matroid capabilities (see also here and here). This time I’ll look at extensions within subclasses of matroids, namely representable matroids. Before we get started, let me remind you of the reference manual, in which the capabilities of Sage’s matroid package are extensively documented. Continue reading

# Matroid Computation with Sage: Extensions

In this post I want to continue exploring the new-found capabilities of Sage with respect to matroid computation. It follows up on this post; Gordon Royle started a different sequence of posts on sage-matroids here. Following a comment by Jason Grout, I decided to experiment with the Sage Cell Server. The result? All computations in this post can be carried out live, by clicking the “Evaluate” button, and you can edit them to play with them! How awesome is that? A word of warning: the cells in each section of this post are linked together, so if you didn’t evaluate a previous cell, the ones below it might not work. For technical reasons, we use # signs on otherwise empty lines. These symbols (and anything following) are comments, and don’t do anything.

The topic for today is matroid extensions. Continue reading

# Matroid Computation with Sage

October 7, 2013, marked a day that I have long been looking forward to: the release of Sage 5.12. This is the first version of Sage to support matroid theory!

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.

# What is Sage?

From the Sage homepage:

Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface.
Mission: Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab.

There are several ways to interact with Sage:

• 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).

# Matroids in Sage

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.

# Some examples

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.

# In conclusion

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.

# Matroids at La Vacquerie – 2013

Stefan and I (and others) have been idly talking about putting together a matroid blog for some time, and it was at a workshop of Henry Crapo’s that we finally put the plan into action, so I thought that I would devote my inaugural post to writing a little about the meeting.

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!

#### Slides:

Dillon Mayhew — Inequivalent representations over GF(7)

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