{"538511":{"#nid":"538511","#data":{"type":"news","title":"40-Year Math Mystery and Four Generations of Figuring","body":[{"value":"\u003Cp\u003EThis 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?\u003C\/p\u003E\u003Cp\u003EBut 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 \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1511.05020\u0022 target=\u0022_blank\u0022\u003Efinally announced a proof\u003C\/a\u003E \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1602.07557\u0022 target=\u0022_blank\u0022\u003Eof that conjecture in Graph Theory.\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003ETheir research was funded by the National Science Foundation.\u003C\/p\u003E\u003Cp\u003EGraph Theory is a field of mathematics that\u2019s instrumental in complex tangles. It helps you make more connecting flights, helps get your GPS unstuck in traffic, and helps manage your Facebook posts.\u003C\/p\u003E\u003Cp\u003EBack to the question. How many? Six (at least).\u003C\/p\u003E\u003Cp\u003EOne 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.\u003C\/p\u003E\u003Cp\u003EElapsed time: 39 years.\u003C\/p\u003E\u003Cp\u003ESo, 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.\u003C\/p\u003E\u003Cp\u003EAnd though the Georgia Tech proof fills some 120 pages of math reasoning, the conjecture itself is only one short sentence:\u003C\/p\u003E\u003Cp\u003E\u003Cem\u003EIf a graph G is 5-connected and non-planar, then G has a TK\u003Csub\u003E5\u003C\/sub\u003E.\u003C\/em\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EThe devil called \u2018TK\u003Csub\u003E5\u003C\/sub\u003E\u2019\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EYou could call a TK\u003Csub\u003E5\u003C\/sub\u003E the devil in the details. TK\u003Csub\u003E5\u003C\/sub\u003Es are larger relatives of K\u003Csub\u003E5\u003C\/sub\u003E, 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\u2019s fitting. A TK\u003Csub\u003E5\u003C\/sub\u003E in a \u201cgraph\u201d is guaranteed to thwart any nice, neat \u201cplanar\u201d status.\u003C\/p\u003E\u003Cp\u003EGraph Theory. Planar. Non-planar. TK\u003Csub\u003E5\u003C\/sub\u003E. Let\u2019s go to the real world to understand them better.\u003C\/p\u003E\u003Cp\u003E\u201cGraph Theory is used, for example, in designing microprocessors and the logic behind computer programs,\u201d said Georgia Tech mathematician Xingxing Yu, who has shepherded the Kelmans-Seymour Conjecture\u2019s proof to completion. \u201cIt\u2019s helpful in detailed networks to get quick solutions that are reasonable and require low computational complexity.\u201d\u003C\/p\u003E\u003Cp\u003ETo picture a graph, draw some cities as points on a whiteboard and lines representing interstate highways connecting them.\u003C\/p\u003E\u003Cp\u003EBut the resulting drawings are not geometrical figures like squares and trapezoids. Instead, the lines, called \u201cedges,\u201d are like wires connecting points called \u201cvertices.\u201d For a planar graph, there is always some way to draw it so that the lines from point to point do not cross.\u003C\/p\u003E\u003Cp\u003EIn the real world, a microprocessor is sending electrons from point to point down myriad conductive paths. Get them crossed, and the processor shorts out.\u003C\/p\u003E\u003Cp\u003EIn such intricate scenarios, optimizing connections is key. Graphs and graph algorithms play a role in modeling them. \u201cYou want to get as close to planar as you can in these situations,\u201d Yu said.\u003C\/p\u003E\u003Cp\u003EIn Graph Theory, wherever K\u003Csub\u003E5\u003C\/sub\u003E or its sprawling relatives TK\u003Csub\u003E5\u003C\/sub\u003Es show up, you can forget planar. That\u2019s why it\u2019s important to know where one may be hiding in a very large graph.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EThe human connections\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe human connections that led to the proof of the Kelmans-Seymour Conjecture are equally interesting, if less complicated.\u003C\/p\u003E\u003Cp\u003ESeymour had a collaborator, \u003Ca href=\u0022https:\/\/www.math.gatech.edu\/users\/thomas\u0022 target=\u0022_blank\u0022\u003ERobin Thomas, a Regent\u2019s Professor at Georgia Tech\u003C\/a\u003E who heads a \u003Ca href=\u0022http:\/\/www.aco.gatech.edu\/\u0022 target=\u0022_blank\u0022\u003Eprogram that includes a concentration on Graph Theory\u003C\/a\u003E. His team has a track record of cracking decades-old math problems. One was even more than a century old.\u003C\/p\u003E\u003Cp\u003E\u201cI tried moderately hard to prove the Kelmans-Seymour conjecture in the 1990s, but failed,\u201d Thomas said. \u201cYu is a rare mathematician, and this shows it. I\u2019m delighted that he pushed the proof to completion.\u201d\u003C\/p\u003E\u003Cp\u003EYu, once Thomas\u2019 postdoc and now a professor at the School of Mathematics, picked up on the conjecture many years later.\u003C\/p\u003E\u003Cp\u003E\u201cAround 2000, I was working on related concepts and around 2007, I became convinced that I was ready to work on that conjecture,\u201d Yu said. He planned to involve graduate students but waited a year. \u201cI needed to have a clearer plan of how to proceed. Otherwise, it would have been too risky,\u201d Yu said.\u003C\/p\u003E\u003Cp\u003EThen he brought in graduate student Jie Ma in 2008, and together they proved the conjecture part of the way.\u003C\/p\u003E\u003Cp\u003ETwo years later, Yu brought graduate students Yan Wang and Dawei He into the picture. \u201cWang worked very hard and efficiently full time on the problem,\u201d Yu said. The team delivered the rest of the proof quicker than anticipated and \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1511.05020\u0022 target=\u0022_blank\u0022\u003Ecurrently have two\u003C\/a\u003E \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1602.07557\u0022 target=\u0022_blank\u0022\u003Esubmitted papers\u003C\/a\u003E and two more in the works.\u003C\/p\u003E\u003Cp\u003EIn addition to the six mathematicians who made and proved the conjecture, others tried but didn\u2019t complete the proof but left behind useful cues.\u003C\/p\u003E\u003Cp\u003ENearly 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\u2019ve thoroughly failed to destroy it, will the proof officially stand.\u003C\/p\u003E\u003Cp\u003ESeymour\u2019s first reaction to news of the proof reflected that reality. \u201cCongratulations! (If it\u2019s true\u2026),\u201d he wrote.\u003C\/p\u003E\u003Cp\u003EGraduate student Wang is not terribly worried. \u201cWe spent lots and lots of our time trying to wreck it ourselves and couldn\u2019t, so I hope things will be fine,\u201d he said.\u003C\/p\u003E\u003Cp\u003EIf so, the conjecture will get a new name: Kelmans-Seymour Conjecture Proved by He, Wang and Yu.\u003C\/p\u003E\u003Cp\u003EAnd it will trigger a mathematical chain reaction, automatically confirming a past conjecture, Dirac\u2019s Conjecture Proved by Mader, and also putting within reach proof of another conjecture, Hajos\u2019 Conjecture.\u003C\/p\u003E\u003Cp\u003EFor Princeton mathematician Seymour, it\u2019s nice to see an intuition he held so strongly is now likely to enter into the realm of proven mathematics.\u003C\/p\u003E\u003Cp\u003E\u201cSometimes you conjecture some pretty thing, and it\u0027s just wrong, and the truth is just a mess,\u201d he wrote in an email message. \u201cBut sometimes, the pretty thing is also the truth; that that does happen sometimes is basically what keeps math going I suppose. There\u2019s a profound thought.\u201d\u003C\/p\u003E\u003Cp\u003E\u003Cem\u003EThe National Science Foundation funded this research under grants DMS-1265564 and AST-1247545. \u0026nbsp;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.\u003C\/em\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":[{"value":"Proof of Kelmans-Seymour Conjecture in Graph Theory, a math field applicable to social media"}],"field_summary":[{"value":"\u003Cp\u003EIn 1977, Princeton mathematician Paul Seymour made a conjecture about certain large graphs. Nearly 40 years later, Georgia Tech mathematicians have come up with a proof he was right. The conjecture is 13 words long; the proof covers 120 pages of math reasoning.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"In social media and much computer technology, a field of math called Graph Theory is used to make networks work. Georgia Tech mathematicians have solved a 40-year Graph Theory mystery."}],"uid":"31759","created_gmt":"2016-05-23 09:46:53","changed_gmt":"2016-10-08 03:21:42","author":"Ben Brumfield","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2016-05-25T00:00:00-04:00","iso_date":"2016-05-25T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"538601":{"id":"538601","type":"image","title":"Yu, Wang, He offer proof for Kelmans-Seymour Conjecture","body":null,"created":"1464703200","gmt_created":"2016-05-31 14:00:00","changed":"1475895326","gmt_changed":"2016-10-08 02:55:26","alt":"Yu, Wang, He offer proof for Kelmans-Seymour Conjecture","file":{"fid":"216413","name":"math_group_001.jpg","image_path":"\/sites\/default\/files\/images\/math_group_001.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/math_group_001.jpg","mime":"image\/jpeg","size":1414250,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/math_group_001.jpg?itok=-cFLlKKG"}}},"media_ids":["538601"],"groups":[{"id":"1188","name":"Research Horizons"}],"categories":[{"id":"153","name":"Computer Science\/Information Technology and Security"},{"id":"145","name":"Engineering"},{"id":"135","name":"Research"},{"id":"150","name":"Physics and Physical Sciences"}],"keywords":[{"id":"2612","name":"Graph Theory"},{"id":"170744","name":"He"},{"id":"172048","name":"K5"},{"id":"169181","name":"Kelmans-Seymour conjecture"},{"id":"256","name":"math"},{"id":"2748","name":"mathematics"},{"id":"172049","name":"TK5"},{"id":"6944","name":"Wang"},{"id":"170745","name":"Yu"}],"core_research_areas":[{"id":"39431","name":"Data Engineering and Science"}],"news_room_topics":[{"id":"71881","name":"Science and Technology"}],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Cstrong\u003EResearch News\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EGeorgia Institute of Technology\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EMedia Relations Contacts:\u003C\/strong\u003E\u0026nbsp;Ben Brumfield,\u003Ca href=\u0022mailto:ben.brumfield@comm.gatech.edu\u0022\u003Eben.brumfield@comm.gatech.edu\u003C\/a\u003E, 404-660-1408\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EWriter:\u003C\/strong\u003E Ben Brumfield\u003C\/p\u003E","format":"limited_html"}],"email":["ben.brumfield@comm.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}