You're reading: Posts Tagged: proof
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.
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”.
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.
Terence Tao has just uploaded a preprint to the arXiv with a claimed proof of the Erdős discrepancy problem.
Boris Konev and Alexei Lisitsa of the University of Liverpool have been looking at sequences of $+1$s and $-1$s, and have shown using an SAT-solver-based proof that every sequence of $1161$ or more elements has a subsequence which sums to at least $2$. This extends the existing long-known result that every such sequence of $12$ or more elements has a subsequence which sums to at least $1$, and constitutes a proof of Erdős’s discrepancy problem for $C \leq 2$.
Here are three things we noticed this month which didn’t get a proper write-up, due to thesis/Edinburgh fringe/holidays: a big proof, a fun maths book club, and a ridiculous bit of pi-related madhattery.