■正方形分割(その7)

【6】彩色多項式

頂点の数がnのグラフの頂点をλ色で塗り分けることを考える.ただし隣り合う頂点は異なる色を塗るものとする.可能な塗り分けの総数はn次多項式として表されることを,バーコフが示した.この多項式P(λ)を彩色多項式という.タットは三角形分割された頂点数nの平面グラフのどの彩色多項式PGもφ^2に近い根をもつことを示しました.

PG(φ^2)<φ5-n

φ^2は5番目のベラハ数

ベラハ数Bn=2+2cos(2π/n),n=1,2,・・・

は彩色多項式の根と関係があり,具体的に書くと4,0,1,2,φ^2,3,3.2469,・・・となる.x^3-5x^2+6x-1=0のひとつの根3.2469・・・は7番目のベラハ数であるが,タットはこれを銀の比と呼んだ.φ^2=2.1618・・・が黄金比と関係しているからであろう.三角形分割された頂点数nの平面グラフの彩色多項式のある根は,この値に近い値をとる.

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

[Q]n枚の壁をもつ美術館を警備するのに最低何人の警備員が必要だろうか? (フバータルの問題)

 フバータルの問題に対するフィスクの解答「美術館定理」は単純で美しいものであった(1978年).

[1]領域を三角形分割する.

[2]三角形の頂点を3色で塗り分けて,それぞれの三角駅の頂点に3色すべてが使われるようにする.

[3]使われた数が最も少ない色を指定し,そこに警備員を配置する.

[A] [n/3]人.

[Q]n枚の直角壁をもつ美術館を警備するのに最低何人の警備員が必要だろうか?

[A] [n/4]人.直角美術館はすべて凸四角形分割をもつ.ガウス記号中の4は四角形分割に関係している.

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