喬治亞理工學院華裔數學家證實40年未解數學難題：Kelmans-Seymour猜想
近日，喬治亞理工學院數學家郁星星教授（簡介附後）和其兩位研究生證明了困擾離散數學領域圖論界40年之久的Kelmans-Seymour猜想。
該猜想由普林斯頓大學著名數學家Paul Seymour於1977年首次提出，是圖論研究的核心猜想之一，與世界近代三大數學難題之一的「四色猜想」（即「在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色」）緊密相關。這項重要成果立刻引起了國際科學界的廣泛關注，Science Daily、Sci24H、Brunch News、Newswise、PHYS.ORG等國際知名學術網站都對該項成果進行了報道。
小科普
圖論研究（Graph Theory）中的「圖」與我們通常所理解的意義不同。它由點組成（稱為「verticles」或「nodes」），由線連接（稱為「edges」）。它可以用來描述許多涉及社會和信息系統之間關係的實際問題。它是數學學科的分支，幫助將航班以最有效的方式連接在一起，幫助你的GPS系統規划出避免交通堵塞的路線，甚至能幫助你在社交網站上管理聯繫人。舉例來說，一個網站的結構便可以通過一個有向圖來呈現，谷歌使用圖論研究作為其搜索引擎演算法的一部分，以檢測網站之間的鏈接。
以下內容節選自COSMOS雜誌專題報道（為確保學科內容準確性，不做翻譯處理）：
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.」
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. 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.
K5示意圖
You could call a TK5 the devil in the details. 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 said.
郁星星教授（右）和他的研究生助理 在白板上演示TK5模型
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.
（從左至右）郁星星教授和他的研究生助理 Yan Wang, Dawei He
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.
郁星星教授簡介
喬治亞理工學院數學系教授、博士生導師，主要研究領域為結構圖論和圖的演算法，解決了圖論中多個重要的猜想：如Moon和Moser在1970年提出的最長圈猜想，Brunbaum在1970年提出的Hamilton圈猜想，Nash-Williams在 1970年提出的生成路猜想以及Thomassen在1990年提出的Hamilton圈猜想。另外與Thomas合作證明了4-連通平面圖和射影平面圖包含Hamilton圈，還給出了多項式時間的構造演算法。這一結果與著名的四色定理有密切的聯繫，得到了圖論界的廣泛關注和讚譽。
1983年至1990年在華東師範大學先後取得學士和碩士學位，1990-1992年在美國Vanderbilt大學攻讀博士學位。2003年至今擔任喬治亞理工學院教授，曾任Internet Mathematics執行編輯，現任SCIENCE CHINA Mathematics， SIAM. J. Discrete Mathematics， Journal of Combinatorics， Discrete Mathematics Algorithms and Applications等多個學術雜誌編輯。在國際知名雜誌上發表論文80餘篇。
