内容要旨 | | 0.序. グラフはリーマン多様体の離散的類似物としてしばしば扱われるが,近年,無限グラフ上の酔歩に関する研究([Th])や,無限グラフ上で離散的ラプラシアンを考え,そのスペクトルの性質や幾何的な性質に関する研究([DKa][DKe][SS])などが盛んに行われている. 本論文では,非コンパクトな単連結2次元リーマン多様体の離散的類似物として自然に扱うことができる無限平面グラフを対象として,その無限平面グラフGと,Gの双対グラフG*における単純酔歩の性質(非再帰性)の相互関係,および,幾何的な指標である等周不等式の相互関係などを調べた.主なテーマは次の通りである: (1)G上の単純酔歩が非再帰的なとき,G*上の単純酔歩も非再帰的であるか?また,その逆はどうか? (2)Gが双曲的であるとき,G*も双曲的であるか? (3)平面グラフに対して,"曲率"は定義できるのか? 1.準備. グラフGに対して,頂点集合をV(G),(無向)辺集合をE(G)とする.ここで我々の扱うグラフは,V(G)が可算集合で,多重辺・自己ループのない連結無限グラフとする.さらに,m(x)で点xの次数(接続している辺の数)を表し,各点xでm(x)は有限と仮定する(局所有限性).各辺xy∈V(G)に対して向きを与えた時は,[x,y]もしくは-[y,x]で点xから点yへの有向辺を表し,有向辺集合をArc(G)で表す.平面に埋め込み可能で,実際にある埋め込みを与えられたグラフGを平面グラフといい,F(G)でGの面集合,E(F)で面Fの境界をなす辺集合を表わし,また,d(F)で面Fの次数(E(F)の要素の数)を表わす. G上の関数および1-formsのl2-空間をそれぞれ次のように定義する. さらに,外微分dがdf([x,y])=f(y)-f(x)で定義されると,dの随伴作用素d*はとなる.(ここでNG(x)はGにおける点xの近傍,つまり,{y∈V(G)|xy∈E(G)}を表す.)以上より離散的ラプラシアンは次のように定義される: グラフ上の単純酔歩(simple random walk)についてはさまざまな研究がされている.良く知られているのは,2次元以下の格子では再帰的で,3次元以上の格子では非再帰的という事実である.一般のグラフにおける単純酔歩の挙動の判定には、次の定理([Ly])を使う. 定理1.1(Lyons).G上の単純酔歩が非再帰的であることと,次の条件を満たすArc(G)上のが存在することは同値である: さて,本論文では次の2種類の等周定数(G)と*(G)を用いる. 上記のそれぞれの定数は,分母が有限グラフKの"面積",分子がKの境界の"長さ"に対応しているという意味で,多様体での等周定数の離散的類似物になっていると思える. 等周定数(G)は,リーマン多様体におけるチーガー定数([Ch])の離散的類似物として知られているが,それは-のスペクトルの下限(G)との関係が次の定理のようになっているためである: 定理1.2([DKe][DKa]).任意のグラフGに対して, 上の定理より,(G)>0ならば(G)>0となり,よって,G上の単純酔歩は強い非再帰性を持つ.平面グラフGは前に述べたように,非コンパクトな単連結2次元リーマン多様体の離散的類似物として扱っているので,(G)>0なる性質を持つ平面グラフGは双曲的であると考えられる. 一方,組み合わせ群論において,*(G)>0はグラフGに付随する群が双曲的であることを意味しているので([LS][GH][Gr]),*(G)>0という性質を持つ平面グラフGも,双曲的であると考えられる.次の事実は組み合わせ群論では良く知られているものを,グラフの言葉で表わしたものである: 定理1.3(Small Cancellation Theory).各F∈F(G),x∈V(G)に対して3m0m(x)<∞,かつ,3l0d(F)<∞と仮定する. 2.平面グラフ上の単純酔歩. Gが平面グラフならば,Gの双対グラフG*が存在する.さて,単純酔歩の挙動はG上とG*上と同じであろうか.この問いに対して次の結果を得た. 定理2.1.Gを次数が有界であるような無限平面グラフとする.G上の単純酔歩が非再帰的ならば,Gの双対グラフG*上の単純酔歩も非再帰的である. 証明方針は,G上に存在する定理1.1の条件を満たす1-formを用いてG*上に条件を満たす1-formを構成してする.しかし,直接構成するのは困難なので,その際,GとG*をより密接につなぐ放射グラフ(Radial graph,[AR]参照)の導入や,適当なグラフの各種変形を用いている点が本質となっている. グラフGをある2次元多様体の離散モデルとすればG*も同じ多様体のGに付随した離散モデルと考えられるので,上の定理2.1は期待通りのものである.しかし次数の有界性は一般には外せない.実際,次数の有界性がない無限平面グラフGで,G上の単純酔歩は非再帰的だがG*上の単純酔歩は再帰的になるグラフ("Yoh-Chang graph")が構成出来た. 3.平面グラフにおける等周不等式. 無限平面グラフにおける(・)と*(・)の関係について主に次の定理を得た: 定理3.1. G*をGの双対グラフとする.このとき,*(G)が正であることと(G*)が正であることは同値である. 定理3.2. d(F)とm(x)がGにおいて有界とする.このとき,次の4つの主張は互いに同値である: 定理3.2もやはり期待通りのものである.しかし,定理2.1と同様に有界条件は一般にははずせない.実際,定理2.1における反例Gがそのまま,(・)は正であるが,*(・)が0になる例になっているためである.この反例Gは,(G)>0だが,(G*)=0となっている. 4.平面グラフの組み合わせ的曲率. 多様体における次の事実は良く知られている: 事実4.1.Xを単連結で,距離空間として完備なものとする.断面曲率K(X)がK(X)-2<0であるとき,Xにおいて,滑らかな閉曲線Cを境界に持つ各円板Dに対して が成立する.さらに,K(X)0であることと,Xにおいて滑らかな閉曲線Cを境界に持つ各円板Dが を満たすことは同値である. さて,上記の事実に対応する性質を持つようなグラフの"曲率"は定義できるのか? 本論文では,平面グラフに対して,多様体における断面曲率の離散的類似物を導入し,それによるグラフの双曲性に対する特徴付けを与えた. 平面グラフGの各点xに対して,点xにおける組み合わせ的曲率G(・)は次のように表現される.この曲率の定義自体は,別の文脈で石田([Is])によって導入された: ここで,F1,F2,…,Fm(x)は点xの周りの面を表わす. Gromovは別の曲率(・)を彼の論文([Gr])で導入したが,G*でGの双対グラフを表わし,f*∈V(G*)をf∈F(G)に対応するものとしたとき,これらの曲率の間には(f)=(f*)という関係がある. 上記の曲率を用いて,次の定理を得た: 定理4.2. (i)各点x∈V(G)に対してG(x)<0であるとき,*(G)>0となる. (ii)各面F∈F(G)に対して(F)<0であるとき,(G)>0となる. 定理4.2の証明においては,次の命題で示されるG(・)の持つ予想外の性質が,本質的である. 命題4.3.G(・)<0であることとG(・)-1/1806は同値である. 5.付記. 本論文では以上のことを中心に議論されているが([H1][H2]),その他に,無限グラフとその線グラフ(line graph)における酔歩の挙動の関係,および,等周定数の関係などに関して得られた結果([H3])についても述べてある. 参考文献[AR]D.S.Archdeacon and R.B.Richter,Construction and classification of self-dual polyhedra,J.Combin.Theory,Ser.B.54(1992),37-63.[Ch]J.Cheeger,A lower bound for the lowest eigenvalue of the Laplacian,Problems in Analysis,A Symposium in honor of S.Bochner(1970),Princeton Univ. Press,195-199.[DKa]J.Dodziuk and L.Karp,Spectral and function theory for combinatorial Laplacians,A.M.S.Contemporary Mathematics 73(1988),25-40.[DKe]J.Dodziuk and W.S.Kendall,Combinatorial Laplacians and isoperimetric inequality,in "From local times to global geometry,control and physics"K.D.Elworthy ed.,Pitman Research Notes in Mathematics Series 150(1986),68-74.[GH]E.Ghys and P.de la Harpe ed.,Sur les groupes hyperboliques d’apres Mikhael Gromov,Progress in mathematics 83(1990),Birkhauser.[Gr]M.Gromov,Hyperbolic groups,Essays in group theory,S.M.Gersten ed.,M.S.R.I.Publ.8,Springer,1987,pp.75-263.[H1]Y.Higuchi,Isoperimetric inequalities of infinite planar graphs,in preparation.[H2]Y.Higuchi,Random walks on infinite planar graphs and their duals,in preparation.[H3]Y.Higuchi,Isoperimetric inequality and random walks of an infinite graph and its line graph,in preparation.[Is]M.Ishida,Pseudo-curvature of a graph,lecture at ’Workshop on topological graph theory’,Yokohama National Univ.,31st Oct.1990.[Ly]T.Lyons,A simple criterion for transience of a reversible Markov chain,Ann.Probab.11(1983),393-402.[LS]R.S.Lyndon and P.E.Schupp,Combinatorial group theory,Springer,1977.[SS]P.W.Sy and T.Sunada,Discrete Schodinger operator on a graph,Nagoya Math.J.125(1992),141-150.[Th]C.Thomassen,Isoperimetric inequalities and transient random walks on graphs,Ann.Probab.20(1992),1592-1600. |