Mathematicians at Georgia Tech believe they have come up with a proof for a 40-year-old maths problem – the Kelmans-Seymour conjecture in graph theory.
Graph theory has nothing to do with what usually comes to mind from the word “graph”.
It deals with points or vertices, connected by lines, called edges, which sometimes form apparently impossible tangles. It can be used to describe many practical problems involving relations between things in social and information systems.
It is the branch of mathematics that helps plan the most efficient use of connecting flights, or your GPS make decisions on how to avoid the worst of the traffic, or even how to manage your friends on Facebook.
The structure of a website, for example, can be represented by a directed graph and Google uses graph theory as part of its search engine algorithms to check links between websites.
Kelmans-Seymour Conjecture’s name comes from Paul Seymour from Princeton University and Alexander Kelmans, who described the conjecture, independently – Seymour in 1977 and Kelmans in 1979.
The conjecture is: “If a graph G is 5-connected and non-planar, then G has a TK5.”
Credit: WIKIMEDIA COMMONS
In a planar graph, there is always some way to draw it so that the lines from point to point do not cross. This has importance in the real world, too.
As Ben Brumfield of Georgia Tech explains: “In the real world, a microprocessor is sending electrons from point to point down myriad conductive paths. Get them crossed, and the processor shorts out.”
In other words, you need a planar graph – or as close as possible to one – to do the job and graphs and graph algorithms can help model a suitable system.
And that’s where the TK5 comes in.
“You could call a TK5 the devil in the details,” writes Brumfield. “TK5s are larger relatives of K5, a very simple formation that looks like a five-point star fenced in by a pentagon.
“It resembles an occult or Anarchy symbol, and that’s fitting. A TK5 in a ‘graph’ is guaranteed to thwart any nice, neat ‘planar’ status.”
Georgia Tech mathematician Xingxing Yu, who helped push the Kelmans-Seymour Conjecture’s proof to completion, says that this makes the conjecture so important, as it helps identify a TK5 in more complex graphs.
“It’s helpful in detailed networks to get quick solutions that are reasonable and require low computational complexity,” he told Brumfield.
Yu took up the work of completing the proof from Robin Thomas, a former collaborator of Seymour and now a professor at Georgia Tech.
“I tried moderately hard to prove the Kelmans-Seymour conjecture in the 1990s, but failed,” he said. “Yu is a rare mathematician, and this shows it. I’m delighted that he pushed the proof to completion.”
Yu picked up on the conjecture around eight years ago.
“I became convinced that I was ready to work on that conjecture,” Yu said. He brought in graduate students Jie Ma in 2008, and Yan Wang and Dawei in 2010 into the project.
The team has now submitted two papers on the proof, with two more on the way. They now face seeing their proof tested to destruction by other mathematicians. Only if they fail to break it will it stand as a proof.
But Wang is sure of his team’s work.
“We spent lots and lots of our time trying to wreck it ourselves and couldn’t, so I hope things will be fine,” he said.