Purple patch for Michael (and Gabriel)

Congratulations are due to Michael who is currently in a purple patch riding a wave of recognition and achievement over the last two or three weeks. (I had look up why it’s called a purple patch and not a green patch or a chartreuse patch etc.)

First, we heard that his latest ARC Discovery Grant application (along with Li and Gabriel) has been successful for a project involving symmetries of directed graphs, about which much less is known than for undirected graphs.

Secondly, he won a UWA Research Award in the “mid-career” category – these are internal awards across the whole university designed to recognise excellence in research; Gabriel also won the same award, but in the “early-career” category.

Then to top things off, we heard yesterday that his promotion to “something” was granted. Unfortunately it is not entirely clear what “something” should be. UWA used to use the British system of “lecturer/senior lecturer/associate professor/professor”, with only a handful of people in latter category. In other words, “Professor” is quite prestigious and only a few people will reach that level.

Then a few years ago, we decided to change to the US system of “assistant professor / associate professor / professor”. I’m not entirely sure why this change was made, but I think that it was partially to allow UWA to attract strong American academics (looking for jobs due to the hiring freeze in the US during the GFC) for whom dropping down to an “associate professor” would be seen as a backward step, and generally to align ourselves more with the US nomenclature than with the UK.

But then the local medical research funding body, the NHMRC, said that anyone who called themselves a professor would be evaluated as though they were an old-style prestigious professor, suddenly making some perfectly good research records look relatively mediocre.

So the edict has come down to, well, we don’t actually know what we’re meant to do. New jobs are to be advertised under the old titles, but holders of old jobs who chose to go to the new titles can continue to use the new titles or revert to the old titles depending on their preference or the day of the week or something. At least, I think I’ve got that right.

Anyway, there’s one thing that is clear. Congratulations to Michael on his promotion to Level D, his ARC Discovery Grant and his UWA Research Award. And to Gabriel for the latter two.

Is there a 5-chromatic cubelike graph?

I’m in Singapore at the moment, spending the weekend watching my 11-year old daughter Amy in a gymnastics competition and the weekdays visiting Dave Roberson (currently at NUS) and Fengming Dong (currently at NTU).

Meeting up with Dave and thinking once again about the annoyingly resistant conjecture that the core of a cubelike graph is cubelike, reminded me of another “cubelike” question that is still unresolved.

First some terminology: a cubelike graph is a Cayley graph for the elementary abelian 2-group Z_2^n; the term “cubelike” arises for two reasons:

  1. The n-dimensional cube is cubelike
  2. If you talk, or write, anything about these graphs, you rapidly need something snappier for the phrase “a Cayley graph for an elementary abelian 2-group”

It has been known for decades that a cubelike graph cannot have chromatic number 3, and this was proved in a beautifully elegant fashion by Payan. A very ambitious conjecture that all cubelike graphs have chromatic number equal to a power of 2 can be disproved by exhibiting a cubelike graph on 16 vertices with chromatic number 7, and cubelike graphs on 64 vertices with chromatic number 6.

But what about 5?

I simply cannot find any cubelike graph with chromatic number 5, and according to Brouwer’s website, this is unknown. Chris Godsil and I thought about this a few years ago, and someone said they had heard someone tell someone else that they had heard that perhaps some Russians had found such a graph on 128 vertices.

So, what’s the problem? Why not just construct all 128-vertex cubelike graphs and check their chromatic number?

The trouble with this is that the number of cubelike graphs grows very rapidly. There are only 1372 such graphs on 32 vertices, and we can find all the chromatic numbers. This jumps to 475499108 on 64 vertices (actually a handful less, this overcounts the number by about 10, due to some “accidental” isomorphisms), and although I don’t know the exact chromatic number of all of these, I can rule out enough of them as potential 5-chromatic graphs to complete the search.

