Skip to content

Getting started with sage_matroids: III

January 29, 2014

After being busy for the last couple of months, it’s time to return to learning how to use a few more of the basic features of sage_matroids.

Last time we looked at graphic matroids which are the binary matroids that can be represented by the vertex-edge incidence matrix of a graph, and mentioned that sage_matroids has a very effective test for being graphic.

sage: f7 = matroids.named_matroids.Fano()
sage: k5 = BinaryMatroid(graphs.CompleteGraph(5).incidence_matrix())
sage: f7.is_graphic()
sage: k5.is_graphic()

So the Fano plane is not graphic, while the cycle matroid of K_5 is graphic. Now if a matroid is graphic then all of its minors are graphic, where a minor is any matroid obtained by repeatedly contracting and deleting elements. For example, let’s just confirm this by checking all the contractions of K_5. We’ll do it in two steps first.

sage: k5cons = [k5.contract(x) for x in k5.groundset()]
sage: [n.is_graphic() for n in k5cons]
 [True, True, True, True, True, True, True, True, True, True]

We can shortcircuit this to avoid making the intermediate list of minors explicitly.

sage: [k5.contract(x).is_graphic() for x in k5.groundset()]
 [True, True, True, True, True, True, True, True, True, True]

If we just want to check that all the values are True without listing them all, we can use the handy Python construct all which is True if all of the elements of an iterable are True.

sage: all([k5.contract(x).is_graphic() for x in k5.groundset()])

Now, what about the Fano plane?

sage: all([f7.contract(x).is_graphic() for x in f7.groundset()])
sage: all([f7.delete(x).is_graphic() for x in f7.groundset()])

So F_7 also has this property, so although it is not graphic itself, all of its minors are graphic, and so it is a minor minimal non-graphic matroid or, in other words, an excluded minor for the class of graphic matroids.

One of the fundamental observations of matroid theory is that any minor-closed class of matroids can be characterised by listing its excluded minors, and there is a vast literature that either (1) takes a natural property defining a minor-closed class of matroids and finds the excluded minors, or (2) takes a list of matroids and investigates the properties enjoyed (endured?) by the class of matroids without minors in the initial list.

So, let’s write a function to detect when a binary matroid is an excluded minor for the class of graphic matroids. This is true when the matroid passed in as the argument to the function is not graphic itself, but all of its single element deletions and contractions are graphic.

sage: def is_excludedminor_graphic(m):
    return (not m.is_graphic()
    and all([m.contract(x).is_graphic() for x in m.groundset()])
    and all([m.delete(x).is_graphic() for x in m.groundset()]))

This code defines a function that can now be called by name for the rest of the Sage session; if it proves useful, then the code can be saved in a file and “imported” at the beginning of a future Sage session.

sage: is_excludedminor_graphic(f7)

So what are some other excluded minors for graphic matroids? It turns out that F_7^* — the dual of the Fano matroid — is another one, as we can confirm.

sage: is_excludedminor_graphic(f7.dual())

Of course, the full list of excluded minors for graphic matroids is known, and consists of F_7, F_7^* and the duals of the graphic matroids M(K_5) and M(K_{3,3}). Let’s just check the first of these.

sage: is_excludedminor_graphic(k5.dual())

It is a famous result of Robertson and Seymour that every minor-closed family of graphs has a finite list of excluded minors and Geelen, Gerards and Whittle have shown that the same is true for binary matroids. Of course, finite doesn’t mean short or easy-to-find and there are lots of minor-closed classes for which the list of excluded minors is not known at all, or for which the list of known excluded minors is vast and still growing.

Next time we’ll talk more about excluded minors for some classes of binary matroids.

The Open Problem Garden

January 23, 2014

It is nearly time for our third “research retreat” where our research group goes away for a few days and sit down in various combinations to discuss some new research problems, preferably problems that require some combination of all our specializations, skills and interests. The aim is to broaden our joint knowledge, introduce graduate students to problems outside their thesis (at least for a little while), encourage additional collaborations, and of course just to have a nice time away from the daily routine.

Choosing suitable problems is hard of course, because anything too technical or specialized immediately makes it difficult for someone outside the immediate area to get up to speed. On the other hand, combinatorics is renowned for easy-to-state problems that are impossible to solve, so we want to avoid those as well.

So before each retreat, I find myself looking online for “open problems in combinatorics” and finding various lists of problems, such as Peter Cameron’s list, Douglas West’s list, and of course “The Open Problem Garden“, which was set up by Matt DeVos and Robert Samal to be a “crowd-sourced” list of problems where users could add problems, comment on problems, discuss solutions etc.

