You're reading: Phil. Trans. Aperiodic.

This video about the proof of the Kelmans-Seymour conjecture is adorable

Theorem: every 5-connected non-planar graph contains a subdivision of $K_5$.

The above statement, conjectured independently by Alexander Kelmans and Paul Seymour in the 70s, is very easy to say. And the video below, starring Dawei He, Yan Wang, and Xingxing Yu, makes it look very easy to prove:

It’s like they got Wes Anderson to film an academic PR video. In the normally uninspiring world of maths press releases, it’s quite refreshing. And the written press release is pretty snappy, too. Let’s not make this a thing, though.

Steinberg’s conjecture is false

Conjecture   Every planar graph without 4-cycles and 5-cycles is 3-colourable.

Nope!

In a paper just uploaded to the arXivVincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado show the construction of a graph with no cycles of length 4 or 5 which isn’t 3-colourable: it isn’t possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours. This is a counterexample to a conjecture of Richard Steinberg from 1976.

The problem was listed in the Open Problem Garden as of “outstanding” importance.

Read the paper: Steinberg’s conjecture is false

via Parcly Taxel on Twitter

Not mentioned on The Aperiodical, March 2016

There’s been a lot of maths news this month, but we’ve all been too busy to keep up with it. So, in case you missed anything, here’s a summary of the biggest stories this month. We’ve got two new facts about primes, the best way of packing spheres in lots of dimensions, and the ongoing debate about the place of maths in society, as well as the place of society in maths.

A surprisingly simple pattern in the primes

Kannan Soundararajan and Robert Lemke Oliver have noticed that the last digits of adjacent prime numbers aren’t uniformly distributed – if one prime ends in a 1, for example, the next prime number is less likely to end in a 1 than another odd digit. Top maths journos Evelyn Lamb and Erica Klarreich have both written very accessible pieces about this, in the Nature blog and Quanta magazine, respectively.

Oliver and Soundararajan’s paper on the discovery is titled “Unexpected biases in the distribution of consecutive primes”.

GCHQ has declassified James Ellis’s papers on public key cryptography

secret-squirrel-gchq

Robert Hannigan, the Director of British intelligence agency GCHQ, gave a speech at MIT recently on the currently contentious issue of backdoors into encryption.

To accompany his speech, and maybe to reaffirm GCHQ’s credentials on the subject, he published two papers written by James Ellis in 1970 about what would become public key encryption: “The Possibility of Secure Non-Secret Digital Encryption” and “The Possibility of Secure Non-Secret Analogue Encryption”.

The story famously goes that two decades after Rivest, Shamir and Adleman announced the RSA algorithm for public key cryptography, GCHQ admitted that their employee Clifford Cocks had come up with essentially the same thing four years before, inspired by James Ellis’s papers on the possibility of cryptography without a secret key.

More information

Rober Hannigan’s speech, Front doors and strong locks: encryption, privacy and intelligence gathering in the digital era.

Read the papers: “The Possibility of Secure Non-Secret Digital Encryption” and “The Possibility of Secure Non-Secret Analogue Encryption” by James Ellis.

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.