Subscribe to our free daily newsletters
  Space Travel News  




Subscribe to our free daily newsletters



TIME AND SPACE
40-year math mystery and 4 generations of figuring
by Staff Writers
Atlanta GA (SPX) May 30, 2016


Georgia Tech mathematicians Xingxing Yu, Yan Wang and Dawei He have offered a proof of the Kelmans-Seymour Conjecture nearly 40 years after Princeton Mathematician Paul Seymour made it in 1977. Image courtesy Micah Eavenson and Georgia Tech. For a larger version of this image please go here.

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. 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."

See the video here


Thanks for being here;
We need your help. The SpaceDaily news network continues to grow but revenues have never been harder to maintain.

With the rise of Ad Blockers, and Facebook - our traditional revenue sources via quality network advertising continues to decline. And unlike so many other news sites, we don't have a paywall - with those annoying usernames and passwords.

Our news coverage takes time and effort to publish 365 days a year.

If you find our news sites informative and useful then please consider becoming a regular supporter or for now make a one off contribution.

SpaceDaily Contributor
$5 Billed Once


credit card or paypal
SpaceDaily Monthly Supporter
$5 Billed Monthly


paypal only

.


Related Links
Georgia Institute of Technology
Understanding Time and Space






Comment on this article via your Facebook, Yahoo, AOL, Hotmail login.

Share this article via these popular social media networks
del.icio.usdel.icio.us DiggDigg RedditReddit GoogleGoogle

Previous Report
TIME AND SPACE
New study implies existence of fifth force of nature
Irvine, Calif. (UPI) May 26, 2016
A team of Hungarian physicists published a paper last year hinting at the possibility of a fifth force of nature. It escaped publicity, but a recent analysis of the data by researchers at the University of California, Irvine has brought the paper back into the limelight. The Standard Model of particle physics - a model that helps scientists explain all the physics we can observe - fea ... read more


TIME AND SPACE
United Launch Alliance gets $138 million Atlas V contract

EchoStar XVIII and BRIsat are installed on Arianespace's Ariane 5

SpaceX makes fourth successful rocket landing

Arianespace to supply payload dispenser systems for OneWeb constellation

TIME AND SPACE
Red and Golden Planets at Opposition

Mars makes closest approach to Earth in 11 years

SwRI scientists discover evidence of ice age at Martian north pole

Opportunity investigating soil exposed by rover wheel

TIME AND SPACE
A new, water-logged history of the Moon

Russian Firm Develops Project of Reusable Spacecraft for Lunar Missions

SwRI scientists discover fresh lunar craters

NASA research gives new insights into how the Moon got inked

TIME AND SPACE
Study suggests Planet 9 is stolen exoplanet

Theft behind Planet 9 in our solar system

New Horizons' Best Close-Up of Pluto's Surface

Close encounters of a tidal kind could lead to cracks on icy moons

TIME AND SPACE
Astronomers find giant planet around very young star

Planet 1,200 Light-Years Away Is Good Prospect for a Habitable World

Kepler-223 System Offers Clues to Planetary Migration

Star Has Four Mini-Neptunes Orbiting in Lock Step

TIME AND SPACE
Understanding today's rocket engine market

Russia to Create New Powerful Plasma Rocket Engine

Roscosmos Proposes International Team to Create Super-Heavy Carrier Rocket

Australian, U.S. HIFiRE rocket achieves Mach 7.5

TIME AND SPACE
Chine's satellite industry eyes global satellite market

Bolivia takes over operations of Chinese-built satellite

NASA Chief: Congress Should Revise US-China Space Cooperation Law

China launches new satellite for civilian hi-res mapping

TIME AND SPACE
Comet Churyumov-Gerasimenko contains ingredients for life

NASA's OSIRIS-REx mission will have a map for that

NASA Begins Launch Preparations for the First U.S. Asteroid Sampling Mission

The Book on the Birthplace of Planetary Science




Memory Foam Mattress Review
Newsletters :: SpaceDaily :: SpaceWar :: TerraDaily :: Energy Daily
XML Feeds :: Space News :: Earth News :: War News :: Solar Energy News






The content herein, unless otherwise known to be public domain, are Copyright 1995-2017 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. All articles labeled "by Staff Writers" include reports supplied to Space Media Network by industry news wires, PR agencies, corporate press officers and the like. Such articles are individually curated and edited by Space Media Network staff on the basis of the report's information value to our industry and professional readership. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. Privacy Statement