Even though everything on the site seems to work well technically (it is based on the notoriously massive and hard-to-learn Drupal CMS so I can only imagine how hard it was to get working), it simply doesn’t seem to have taken off, and I can’t really understand why. A good fraction of the problems were posted by Matt and Robert, and though I’ve added a few and tried to comment on others, the lack of activity from other people means that it rapidly dropped off my radar.

On the other hand, MathOverflow seems to work brilliantly and have created a real sense of community, but again I have no real idea why. On the other hand, when I first heard about Twitter, I thought it was the dumbest idea I’d ever heard, so my insight into what works and doesn’t is clearly not very finely tuned.

It would be really nice if something like the Open Problem Garden worked well, but what is the secret sauce it needs to take off? Could it really just be the gamification that MO has, complete with upvoting, downvoting, points and “medals”? Or something more sophisticated?

100 today

January 17, 2014

I don’t usually post personal things on this maths blog, but today I’ll make an exception.

My father was born in Perth on 17 January 1914, which makes him 100 years old today (and still going strong). He’s had a pretty full life, and is mildly famous for his participation in The Great Escape, of which there are now only two survivors (the other being a sprightly 92-year old from Devon, UK).

Happy Birthday Dad!


Regular cycles of elements in finite primitive permutation groups

November 18, 2013

Cheryl Praeger, Pablo Spiga and I have just uploaded to the arxiv our preprint  Finite primitive permutation groups and regular cycles of their elements.   Everyone recalls from their first course in group theory that if you write a permutation in cycle notation, for example (1,2)(3,4,5)(6,7,8,9,10), then its order is the lowest common multiple of it cycle lengths. As I have just demonstrated, not every permutation must have a cycle whose length is the same as the order of the element. We call a cycle of an element g whose length is the order of g, a regular cycle.  A natural question to ask is when can you guarantee that a permutation has a regular cycle? Or in particular, for which permutation groups do all elements have a regular cycle?

Clearly, the full symmetric group contains elements with no regular cycles, but what about other groups?  Siemons and Zalesskii showed that for any group G  between PSL(n,q) and PGL(n,q) other than for (n,q)=(2,2) or (2,3), then in any action of G, every element of G has a regular cycle, except G=PSL(4,2) acting on  8 points. The exceptions are due to isomorphisms with the symmetric or alternating groups.  They also later showed that for any finite simple group G,other than the alternating group, that admits a 2-transitive action, in any action of G every element has a regular cycle. This was later extended by Emmett and Zalesskii to any finite simple classical group not isomorphic to PSL(n,q).

With these results in mind, we started investigating elements in primitive permutation groups. The results of this work are in the preprint. First we prove that for k\leq m/2, every element of Sym(m) in its action on k-sets has a regular cycle if and only if m is less than the sum of the first k+1 primes. After further computation we were then willing to make the following conjecture:

Conjecture: Let G\leqslant Sym(\Omega) be primitive such that some element has no regular cycle. Then there exist integers k\geq1, r\geq1 and m\geq5 such that
G preserves a product structure on \Omega=\Delta^r with |\Delta|=\binom{m}{k}, and Alt(m)^r  \vartriangleleft G\leqslant Sym(m)\textrm{wr} Sym(r), where Sym(m) induces its k-set action on \Delta.

The general philosophy behind why such a result should be true is that most primitive groups are known to be small in terms of a function of the degree.  There is a large body of work bounding the orders of primitive permutation groups with the best results due to Maroti. The actions of Sym(m) on k-sets are the usual exceptions.

Our paper  goes about attempting to prove this conjecture. We make substantial progress and reduced its proof to having to deal with all the primitive actions of classical groups. Note that Emmett and Zalesskii only dealt with simple ones.  One consequence of our work is we showed that every automorphism of a finite simple group has a regular cycle in its action on the simple group.

Pablo and Simon Guest have subsequently gone on to prove the result for all actions of classical groups and so the conjecture is now a theorem.

Pablo gave a great talk about the conjecture and its subsequent proof  at the recent BIRS workshop on Permutation Groups in Banff which you can view here.


November 8, 2013

The Minister for Education (finally) announced the ARC Future Fellowships commencing in 2013 this morning, and simultaneously, the DECRA’s and Discovery Projects. Our research group missed out on a grant of the first and second kind, but we had success with two Discovery Projects:

  1. Cheryl Praeger, Stephen Glasby, and Alice Niemeyer (“Finite linearly representable geometries & symmetries).
  2. Gordon (“Real chromatic roots of graphs & matroids”)

I remember last summer when both grant applications were being written, and it was a lot of work for all involved, so it’s great to see that both have awarded to support cutting edge research.

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.


Get every new post delivered to your Inbox.

Join 44 other followers