您的位置: 首页  校友风采

郁星星:华东师大83级数学系学长证实40年未解数学难题Kelmans-Seymour猜想

       日前,美国佐治亚理工学院郁星星教授和其两位研究生证明了困扰离散数学领域图论界40年之久的Kelmans-Seymour猜想。所以,上图可不是在画简单的五角星哦,而是郁星星教授的研究生Dawei He在演示Kelmans-Seymour猜想的部分证实过程,现在是不是有些不明觉厉?

郁星星教授是华东师大数学系校友、1983年至1990年在华东师范大学先后取得学士和硕士学位,2010年起被聘为华东师大紫江讲座教授、博士生导师。


郁星星教授和他的研究生助理 Yan Wang, Dawei He


郁星星教授(右)和他的研究生助理 在白板上演示TK5模型

 

什么是Kelmans-Seymour猜想?

该猜想由普林斯顿大学著名数学家Paul Seymour1977年首次提出,是图论研究的核心猜想之一,与世界近代三大数学难题之一的四色猜想(即在一个平面或球面上的任何地图能够只用四种颜色来着色,使得没有两个相邻的国家有相同的颜色)紧密相关。


Paul Seymour
教授,Kelmans-Seymour猜想提出者

 

Kelmans-Seymour猜想内容

 

40年困扰离散数学领域图论界

既然是困扰离散数学领域图论界40年之久的难题,那么图论研究究竟是什么?对我们的生活有什么意义?

图论研究(Graph Theory)中的与我们通常所理解的意义不同。它由点组成(称为“verticles”“nodes”),由线连接(称为“edges”)。它可以用来描述许多涉及社会和信息系统之间关系的实际问题。

它是数学学科的分支,帮助将航班以最有效的方式连接在一起,帮助你的GPS系统规划出避免交通堵塞的路线,甚至能帮助你在社交网站上管理联系人。举例来说,一个网站的结构便可以通过一个有向图来呈现,谷歌使用图论研究作为其搜索引擎算法的一部分,以检测网站之间的链接。

猜想被证明后,立刻引起了国际科学界的广泛关注,Science DailySci24HBrunch NewsNewswisePHYS.ORG等国际知名学术网站都对该项成果进行了报道。


以下内容节选自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.

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.

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.


 

郁星星,佐治亚理工学院数学系教授、博士生导师,华东师范大学紫江讲座教授、博士生导师。主要研究领域为结构图论和图的算法,解决了图论中多个重要的猜想:如MoonMoser1970年提出的最长圈猜想,Brunbaum1970年提出的Hamilton圈猜想,Nash-Williams 1970年提出的生成路猜想以及Thomassen1990年提出的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余篇。

作者: | 信息来源: | 发布日期:2016-06-16 | 浏览次数:
更多


微信 APP(苹果) 我要捐赠 APP (安卓) 微博 RSS

上海市中山北路3663号华东师范大学地理馆112室 Tel:021-62235878 021-62235002
校友投稿: lwxz@admin.ecnu.edu.cn Copyright © 华东师范大学校友会