You're reading: News

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

Particularly mathematical New Year Honours 2017

Usually at this time of year, I have a look through the New Year Honours list for particularly mathematical appointments. Here are the names I’ve found that are particularly mathematical.

  • Tricia Dodd, Chief Methodology Officer, UK Statistics Authority, appointed MBE “for services to Statistics and Research”.
  • Dave Watson, director of IBM Research in the UK, who apparently has a focus on big data, appointed CBE “for services to Science and Engineering Research”.
  • Maggie Philbin, appointed OBE “for services to Promoting careers in STEM and Creative Industries”.
  • Anne-Marie Imafidon, co-founder and CEO of Stemettes, appointed MBE “for services to Young Women within STEM Sectors”.

I think every time I have done this (for New Year and Birthday Honours since 2013), there has been at least one person on the list, and usually several, specifically included for services to mathematics or mathematics education. This time, this is not the case, though there is one mention of statistics.

Are there any others I’ve missed? Please add any of interest in the comments below. A full list may be obtained from the UK Government website.

Relatively Prime is back!

Aperiodipal numero uno Samuel Hansen’s acclaimed podcast series Relatively Prime is back, on a new monthly schedule, with an episode about how PhD student Ibrahim Sharif designed a lottery to award licences to sell cannabis in the state of Washington.

When the stakes are so high (geddit?! – Ed.) you have to be really sure that your lottery is fair. That’s where a lot of fun maths comes in.

You can listen to Lottery Daze on relprime.com. Sam intends to fund this new incarnation of Relatively Prime through Patreon – you can pledge to pay Sam a certain amount (starting at a dollar) for every episode he releases, with perks for paying more such as a postcard from Sam or placing an ad in one of the episodes.

Listen to Lottery Daze on relprime.com

Support Relatively Prime on Patreon

Association for Women in Maths essay contest

The Association for Women in Mathematics in the USA is running its annual essay contest again, open to students in three age categories from Grade 6 to undergraduate.

Here’s the blurb:

To increase awareness of women’s ongoing contributions to the mathematical sciences, the Association for Women in Mathematics (AWM) and Math for America are co-sponsoring an essay contest for biographies of contemporary women mathematicians and statisticians in academic, industrial, and government careers.

The essays will be based primarily on an interview with a woman currently working in a mathematical sciences career. This contest is open to students in the following categories: Grades 6-8, Grades 9-12, and College Undergraduate. At least one winning submission will be chosen from each category. Winners will receive a prize, and their essays will be published online at the AWM web site. Additionally, a grand prize winner will have his or her submission published in the AWM Newsletter.

The deadline for entries is January the 31st 2017, and if you want the AWM to pair you up with an interviewee, you need to get a request in by January 10th.

All the prize-winning essays from previous years are online, including this nice one about Tanya Khovanova by high school student Emily Jia.

More information

AWM essay contest

Contest rules

Past winners

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