Skip to content

Getting started with sage_matroids: II

October 23, 2013

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

Read more…

Getting started with sage_matroids: I

October 16, 2013

Sage 5.12 has just been released, and this is the first release that automatically incorporates the sage_matroids package that was primarily written by Rudi Pendavingh and Stefan van Zwam. Over at The Matroid Union, Stefan has written an introductory post along with some examples of using the package, and I’m going to complement this with some additional examples. Unlike Stefan though, I’m not an expert in Python, so this post is really to show how easy it is to just get started, even if you don’t know all that much about Python.

I’ll assume that you’ve installed Sage 5.12 and you either have a notebook (the browser interface) or command line working; on the command line Sage prompts you for input with the “sage: ” or “…” when multiline input is incomplete.

I’m mostly interested in binary matroids, which are basically just sets of binary vectors; traditionally a binary matroid is represented by the columns of a binary matrix. Let’s start with an easy binary matroid, namely the Fano plane which is, of course, the “standard” starting example in matroid theory. We can build it in two steps by typing in the representing matrix row-by-row and then creating the matroid.

sage: mat = Matrix([[0,0,0,1,1,1,1],[0,1,1,0,0,1,1],[1,0,1,0,1,0,1]])
sage: bm = sage.matroids.advanced.BinaryMatroid(mat)
sage: bm
Binary matroid of rank 3 on 7 elements, type (3, 0)

Notice that I have to use the “full name” of the constructor for a binary matroid, but if I get tired of typing the whole thing, then I can just tell Sage once-and-for-all where to find it and then just use the “short name”.

sage: from sage.matroids.advanced import BinaryMatroid
sage: bm = BinaryMatroid(mat)

Either way, the  variable “bm” now reports that it represents a binary matroid of rank 3 with 7 elements and gives some additional information that it is of “type (3,0)” (of which more later).

Now I can ask Sage lots of things about this matroid, such as confirming that I entered the matrix correctly, by asking for the representing matrix: notice that the syntax is the common object-oriented style whereby the object “bm” is asked to run the method “representation” and the value returned by the method is then displayed (or assigned to a variable etc.)

sage: bm.representation()
[0 0 0 1 1 1 1]
[0 1 1 0 0 1 1]
[1 0 1 0 1 0 1]

So the elements of this matroid — the groundset — is the set of columns of the matrix. To refer to a particular subset of the columns, I’ll need to know the “names” of the elements.

sage: bm.groundset()
frozenset([0, 1, 2, 3, 4, 5, 6])

This tells me that the groundset is an immutable set (the “frozen” part) containing the elements 0, 1, \ldots, 6. Mostly the end-user doesn’t need to know about immutable sets or why the groundset is immutable, so this is just a bit of the implementation showing and can safely be ignored. Or just use the alternative version of the command

sage: bm.groundset_list()
[0, 1, 2, 3, 4, 5, 6]

Now I know the groundset, I can find out all the usual “matroidy things” about the matroid, such as the rank of an arbitrary subset of the groundset.

sage: bm.rank([0,2,4])
sage: bm.rank([0,1,2])

The bases of the matroid are all the independent subsets of columns, and I can find out how many of these there are, and also which they are.

sage: bm.bases_count()
sage: bm.bases()
Iterator over a system of subsets

Ah, the first one is clear – there are 28 bases, but the second one didn’t give me what I expected, which was the list of bases, but rather an iterator. An iterator is a container object that supplies the objects it contains “one-by-one” (the container object can thereby represent a huge collection by not actually storing any of the objects but only producing them when called for). In this case though, we just want to see them all and so we use Python’s standard syntax for working with iterables.

sage: [b for b in bm.bases()]
[frozenset([0, 2, 3]),
 frozenset([1, 2, 3]),
 frozenset([0, 1, 3]),
 frozenset([1, 3, 4]),
 frozenset([2, 3, 4]),
 frozenset([0, 2, 4]),
 frozenset([1, 2, 4]),
 frozenset([0, 1, 4]),
 frozenset([0, 4, 5]),
 frozenset([1, 4, 5]),
 frozenset([3, 4, 5]),
 frozenset([0, 3, 5]),
 frozenset([2, 3, 5]),
 frozenset([0, 2, 5]),
 frozenset([1, 2, 5]),
 frozenset([0, 1, 5]),
 frozenset([1, 5, 6]),
 frozenset([2, 5, 6]),
 frozenset([3, 5, 6]),
 frozenset([4, 5, 6]),
 frozenset([0, 4, 6]),
 frozenset([2, 4, 6]),
 frozenset([3, 4, 6]),
 frozenset([0, 3, 6]),
 frozenset([1, 3, 6]),
 frozenset([0, 2, 6]),
 frozenset([1, 2, 6]),
 frozenset([0, 1, 6])]

The notation is simple for mathematicians because it is so similar to set notation – the command can be essentially translated directly into mathematics as \{b : b \in {\rm bases(bm)}\}. Of course, listing the contents of an iterable object is such a common activity that you can just use

sage: list(bm.bases())

to get the same result.

The circuits of the matroid are the minimal dependent sets of columns, and unsurprisingly can be accessed by

sage: bm.circuits()
Iterator over a system of subsets
sage: len(bm.circuits())

What if we want to know the lines of the binary matroid, which are the circuits of size 3. Again the Python notation is straightforward for mathematicians:

sage: [c for c in bm.circuits() if len(c) == 3]
 [frozenset([0, 1, 2]),
 frozenset([0, 3, 4]),
 frozenset([2, 4, 5]),
 frozenset([1, 3, 5]),
 frozenset([0, 5, 6]),
 frozenset([1, 4, 6]),
 frozenset([2, 3, 6])]

