Getting started with sage_matroids: II

Following on from my previous post on getting started with sage_matroids, let’s look at a few more of the built-in features.

One of the most fundamental classes of matroids is the class of graphic matroids. Given a graph G, the graphic matroid M(G) has the edge set of G as its elements, and the forests of G as its independent sets. The circuits of M(G), i.e. the minimal dependent sets, are then precisely the cycles of G, so sometimes M(G) is called the cycle matroid of G.

The decision to go with Sage, rather than to either develop a stand-alone system or build on an existing stand-alone system, was largely driven by the fact that Sage provides both a standard programming language and a vast amount of inbuilt combinatorial functionality already. In particular, we can just piggyback on the very extensive “graphs” package to immediately create a graphic matroid using, of course, the canonical graph theory example.

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

In this case, the matroid reports that it is a regular matroid, which is a matroid represented by a totally unimodular matrix (a matrix all of whose sub-determinants are 0, 1 or -1).  Let’s see it:

sage: pm.representation()
[-1 -1 -1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 1  0  0 -1 -1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  1  0 -1 -1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  1  0 -1 -1  0  0  0  0  0  0]
[ 0  1  0  0  0  0  0  1  0 -1  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0 -1 -1  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0 -1 -1  0]
[ 0  0  0  0  0  0  1  0  0  0  1  0  0  0 -1]
[ 0  0  0  0  0  0  0  0  1  0  0  1  1  0  0]
[ 0  0  0  0  0  0  0  0  0  1  0  0  0  1  1]

In fact, this matrix is just the vertex-edge incidence matrix of the Petersen graph, with the first entry in each column set to -1. A regular matroid can be represented over any field by the same matrix.

Turning a graph into a matroid is easy of course, but what about the other way round?

Suppose we start with a binary matroid and ask “Does this matroid come from a graph?” For example, consider the matroid “bm” with the following representing matrix:

sage: bm
Binary matroid of rank 6 on 15 elements, type (4, 2)
sage: bm.representation()
[1 0 0 0 0 0 1 1 0 0 1 0 1 0 0]
[0 1 0 0 0 0 0 0 1 1 0 0 1 1 0]
[0 0 1 0 0 0 1 1 1 0 1 0 0 0 1]
[0 0 0 1 0 0 0 0 0 0 1 1 1 1 0]
[0 0 0 0 1 0 1 1 0 0 0 1 0 0 1]
[0 0 0 0 0 1 0 1 1 1 1 0 0 0 0]

It is clear that this particular matrix is not the vertex-edge incidence matrix of any graph, because some of the columns have more than two 1s. However a matroid can be represented by many different matrices and, in particular, any matrix that is row-equivalent to this matrix will represent the same matroid.  Searching through all the matrices row-equivalent to this one in order to find one with no more than two ones in each column is enough, but is rather unappealing. Fortunately, there are better ways to determine whether a matroid is graphic, and Rudi has implemented an elegant algorithm devised by Jim Geelen and Bert Gerards:

sage: bm.is_graphic()
False

A matroid is cographic if its dual matroid is graphic, and so we check this

sage: bm.dual().is_graphic()
True

It would be nice if a “True” response from the  “is_graphic()” method actually gave us a graph as well so we could identify which graphic matroid we have, but this is currently not implemented. Of course, the beauty of the open nature of  Sage is that if anyone feels like implementing this, then they can create the code, submit it to Sage as a patch, and then have it reviewed and incorporated into sage_matroids for all future users. Ultimately sage_matroids will grow and develop only if users who build useful functions for their own research then contribute them back to the community in this way.

Anyway, in the absence of this functionality we have to do a bit more work. Let’s pull out some more information

sage: bm.size()
15
sage: bm.rank()
6
sage: bm.bases_count()
2000

So the dual of bm has rank 9, size 15 and 2000 spanning trees. There’s only one graph that matches this, which is the Petersen graph, but let’s just confirm this to be absolutely sure.

sage: bm.dual().is_isomorphic(pm)
True

Here we are using the sage_matroids function “is_isomorphic” which detects isomorphism between matroids (using a straightforward, but optimised, algorithm).

Next time I’ll give some examples on  how to combine functions, either from sage_matroids or elsewhere in Sage, to very quickly and easily add new functionality and save it for re-using.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Up ↑

%d bloggers like this: