Nav: Home

40-year math mystery and 4 generations of figuring

May 25, 2016

This may sound like a familiar kind of riddle: How many brilliant mathematicians does it take to come up with and prove the Kelmans-Seymour Conjecture?

But the answer is no joke, because arriving at it took mental toil that spanned four decades until this year, when mathematicians at the Georgia Institute of Technology finally announced a proof of that conjecture in Graph Theory.

Their research was funded by the National Science Foundation.

Graph Theory is a field of mathematics that's instrumental in complex tangles. It helps you make more connecting flights, helps get your GPS unstuck in traffic, and helps manage your Facebook posts.

Back to the question. How many? Six (at least).

One made the conjecture. One tried for years to prove it and failed but passed on his insights. One advanced the mathematical basis for 10 more years. One helped that person solve part of the proof. And two more finally helped him complete the rest of the proof.

Elapsed time: 39 years.

See video: https://www.youtube.com/watch?v=kJezlZBrbPk

So, what is the Kelmans-Seymour Conjecture, anyway? Its name comes from Paul Seymour from Princeton University, who came up with the notion in 1977. Then another mathematician named Alexander Kelmans, arrived at the same conjecture in 1979.

And though the Georgia Tech proof fills some 120 pages of math reasoning, the conjecture itself is only one short sentence:

If a graph G is 5-connected and non-planar, then G has a TK5.

The devil called 'TK5'

You could call a TK5 the devil in the details. TK5s are larger relatives of K5, a very simple formation that looks like a 5-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.

Graph Theory. Planar. Non-planar. TK5. Let's go to the real world to understand them better.

"Graph Theory is used, for example, in designing microprocessors and the logic behind computer programs," said Georgia Tech mathematician Xingxing Yu, who has shepherded the Kelmans-Seymour Conjecture's proof to completion. "It's helpful in detailed networks to get quick solutions that are reasonable and require low computational complexity."

To picture a graph, draw some cities as points on a whiteboard and lines representing interstate highways connecting them.

But the resulting drawings are not geometrical figures like squares and trapezoids. Instead, the lines, called "edges," are like wires connecting points called "vertices." For a planar graph, there is always some way to draw it so that the lines from point to point do not cross.

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 such intricate scenarios, optimizing connections is key. Graphs and graph algorithms play a role in modeling them. "You want to get as close to planar as you can in these situations," Yu said.

In Graph Theory, wherever K5 or its sprawling relatives TK5s show up, you can forget planar. That's why it's important to know where one may be hiding in a very large graph.

The human connections

The human connections that led to the proof of the Kelmans-Seymour Conjecture are equally interesting, if less complicated.

Seymour had a collaborator, Robin Thomas, a Regent's Professor at Georgia Tech who heads a program that includes a concentration on Graph Theory. His team has a track record of cracking decades-old math problems. One was even more than a century old.

"I tried moderately hard to prove the Kelmans-Seymour conjecture in the 1990s, but failed," Thomas said. "Yu is a rare mathematician, and this shows it. I'm delighted that he pushed the proof to completion."

Yu, once Thomas' postdoc and now a professor at the School of Mathematics, picked up on the conjecture many years later.

"Around 2000, I was working on related concepts and around 2007, I became convinced that I was ready to work on that conjecture," Yu said. He planned to involve graduate students but waited a year. "I needed to have a clearer plan of how to proceed. Otherwise, it would have been too risky," Yu said.

Then he brought in graduate student Jie Ma in 2008, and together they proved the conjecture part of the way.

Two years later, Yu brought graduate students Yan Wang and Dawei He into the picture. "Wang worked very hard and efficiently full time on the problem," Yu said. The team delivered the rest of the proof quicker than anticipated and currently have two submitted papers and two more in the works.

In addition to the six mathematicians who made and proved the conjecture, others tried but didn't complete the proof but left behind useful cues.

Nearly four decades after Seymour had his idea, the fight for its proof is still not over. Other researchers are now called to tear at it for about two years like an invading mob. Not until they've thoroughly failed to destroy it, will the proof officially stand.

Seymour's first reaction to news of the proof reflected that reality. "Congratulations! (If it's true...)," he wrote.

Graduate student Wang is not terribly worried. "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.

If so, the conjecture will get a new name: Kelmans-Seymour Conjecture Proved by He, Wang and Yu.

And it will trigger a mathematical chain reaction, automatically confirming a past conjecture, Dirac's Conjecture Proved by Mader, and also putting within reach proof of another conjecture, Hajos' Conjecture.

For Princeton mathematician Seymour, it's nice to see an intuition he held so strongly is now likely to enter into the realm of proven mathematics.

"Sometimes you conjecture some pretty thing, and it's just wrong, and the truth is just a mess," he wrote in an email message. "But sometimes, the pretty thing is also the truth; that that does happen sometimes is basically what keeps math going I suppose. There's a profound thought."
-end-
The National Science Foundation funded this research under grants DMS-1265564 and AST-1247545. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Georgia Institute of Technology

Related Math Articles:

Using math to blend musical notes seamlessly
MIT researchers have invented an algorithm that produces a real-time portamento effect, gliding a note at one pitch into a note of another pitch, between any two audio signals, such as a piano note gliding into a human voice.
Novel math could bring machine learning to the next level
In recent years, a theory called 'Topological Data Analysis,' stemmed from a branch of Mathematics so abstract that it did not seem to have any application whatsoever in the real world, has been making computers much better at recognizing meaningful structure inside all kinds of large datasets (a.k.a.
Study shows we like our math like we like our art: Beautiful
A beautiful landscape painting, a beautiful piano sonata -- art and music are almost exclusively described in terms of aesthetics, but what about math?
Phase transitions: The math behind the music
Physics Professor Jesse Berezovsky contends that until now, much of the thinking about math and music has been a top-down approach, applying mathematical ideas to existing musical compositions as a way of understanding already existing music.
IQ a better predictor of adult economic success than math
IQ in childhood is a better indicator of adult wealth than math for very preterm and very low-weight babies, according to a new study in PLOS ONE.
Math + good posture = better scores
A San Francisco State University study finding that students perform better at math while sitting with good posture could have implications for other kinds of performance under pressure.
Army researcher uses math to uncover new chemistry
In the future, materials scientists will use advanced software to specify the properties they desire and a program will deliver a choice of optimized chemical compounds.
New math bridges holography and twistor theory
A new perspective bridges two approaches to understanding quantum gravity.
Positive attitude toward math predicts math achievement in kids, Stanford study finds
For the first time, scientists have identified the brain pathway that links a positive attitude toward math to achievement in the subject.
Math can predict how cancer cells evolve
Applied mathematics can be a powerful tool in helping predict the genesis and evolution of different types of cancers, a study from the University of Waterloo has found.
More Math News and Math Current Events

Top Science Podcasts

We have hand picked the top science podcasts of 2019.
Now Playing: TED Radio Hour

In & Out Of Love
We think of love as a mysterious, unknowable force. Something that happens to us. But what if we could control it? This hour, TED speakers on whether we can decide to fall in — and out of — love. Guests include writer Mandy Len Catron, biological anthropologist Helen Fisher, musician Dessa, One Love CEO Katie Hood, and psychologist Guy Winch.
Now Playing: Science for the People

#543 Give a Nerd a Gift
Yup, you guessed it... it's Science for the People's annual holiday episode that helps you figure out what sciency books and gifts to get that special nerd on your list. Or maybe you're looking to build up your reading list for the holiday break and a geeky Christmas sweater to wear to an upcoming party. Returning are pop-science power-readers John Dupuis and Joanne Manaster to dish on the best science books they read this past year. And Rachelle Saunders and Bethany Brookshire squee in delight over some truly delightful science-themed non-book objects for those whose bookshelves are already full. Since...
Now Playing: Radiolab

An Announcement from Radiolab