You're reading: Posts By Katie Steckles

Graph Isomorphism panto: oh no it isn’t; oh yes it is!

As we reported back in November 2015, László Babai came up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. At the time, this proof still needed peer review, and in the last week or so, two big developments have occurred on that front.

On Wednesday 4th January, an error was discovered in the proof. Harald Helfgott (of the University of Göttingen in Germany and France’s National Center for Scientific Research), who studied the paper for several months, discovered that the algorithm was not quasipolynomial ($\displaystyle{ 2^{\mathrm{O}((\log n)^{c})} }$ for some fixed $c>0$) as claimed, but merely subexponenential: growing faster than a polynomial but still significantly slower than exponential growth).

Adorably, Babai posted this message on his website:

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.

But maths is all about the drama, so on Monday 9th January Babai announced a fix for the error, and it’s now back on the quasipolynomial table. This has now been confirmed (as of 14th Jan) by Harald Helfgott himself at the Bourbaki seminar in Paris. Amusingly, Helfgott had only been studying the paper in such detail in order to give the seminar, and it was this close scrutiny which allowed him to discover the mistake.

More information

Announcement on Babai’s website

Fixing the UPCC Case of Split-or-Johnson – Babai’s paper detailing the fix (PDF)

Graph Isomorphism Vanquished — Again, at Quanta Magazine

Bourbaki Seminar – Harald Helfgott, on YouTube

Mobile Numbers: Multiples of nine

In this series of posts, Katie investigates simple mathematical concepts using the Google Sheets spreadsheet app on her phone. If you have a simple maths trick, pattern or concept you’d like to see illustrated in this series, please get in touch.

We’re all (hopefully) aware that a pleasing property of numbers that are divisible by nine is that the sum of their digits is also divisible by nine.

It’s actually more well known that this works with multiples of three, and an even more pleasing fact is that the reason three and nine work is because nine is one less than the number base (10), and anything that’s a factor of this will also work – so, in base 13, this should work for multiples of 12, 6, 4, 3 and 2. Proving this is a bit of fun.

Once when I was thinking about this fact, an interesting secondary question occurred.

Puzzlebomb – December 2016

Puzzlebomb LogoPuzzlebomb is a monthly puzzle compendium. Issue 60 of Puzzlebomb, for December 2016, can be found here:

Puzzlebomb – Issue 60 – December 2016 (printer-friendly version)

The solutions to Issue 59 will be posted around one month from now.

This will be the last regular monthly Puzzlebomb – in future, there will be occasional one-offs but regular editions are taking a break. If you have any ideas for puzzles, please send them in! Previous issues of Puzzlebomb, and their solutions, can be found at Puzzlebomb.co.uk.

CP’s solid used as the basis of a puzzle

Back in 2013, our own Christian Lawson-Perfect came up with a way of making a solid from the smallest non-Hamiltonian graph, the Herschel Graph. Called the Herschel Enneahedron, it’s got nine faces (three squares and six kites) and the same symmetries as the graph itself.


The most recent news is that Spektrum magazine – sort of a German version of New Scientist – has included in its regular puzzle column a Herschel Enneahedron-related challenge. Here’s Google’s best effort at translating it:

Please make a polyhedron of 3 squares and 6 cover-like kite rectangles with suitable dimensions (in your thoughts, drawings or with carton). What symmetry properties does it have, how many corners and edges? Is it possible to make a (Hamilton-) circular path on its edges, which takes each corner exactly once and does not use an edge more than once?

Before you get out your cartons and start working on this, given that we started from a graph which isn’t Hamiltonian, you may have a slight spoiler on the answer here… but the solution given includes some nice videos and explanation as to how the solid is formed.

Treitz Puzzles 313, at Spektrum.de