And there, we have the list of the lines of the Fano plane, exactly as expected. A frozen set is iterable, and so we can smarten up the output easily enough.

sage: [list(c) for c in bm.circuits() if len(c) == 3]
[[0, 1, 2], [0, 3, 4], [2, 4, 5], [1, 3, 5], [0, 5, 6], [1, 4, 6], [2, 3, 6]]

So there we have our first run through the absolute basics of using sage_matroids. Next time, I’ll move on to using – and building on – some of the more sophisticated built-in functions.

The Klein Correspondence II

October 10, 2013

This is a continuation of my last post on this subject. As Gordon remarked in one of his posts, you may need to refresh your browser if some of the embedded gifs do not appear as they should.

Dualities and isomorphisms of classical groups

Four of the five families of classical generalised quadrangles come in dual pairs: (i) Q(4,q) and W(3,q); (ii) H(3,q^2) and Q^-(5,q). Both can be demonstrated by the Klein correspondence. Recall from the last post that the Klein correspondence maps a line of \mathsf{PG}(3,q) represented as the row space of


to the point (p_{01}:p_{02}:p_{03}:p_{12}:p_{31}:p_{23}) where


Now consider the symplectic generalised quadrangle W(3,q) defined by the bilinear alternating form

B(x,y):=x_0y_1 - x_1y_0 + x_2y_3 - x_3y_2.

A totally isotropic line M_{u,v} must then satisfy

0 = B(u,v) = p_{01} + p_{23} .

Therefore, the lines of W(3,q) are mapped to points of Q^+(5,q) lying in the hyperplane \pi:X_0+X_5=0. Now the quadratic form defining Q^+(5,q) is Q(x)=x_0x_5+x_1x_4+x_2x_3 and \pi is the tangent hyperplane at the projective point (1:0:0:0:0:1), which does not lie in the quadric. Hence the hyperplane \pi is non-degenerate and so we see that W(3,q) maps to points of Q(4,q). That this mapping is bijective follows from noting that the number of lines of W(3,q) is equal to the number of points of Q(4,q) (namely, (q+1)(q^2+1)).

Hence \mathsf{P\Gamma Sp}(4,q)\cong \mathsf{P\Gamma O}(5,q).

Now we will consider a more difficult situation which reveals that the generalised quadrangles H(3,q^2) and Q^-(5,q) are also formally dual to one another. Read more…

News Update

October 9, 2013

It’s been a long time since we posted anything here, but things have kept on happening, so I thought I’d just give a sketchy update.

One of the reasons behind the hiatus in blog posts is that there’s now only two months to go before we host 37ACCMCC, the annual Australasian Combinatorial Conference, here in Perth. I’m the director of the organising committee and it’s quite a juggling act trying to keep on top of everything. It’s a bit of a guessing game too, because we have to book things like the conference dinner and excursion, but with most people registering at the last minute, we have no real idea of numbers! Now I know what it’s like to be on the receiving end, I’m going to register early for all future conferences!

We have a poster now though, which you can see here (or as a PDF here); you can probably recognise the nice building from our blog’s banner image.


Read more…

Regular graphs, triangles and MathOverflow

August 2, 2013

I’ve just uploaded a paper “Quartic graphs with every edge in a triangle” to the arxiv — joint with Florian Pfender — that characterises the quartic graphs with the property that every edge lies in a triangle.

Although this property doesn’t seem all that strong at first sight, it is actually very restrictive when the graph is regular of low enough degree. We end up with an exact characterisation saying that a 4-regular graph with every edge in a triangle is either:

  • a squared n-cycle, or
  • the line graph of a cubic (multi) graph, or
  • obtained from these by replacing triangles by copies of K_{1,1,3}.

Exact structural characterisations of natural classes of graphs are appealing, and this contains a nice mixture of a thin infinite family, a general construction and an operation under which the class is closed.

However, this paper would actually never have seen the light of day if it had not been for MathOverflow, the gamified question-and-answer website for research-level maths questions.

Read more…

Vale Laci Kovács

July 28, 2013

Many of us just received the sudden news of the passing of Laci Kovács, who spent amost of his career at the Australian National University and retired around 2001. Laci was a student of Bernhard Neumann and supervised 18 graduate students.

My own personal interaction with Laci started in my honours year. I was lucky enough to have solved a problem in combinatorial group theory and I sent a draft of a paper to a dozen or so group theorists. Laci and I exchanged emails and I looked into the possibility of persuing a PhD with him, but what discouraged me from going to ANU was his plans to take long service leave, and possible retirement. Plus, I was also in contact with Cheryl Praeger who was effectively luring me to the west, and that’s what I eventually ended up doing. Laci ended up being one of my PhD examiners and took great interest in my work. He came to Perth at least a couple of times during my PhD and first postdoc, and we had long enjoyable discussions in my office, on politics (one of Laci’s pet subjects) and mathematics.

Laci was one of the integral members of the golden era of group theory at ANU, and he will be sorely missed by the GT-community.

A plug/reminder

July 23, 2013

Just a quick reminder that the annual “Australasian Conference on Combinatorial Mathematics and Combinatorial Computing” (ACCMCC) will be in Perth this December, and registration is open.

It’s a good idea to get in early in getting accommodation at St George’s College (across the road from UWA), which you must book yourself. The early-bird registration is available until 11th November.

For more information, please go to the conference webpage.


Get every new post delivered to your Inbox.

Join 40 other followers