佐治亚理工学院华裔数学家证实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余篇。
