赫渥特的地图着色公式与杨斯等人的完全图的亏格公式之间的关系及其来龙去脉

雷明85639720

赫渥特的地图着色公式与杨斯等人的完全图的亏格公式之间的关系及其来龙去脉
雷  明
（二○一四得十二月十一日）

赫渥特在1890年已经得到了一个多阶曲面上的着色公式——γ≤<（7＋√（1＋48n））/2>（其中< >表示其中的数字向下取整，γ表示图的色数，n表示图的亏格，下同），杨斯（Youngs）在1967年以后得到了完全图的亏格公式——n（KV）＝［（v－3）（v－4）/12］（其中［ ］表示其中的数字向上取整，KV表示顶点数为v的完全图，下同），但这两个公式是怎么得来的，文献资料上没有说，也没有看到后人对此进行的推导与证明。文献资料上只能看到利用杨斯公式来对赫渥特公式进行所谓证明的资料。
1、对两个公式的分析
赫渥特公式说的是相同亏格的图的色数。而图的色数又与其最小完全同态的顶点数相等，所以我们可以用完全图的顶点数v来代替公式中的色数γ，使公式变成v（KV）≤<（7＋√（1＋48n））/2>。由于图的最小完全同态的亏格一定是小于等于原图的亏格的，所以公式中的等式是指最小完全态的亏格与原图的亏格相同的的图的最小完全同态的顶点数，而不等式则指的是最小完全同态的亏格比原图的亏格小的图的最小完全同态的顶点数。这个赫渥特公式主要是用亏格求该和下的图的最小完全同态的顶点数上界的方法。
杨斯的公式则是用完全图的顶点数去求该图可嵌入曲面的亏格的方法。公式本身是向上取整的，说明了顶点数为v的完全图的亏格是不会小于取整前的（v－3）（v－4）/12的值的，所以我们也可以把公式变成n（KV）≥［（v－3）（v－4）/12］。由于图的亏格是其可嵌入的曲面的最小亏格，所以公式中不等式是指该完全图所能够嵌入到的所有曲面的亏格，而等式则是该完全图所能嵌入的曲面的最小亏格，这个曲面的亏格就是该完全图的亏格。杨斯在这里是求完全图的亏格，所以他只用了一个等式。
2、两个公式的关系
从表面上看，这两个公式不仅表现形式不同，而且表示的意义也不同，但实质上这两个公式却是同一个公式的两种不同的表现形式（写法）罢了。它他之间的关系可以形象的这样来描述：即把赫渥特公式用v（KV）＝f（n）表示，则可以把杨斯公式用n（KV）＝f＇（v）来表示，或者说两个公式互为反函数。
把杨斯公式取整理前的形式n（KV）≥（v－3）（v－4）/12变形得
12 n≥v2－7v＋12
0≥v2－7v＋12－12 n
即
v2－7v＋12－12 n≤0
解这个关于v的一元二次不等式得正根是
        v≤（7＋√（1＋48n））/2
再向下取整理就得到了赫渥特公式。
把赫渥特公式取整理前的形式v（KV）≤（7＋√（1＋48n））/2变形得
        2v≤7＋√（1＋48n）
        2v－7≤√（1＋48n）
    4v2－28v＋49≤1＋48n
    v2－7v＋12≤12n或v2－7v＋12－12n≤0
对这个关于v的一元二次不等式进行因式分解成为
    （v－3）（v－4）≤12n
即有
        n≥（v－3）（v－4）/12
再向上取整就得到了杨斯公式。
这两个公式在相互转换的过程中，共同都有一个v2－7v＋12－12n≤0的关到v的一元二次不等式，这就是他们能够相互推导出来的基础。所以才有解这个关于v的一元二次不等式就得到赫渥特公式，而对这个关于v的一元二次不等式进行因式分解就得到了杨斯公式。这本来两个公式就是同一个公式，怎么能利用一个去证明另一个呢。
3、关于v的二元一次不等式v2－7v＋12－12n≤0的来历
由于两个公式均未得到证明是正确与否，尽管两个公式可以相互推导，但也不能用一个去证明另一个。只有把他们共同都有的那个二元一次不等式v2－7v＋12－12n≤0的来历找到了，并且肯定其是正确无误的，才能得出以上赫渥特和杨斯的两个公式都是正确的结论。
我们知道，多阶曲面上的图的欧拉公式v＋f－e＝2－2n已经证明是正确的，其中v、f、e、n分别代表图的顶点数、面数、边数和图或曲面的亏格数。我们还知道可嵌入某曲面上的图中边与面的关系是3f≤2e，把f≤2e/3代入欧拉公式v＋f－e＝2－2n中得
    v＋2e/3－e≥2－2n
    3v＋2e－3e≥6－6n
    3v－e≥6＋6n
再把完全图的边与顶点的关系e＝v（v－1）/2代入上式3v－e≥6＋6n中即可得到
        3v－v（v－1）/2≥6－6n
        6v－v2＋v≥12－12n
        7v－v2－12＋12n≥0
即有
        v2－7v＋12－12n≤0
这就是上述的一元二次不等式。这里为什么要用e＝v（v－1）/2而不用e≤v（v－1）/2呢，是因为我们上面研究的两个公式中的v都是指图的最小完全同态（也是一个完全图）的顶点数。
到此就证明了赫渥特和杨斯的公式都是正确的。由于欧拉公式本身就适用于亏格为0的平面图，所以该两公式也都适用于平面图。这也就证明了四色猜测是正确的。
                         雷  明
二○一四年十二月十一日于长安

注：该文已于二○一四年十二月十四日在《中国博士网》上发表过。