単純ランダムウォークがd2≦ならば再帰的、ｄ≧３ならば非再帰的であるとは

人間は酔っぱらっても偶然に帰路がみつかるが、鳥が酔っぱらうと永遠に迷子になる可能性があるということである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】平面グラフの曲率

　正多角形は無限に多く存在しますが，それでは，「互いに合同な正多角形を隙間も重なりもないように並べて平面を完全に埋める仕方が何通りあるでしょうか？」この問題は昔から知られていて，それが３種類に限ることは以下のようにして証明されます．

　正多角形の中で平面をタイル張りのように隙間なく埋めつくすことができる平面充填形では，各頂点に正ｐ角形がｑ面が会するとすると，正ｐ角形の一つの内角は２（１−２／ｐ）×９０°であり，一つの頂点の回りの内角の和はこれがｑ個集まって四直角ですから，

　　２ｑ（１−２／ｐ）＝４，すなわち，

　　１／ｐ＋１／ｑ＝１／２　　　（ｐ，ｑ≧３）

　　（ｐ−２）（ｑ−２）＝４

で，この条件を満たす（ｐ，ｑ）の組は（３，６），（４，４），（６，３）の３通りしかありません．したがって，平面充填形は正三角形，正方形，正六角形の３通りあり，正三角形，正方形，正六角形配置の３つだけです．このうち正方形のは碁盤，正六角形のは蜂の巣などでおなじみでしょう．

　それらの内部を除いた頂点と辺からなるグラフをそれぞれ「三角格子」，「正方格子」，「六角格子」と呼びます．また，三角格子と六角格子は互いに双対格子になっています．

［補］１種類の正多角形を使った３通りのタイル張り（プラトンの平面充填形）はわかりましたが，それでは２種類以上の正多角形を使ったらどうでしょうか（アルキメデスの平面充填形）？　それを全部求めてみよといわれたらちょっと大変ですが，じつは，アルキメデスの平面充填形は全部で８種あります．アルキメデスの平面充填形の例としては，カゴメ格子があるというわけです．

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

　２次元の平面の中に正多角形は無限に多くあるのに反して，３次元の空間には無限に多くの正多面体は存在しません．平面充填形は，面数が無限大となって全体が一面に広がってしまった正多面体と解釈することができますが，平面充填形の場合と同様にして，正多面体の各面を正ｐ角形，各頂点にｑ面が会するとすると，頂点の周囲は４直角未満ですから，不等式

　　２ｑ（１−２／ｐ）＜４，すなわち，

　　１／ｐ＋１／ｑ＞１／２　　　（ｐ，ｑ≧３）

　　（ｐ−２）（ｑ−２）＜４

が正多角形となる必要条件です．このような整数の組は（ｐ，ｑ）＝（３，３），（３，４），（３，５），（４，３），（５，３）の５通りで，それぞれ，正４面体，正８面体，正２０面体，正６面体，正１２面体に対応します．すなわち，正多面体は正４・６・８・１２・２０面体の５種類あって５種類しかないことはプラトンの時代にはすでに見つけられていて，それらがプラトンの自然哲学で重要な役割を演ずるところから，正多面体はプラトンの立体（Platonic solid）とも呼ばれています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【４】酔歩の再帰性

　各頂点が一定の個数ｑのｐ角形で囲まれている平面グラフは（ｐ，ｑ）正則と呼ばれています．三角格子は（３，６）正則，亀甲格子（六角格子）は（６，３）正則平面グラフです．各頂点の周りに７個の三角形がある（３，７）正則平面グラフはもし正三角形ののタイル貼りによって作ろうとすれば６０°×７＝４２０°＞３６０°となって，平面をはみ出してしまうことになります．

　２次元格子は

　　Ｈ＝４−（ｐ−２）（ｑ−２）＞０，＝０，＜０

の値によって大きく様子が異なり，それに応じて酔歩の再帰性も非常に異なるものになります．その意味でＨは正則平面グラフの曲率と呼ばれます．

　Ｈ＝０となるのは（ｐ，ｑ）＝（３，６），（４，４），（６，３）の３通りの場合に限られ，いずれも平面上のグラフとなり，酔歩はすべて再帰的です．

　Ｈ＞０となるのは（ｐ，ｑ）＝（３，３），（３，４），（３，５），（４，３），（５，３）の５通りの場合に限られ，いずれも正多面体の頂点と辺を平面上に投影して得られる有限グラフとなり，酔歩はすべて再帰的です．一般化された結果を示すと，被覆変換群がＺ^2と同型のと格子上の酔歩は再帰的となります．

　（３，７）正則グラフの場合にはＨ＜０となりますが，一般にＨ＜０のときには道の数が指数関数的に増大するので，出発点に戻る可能性は低く非再帰的になることが証明されています．２次元正則グラフ上の酔歩が常に再帰的であるとは限らないのです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