Conjecture Every planar graph without 4-cycles and 5-cycles is 3-colourable.
In a paper just uploaded to the arXiv, Vincent 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
Previously unseen footage has been unearthed by The Aperiodical’s crack team of investigative journalists of Kevin Bacon and Paul Erdős writing a paper together, and a still from this is shown above. This has massive consequences for the important topics of Erdős numbers, Bacon numbers and Erdős-Bacon numbers.
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”.
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.
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 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.
Who could have guessed that this non-story about somebody being out of his depth and quite obviously wrong would get so out of hand? Here’s an update on The Continuing Tale Of The Man Whose Claims Couldn’t Be Verified.