科研学术

当前位置: 首页  >  科研学术  >  教师解决的数学猜想

教师解决的数学猜想

熊黎明教授解决图论中“漂亮猜想”的重要进展

发布日期:2012年04月10日

What is a beautiful conjecture?

    The mathematician's patterns, like the painter's or the poet's must be beautiful; the ideas, like the colors or the words must fit together in a harmonious way. Beauty is the first test: there is no permanent place in this world for ugly mathematics.

---------G.H. Hardy

    这里要讲的就是图论里一个漂亮猜想。首先给出一些描述, 尽量让没有任何图论知识的人都能明白。一个是指它有一个有限集合(里面的元素叫做顶点)并且对这个集合中某些顶点对(即两个顶点)给了一个关系(叫做一条)。一个存在从某个顶点出发、经过每个顶点恰好一次并且最后又回到出发顶点的、顶点与边交替出现的序列的图叫做哈密尔顿的。一个满足每对顶点之间存在顶点与边交替出现的序列(注意:此时未必包含所有顶点!)的图叫做连通的,否则就叫做不连通的; 满足去掉至少4个顶点变为不连通的连通图就是4连通的。如果一个图的任意四个顶点及其在这个图里所有的边都不形成一个(四个顶点三条边的图, 满足它有一个顶点与其它三个顶点之间都有边), 那么这个图就叫做无爪图。明白了这些描述后, 您一定能理解下面猜想的含义了, 哪怕您从来没接触过图论!

    猜想A(Matthews and Sumner, 1984):每个4连通的无爪图都是哈密尔顿的。

    图论界熟知的法国图论学家Bondy(邦迪)把它列为图论中20个重要而又漂亮的猜想之一。这是个至今依然没有完全解决的著名猜想(历时快30年了!目前最好的结果是:将猜想里4改为6,结论成立)。说它著名是因为它的影响大,与之相关的问题多,尝试解决它的名家也特别多,由此也产生了许多新概念、新技巧、新结果及新猜想等等。上世纪九十年代开始至今,每隔一段时间欧洲国家都会举办专题会议对它进行专门探讨。关于这方面的结果十分丰富,故事也很多,不是几句话能说清楚的。如果您感兴趣,可以从最近发表在Graphs and Combinatorics上(2012年第一期)的综述文章How many conjectures can you stand? A survey读到对它进行的专门介绍、分析及相关结果。

    现任J. Graph Theory的主编之一Thomassen教授也提出一个看起来似乎更弱的猜想。

    猜想B(Thomassen, 1986):每个4连通的线图都是哈密尔顿的。

    这里线图是它把某个图的边集合作为它的顶点集并且线图中两个顶点存在边是指它们在原图里有个共同的顶点。因为线图都是无爪的,所以猜想A能推出B;可能是因为名人效应似乎猜想B比A更有名。但是,十一年后,捷克Ryjacek教授通过引入局部闭包概念证明了它们实际上是等价的。

    关于这两个猜想的探讨,一方面试图去证明它的一些特殊情况是成立的。我们也做了这方面的工作(文章见Hourglasses and Hamilton Cycles in 4-connected Claw-free Graphs, J. Graph Theory, 48 (2005) 267-276)。我们的工作为解决这个猜想开辟了一个新的思路:我们证明了每个具有Hourglass性质(即它满足它的每个导出Hourglass都存在某对没有边的顶点满足它们之间有一条长为2并且顶点都不在这个导出Hourglass的路)的4连通无爪图都是哈密尔顿的。按照这个思路可以进一步考虑一般情况:当每个导出Hourglass都存在某对没有边的顶点满足它们之间有一条限定长并且顶点都不在这个导出Hourglass的路时猜想是否成立。虽然我们不知道这个思路对解决猜想有多困难,但是审稿人认为这是个很好的新思路!解决这个问题的故事是这样的:我刚来咱们北理工作时,恰逢Ryjacek率团访问中国科学院,合作者之一李明楚教授(当时在天津大学任教)联系我,要求和他们探讨问题(目标是推广一个已知的结果), 他从天津来北京只呆了半天,把他原来做的一个结果讲解后提出了进一步的问题,当时我们基本上能够利用他的这个结果部分解决猜想。但是有意思的是,我们后来发表的证明完全不是开始时候的思路。李明楚走后,我们继续讨论。我注意到:如果利用美国赖虹建教授的关于边在小圈上的一个结果,可以避开李明楚已经证明的中间结果(否则其证明是冗长的!);再结合Ryjacek的闭包运算,最后大家一起讨论得到发表的证明。每个合作者在里面都起了不同的作用。我与大家分享这些,是想说:合作交流与共同探讨对于数学研究是多么的重要!每个人的知识都是有限的,但是集体的智慧能迸发出意外神奇的火花!

    关于这两个猜想探讨的另一方面工作是给出它们的一些等价命题。我们也证明了它等价于一个似乎更弱的猜想:周长与顶点个数之比在所有4连通无爪图中当图的顶点个数趋于无穷时上极限等于1。这个等价猜想对于学过数学分析的人也是容易理解的!2001年底当我在捷克访问时,有一天合作者拿来一个图的构造。直观上,看了之后我觉得可以对上面猜想作一些工作,经过推理可以得到结果。因为其证明有许多细节需要反复推敲修改,所以相关结果直到2005年才发表在Graphs and Combinatorics上(文章见:ANote on the Shortness Coefficient and theHamiltonicityof 4-Connected Line Graphs,Graphs and Combinatorics, 21 (2005) 137-144)。 从这里也能看出合作交流与讨论对数学研究的重要性。