But on 128 vertices, we have 1038397981840994509577948 graphs to work through (that’s just about 10^{30} and so unless we stumble on one somehow (perhaps someone knows who “the Russians” are) or make some theoretical advance, this problem is likely to remain unresolved for the time being.

Go Akshay!

Tomorrow the winner(s) of the Fields medal(s) for 2014 will be announced at the Seoul ICM and we’ll be eagerly awaiting the outcome.

Although he is only an outside chance (at least according to http://poll.pollcode.com/p6es9_result) one of the mathematicians “in the mix” is the UWA graduate Akshay Venkatesh. Actually Akshay went through Uni at the same time as Michael, although he’s 5 or 6 years younger than Michael. I remember first meeting them when I was chairing a seminar by Jack Koolen, and Akshay and Michael turned up. I must admit that on seeing this fresh-faced youngster (Michael) with someone barely of high-school age (Akshay), I assumed they were strays from some high-school visit and enquired whether they knew what sort of talk they were coming to!

Anyway, while I wish Akshay all the best, this post is really about the consequences of a possible award to him. Our university is obsessed by rankings and while the official goal “Top 50 by 2050” doesn’t specify which ranking system it is referring to, it is widely understood to be the Shanghai Jiao-Tong ranking of world universities. Personally, I don’t find this goal at all motivating – firstly it is totally unachievable without either a truly massive increase in resources or by such a severe distortion of university activities to focus only on the ranking criteria that it would no longer be recognisable as a university.

The problem is that the SJT criteria are incredibly narrowly focussed on extreme events such as Fields Medals and Nobel Prizes. For each university, 10% of the score is based on alumni with  Nobel prizes/Fields Medals, while a further 20% is based on Faculty with Nobel prizes/Fields Medals.  Another 20% is based on highly-cited researchers, of which UWA has a handful (including Cheryl). So 50% of the ranking is based on a tiny number of individuals. Of course universities devious enough about the rankings can appoint a few Nobel prize winners on reasearch-only positions and move up a few slots, whether or not the Nobel prize winner ever meets a student, or indeed ever steps on campus.

Despite this, I’m willing to accept that a university with 20 Nobel prize winners is statistically different from a university with one, like UWA.  But is there really a difference between a university with one Nobel prize winner and two, or zero?  If Akshay wins tomorrow, then UWA will score some points in the 10% and move up the rankings, and be deemed a better university than it was before. 

But does this make sense?

Akshay was at UWA nearly 20 years ago, and by all accounts he was prodigiously talented when he arrived at UWA and prodigiously talented when he left. It’s not clear to me that this reflects on UWA today in any particular way. 

Nevertheless, a win for Akshay still might have some direct benefit for us in the publicity that follows a high profile win. Since Akshay’s day, the Maths department has dramatically shrunk due to being the main target of relentless rounds of budget cuts, staff sackings, more budget cuts and so on. Although we pride ourselves on being a member of Australia’s “Group of 8” universites, we now have by far the weakest Mathematics course, with fewer than half the options of any of the others. Meanwhile, competitors like Monash are investing heavily in Maths with 15 new positions currently advertised. So if Akshay wins and the light of publicity shines on us, it might be a nice time to point out at the highest level that there aren’t any Top 50 universities with an emaciated Maths department.

So, one way or the other – good luck and  Go Akshay!

PS Another candidate “in the mix” is our old friend Harald Helfgott who has visited a couple of times and tried to teach us the mysterious properties of the sizes of triple products in groups. When we first invited him, we were told that he was of “Fields medal” quaility, but since he’s proven the ternary Goldbach conjecture, his odds are rapidly shortening. So good luck Harald!

Getting started with sage_matroids IV

Over at the MatroidUnion, Irene has written a comprehensive series of posts on classes of matroids that arise from biased graphs, so head there for more details on how even cycle matroids fit into the grand scheme of things. In this post however, we’ll just think about even cycle matroids on their own. This is also the first post I’ve written in Markdown, rather than battling with the visual editor, and while it formats the code nicely, I can’t make it format the output nicely (without the line numbers etc).

It is often convenient to identify a binary matroid with the row space of any (and hence all) of its representing matrices. For example, we’ve already discussed graphic matroids which are the binary matroids that can be represented by the vertex-edge incidence matrix of a graph, and so we’ll just call a subspace graphic if it is the row space of such a matrix. An even cycle matroid is a binary matroid that can be represented by the vertex-edge incidence matrix of a graph with an extra row added or, equivalently, a binary vector space containing a graphic subspace of codimension one.

There is no fast algorithm known for checking if a binary matroid is an even cycle matroid and so we have to just check all of its subspaces of codimension one for being graphic. It is easy to see that all the subspaces of codimension one can be obtained from a matroid M by extending M by a binary element e not in M and then immediately contracting e and so we get the following function:

def is_evencycle(m):
    if (m.rank() < 4):
        return true
    else:
        return any([n.contract('X').is_graphic()
            for n in m.linear_extensions('X')])

This uses the name ‘X’ to label the new element that is immediately contracted. If one of the elements of m is already called ‘X’, then the linear extensions method will fail. A more careful approach would be to first find a definitely new label.

Even-cycle matroids form a minor-closed class and so a very natural problem is the determination of the excluded minors for this class. We’ll certainly need to able to check that a matroid is an excluded minor – recall that this means that the matroid is not itself an even cycle matroid, but all of its single element deletions and contractions are even cycle matroids. We can easily modify the code that we used for graphic matroids to get:

def is_excludedminor_evencycle(m):
    return (not is_evencycle(m)
    and all([is_evencycle(m.contract(x)) for x in m.groundset()])
    and all([is_evencycle(m.delete(x)) for x in m.groundset()]))

Let’s use this to find the excluded minors for even cycle matroids of rank at most 5 in the most naive fashion possible, in other words, simply applying the function to every one of the 1372 binary matroids of rank at most 5. Assume that an array called “rank5s” has been defined such that “rank5s[e]” contains all the e-element binary matroids of rank at most 5. (It is fairly easy to make such an array using Sage.)

exminors = []
for e in range(32):
    for m in rank5s[e]:
        if is_excludedminor_evencycle(m):
            exminors.append(m)

What do we get at the end of this?

sage: len(exminors)
13
sage: [ [m.rank(),m.size()] for m in exminors]
[[5, 12],
[5, 12],
[5, 13],
[5, 13],
[5, 13],
[5, 13],
[4, 14],
[5, 14],
[5, 14],
[5, 14],
[5, 14],
[5, 15],
[5, 15]]

There is a unique excluded minor of size 14 and rank 4, which can only be PG(3,2)^{-}, the
matroid obtained by deleting an arbitrary element from PG(3,2), but the 12 additional excluded minors of rank 5 do not bode well for an excluded minor characterisation of even cycle matroids.

In fact, we’ll see in a later post in this series that things are even worse than it seems, but let’s return to the main point of this post, which is to demonstrate the relative ease of building on the functions provided in sage-matroids.

One fundamentally unsatisfying aspect of this code for excluded minors is that we’ve written two almost identical functions for the “excluded minor” functionality, but changing the occurrences of

m.is_graphic()

to

is_evencycle(m)

and if we continue to work with more properties, then we’ll need a separate function for
each and every property.

There is, however, a better way — we can create a function so that the property to
be tested is one of the parameters of the function.

def is_excluded_minor(p,m):
    return (
    not p(m)
    and all([p(n) for n in [m.contract(e) for e in m.groundset()]])
    and all([p(n) for n in [m.delete(e) for e in m.groundset()]]))

Now we can simply test whether a matroid is an excluded minor for the class of even cycle
matroids with

is_excluded_minor(is_evencycle, m)

and if we subsequently write a function for testing some other property, say whether the
matroid is an even cut matroid, then we can just insert the new property name into the
same function.

is_excluded_minor(is_evencut, m)

The only minor wrinkle is to remember to use the right name for the built-in functions.

is_excluded_minor(BinaryMatroid.is_graphic, m)

Next time, we’ll look a little more closely at the excluded minors for the even cycle matroids
and try to work out just how bad things might get!

Getting started with sage_matroids: III

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()
 False
sage: k5.is_graphic()
 True

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()])
 True

Now, what about the Fano plane?


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

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)
 True

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())
 True

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())
 True

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

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

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!

 

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

Continue reading “Getting started with sage_matroids: II”

Up ↑