■ヒーウッドの公式(その3)

 今回のコラムのテーマは,種数gの閉曲面上の地図の彩色数に関するヒーウッドの公式(必要条件)の導出です.

 以下,

  H(g)=[{7+√(1+48g)}/2]

と同値な

  H(χ)=[{7+√(49−24χ)}/2]

について,一松信先生よりご教示された証明を紹介いたします.

===================================

【1】目標

 面上の多角形分割で,面数F,頂点数V,辺数Eとするとき,オイラー標数

  χ=F+V−E・・・・・・・(1)

の閉曲面(向きづけられるか否かは不問)上の地図は,辺で境される国を別の色で塗るという条件下において,ヒーウッドの数

  H(χ)=[{7+√(49−24χ)}/2]  ([・]は切り捨て)

色あれば塗り分けられる(十分条件).

[注1]この公式は本来χ<0の場合にのみ有効である.ただし結果的にχ=1(射影平面)とχ=0で向きづけられる曲面(輪環面)では必要十分な正しい値(それぞれ6と7)を与える.χ=2(球面)のときには4を与えるが,これは「偶然の一致」であって四色問題の解ではない(∵上の公式を導くときχ<0という条件を本質的に使っている).

[注2]これは十分条件であって,必要条件(どうしてもそれだけの色がいる)ではない.結果的にはχ=0で向きづけられない曲面(クラインの瓶)以外の曲面ではすべて正しく必要十分な色数を与えている.クラインの瓶は唯一の例外で公式の値は7だが,実は6色で必要十分である.必要性は部分的(χの特別な値の例)には19世紀末から知られていたが,最終的にはヤングスとリンゲルとが共同研究して1968年に完全に証明された.

===================================

【2】証明

[1]第1段階

 まず,地図を次のような標準地図に限定しても一般性を失わない.すべての頂点にはちょうど3個国が会している(4個以上が1点に会することはない).−−−それには4個以上が1点に会していたら,その点の近くに新しい1国を作って地図を修正すればよい(必要なら後にその国をつぶしてもとに戻す).

 したがって,面(国)の数をF,頂点数をV,辺数をEとするとき

  3V=2E・・・・・・・(2)

としてよい.

[注]χ=F+V−E・・・・・・・(1)

オイラー標数の定義.この基本量の値は曲面を定めれば一定であることは曲面(2次元多様体)のトポロジーの基本定理で,これは既知とする.向きづけられる場合はχ=2−2g(gはgenus(示性数,種数))であり,彩色数などと関連するのはある意味では自然な話である.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[2]第2段階

 N色で十分であることは,F>Nのとき必ずN−1辺以下の国があることを示せばよい.(F≦NならN色で塗り分けられるのが自明である.)N−1辺以下の国があれば,一時,その国を隣接する国の1つと合併させる.そうすると辺の数が1つ減るから,Fに関する数学的帰納法によってF−1国以下の地図でよいと仮定して(N国以下なら自明)とりあえず塗り分ける.その後,もとの国を独立させたとき周りにN−1国以下しかないから,N−1色で十分なので,残った色をその国に与えればF国のときも正しい・・・という形で数学的帰納法による証明ができる

[注]互いに接するN国があるか否かは必要性の証明には不可欠だが,十分性の証明には不必要である.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[3]第3段階

 少しわかりにくい条件だが次の補助定理を証明する.

  「オイラー標数の閉曲面上の標準地図に対して,ある正の整数Nがあり,F>Nである任意の整数Fについて,不等式

  NF>6(F−χ)・・・・・・・(3)

が成立する.」

という条件があれば,F(>N)国からなる標準地図中に必ずN−1辺以下の国がある.

証)結果を否定すると,すべての国がN辺以上だから,のべNF本以上の辺が2回数えられるので

  NF≦2E・・・・・・・(4)

である.(2)を(1)に代入すると

  χ=F+V−E=F+2/3E−E=F−1/3E

であり,

  F−χ=E/3≧NF/6

すなわち,6(F−χ)≧NFを得る.これは条件(3)の不等式と矛盾する.

系)したがって,その標準地図ではN色で塗り分けられる(第2段階の帰納法).

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

[4]第4段階

 条件(3)を満たす最小のN0を求める.χの正負によって場合分けがいる.

(i)χ>0のとき,N0=6とすれば明らかである.

[注]χ=1のときには実際に6色が必要十分である.χ=0のときには6−1=5辺以下の国があるという事実は正しく,6色で十分なことが導かれる.ただしこれは不完全な結果である.ケンペの方法によって5色で十分なことが証明できる.4色で十分という四色問題はこれとは別の大問題(大定理)である.

(ii)χ=0のときN0=7が最低である.実際向きづけられるときには7色が必要十分である.

(iii)χ<0のとき(このときが本題),N≧7でなければならない.(3)を(N−6)F>−6χ>0と置き換える.N−6>だからFが大きいほど有利である.したがって,F>Nである最低のF=N+1について成立すればよい.

  (N−6)(N+1)+6χ>0

とすると,Nに関する2次不等式

  N^2−5N+(6χ−6)>0

を与える.N>0だから,この解は

  N>{(5+√(25−4(6χ−6))/2}={(5+√(49−24))/2}

を得る.

 Nは整数である(本当に大きい)から,最低の値は

  N0=[右辺+1]=[{7+√(49−24χ)}/2]

[注]具体的な数値を示すと次の通りになる.

  g(向きづけられるときのg)

  N0(ヒーウッドの数):[4]は機械的な計算(前述の注参照)

χ : 2  1  0 −1 −2 −3 −4 −5 −6 −7 −8 −9 −10

g : 2     1     2     3     4     5      6

N0:[4] 6  7  7  8  9  9 10 10 10 11 11  12

===================================