2017-08-26

p-angulation n faces平面グラフとそのグラフ距離『私のためのBrownian map構成法』

Uniqueness and universality of the Brownian map(資料1)
Random Geometry on the Sphere(資料2)
The Brownian map is the scaling limit of uniform random plane quadrangulations(資料3)
平面グラフは、球面上の連結グラフであるので、平面グラフはorientation-preserving homeomorphisms of S2と考えられる
平面グラフには双対グラフがある(多角形をノードにとり、多角形の隣接関係をエッジとしたグラフ)
平面グラフには次のような制約を入れられる
- q角形のみで出来ていて、n個のq角形で出来ているもの
- この集合を $A^q_n$ と書く。A set of all rooted planar q-angulations with n faces と英語で記載するとわかりやすいかもしれない
- $q=3$ のとき、nが奇数のときは $A^{q=3}_n$ には要素がない
- 集合 $A^q_n$ の要素 $M_n \in A^q_n$
はグラフなので、ノードのセットがある。それをと書き、そのグラフのノード間距離(すべてのエッジの長さは１)をと書けば、それはこのグラフを「表している」から、と書くことにする。
- グラフが $G=(V,E)$ のように、ノード集合とエッジ集合とのペアであることと対応するが、エッジ集合の代わりに $d_{gr}$ を用いている。
グラフ同士に「異同」を定量する『メトリック』がある
- ２つの $(m_n^1,d_{gr}^1),(m_n^2,d_{gr}^2)$ があったときに、それらが全く同一のグラフであったときに0となり、異同の程度に応じて正の値をとるような、そんなメトリックがある。Gromov-Hausdorff dissimilarityと言うのがそれである
- このとき、 $(m_n,d_{gr})$ は、ある空間 $K$ の点であって、この空間 $K$ にはメトリック $D_{GH}$ が備わっている、と言い、 $(K,d_{GH})$ と書いて、そのようなメトリックを備えた空間であることを表記する
q-angulationでのfaces数nをどんどん増やしていくと、対応する球面は、点の粗密はあるものの、点で埋め尽くされるようになる。そのとき、どの点とどの点とが近くて、どの点とどの点とが遠いか、というのは、グラフ距離で測れるのは、相変わらずである。ただし、点の数がどんどん増えると、グラフ的距離はどんどん長くなる。したがって、nの値に応じて、１辺の長さを加減するのが適当である。
- 今、 $(\frac{9}{q(q-1)})^{1/4} n^{-1/4}$ という調整係数を用いることにすると
- $(m_n, (\frac{9}{q(q-1)})^{1/4} n^{-1/4} d_{gr})$ というグラフ(とその遠近メトリックと)が定められるが、このnを無限大にしたときの極限が、 $q$ によらず同じであることが知られているのだという
- この極限をブラウニアンマップと呼ぶ
- それを $(m_n,(\frac{9}{q(q-1)})^{1/4} n^{-1/4} d_gr) \rightarrow_{n \to \infty}(m_\infty,D^*)$ と書く
- ここで、nが増えれば増えるほど、平均して、点間距離は $n^{-1/4}$ に比例して長さを調整する必要がある、ということが読み取れる。単純に２次元平面なら、-1/2乗に比例させるのがよいが、グラフ距離の場合には、次元が2ではなく、もっとフラクタル的な込み入った次元なので-1/4となる(らしい)