³ÎΨÏÀ¤È¥Ñ¡¼¥·¥¹¥Æ¥ó¥È¥Û¥â¥í¥¸¡¼

確率論とパーシステントホモロジー

白井朋之1

九州大学 IMI Dec. 23, 2017

1

ENCOUTNERwithMATHEMATICS70 @Chuo Univ. on Dec.22-23, 2017, Supported by JSPS(26287019, 17K18740); JST CREST(15656429) 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 1 / 72

Contents

1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 2 / 72 1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 3 / 72

データからパーシステント図へ

1 各種データ 点データ ⊂ RN 画像データ (pixel, voxel) 関数のプロファイル 多様体，コンパクト集合．．． 2 単体複体，セル複体などのフィルトレーション (単調増大族) (=_{⇒ パーシステント加群)} 3 各次元のパーシステント図． 4 パーシステント図に対するカーネル法 Data_{→ F(Cpx)}f _{→ PD}g _{→ H}h k 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 4 / 72

確率論とトポロジー

I

George P´olya (1921): 1, 2次元単純ランダムウォークは再帰的，3 次

元以上の単純ランダムウォークは非再帰的．

Mark Kac (1966): Can one hear the shape of a drum? ∞ ! i=1 e−λit _∼ |Ω| 2πt − L 4 1 √ 2πt + (1− r) 1 6 (t→ 0) Ωは境界をもつ 2 次元領域，L は境界の長さ，r は穴の個数． アイデアはブラウン運動を Ω 上で走らせる． ´ Emile Picard (1878): 全複素平面上の正則函数 (整関数) f の値域が C \ {a, b} に含まれれば定数関数である．(Picard の小定理) Davis のアイデア (1975)：C \ {−1, 1} 上でブラウン運動 f (Bt)を走 らせて巻きつきがあることを示す． 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 5 / 72

確率論とトポロジー

II

Broadbent-Hammersley, Harris, Russo (1950後半から 1960 年代)：

パーコレーションの問題 (化学者 Paul Flory (1940) によって考えら れた)．1960 年代に数学の問題として定式化． 例：パーコレーション確率 θ(p) := Pp(|C0| = ∞) の挙動． Harry Kesten (1982): Z2 上のボンドパーコレーションの臨界確率は 1/2であることを示す． Figure:p = 1/4, 1/2, 3/4 パーコレーションの問題 = ランダムなグラフの「連結性」の問題 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 6 / 72

Random vs Statistical vs Deterministic

“My overall conclusion is that I believe stochastic methods will transform pure and applied mathematics in the beginning of

the third millenium. Probability and statisticswill come to be

viewed as the natural tools to use in mathematical as well as scientific modeling.”

—The Dawning of the Age of Stochasticity,

David Mumford, 2000.

“I predict a new subject of statistical topology. Rather than count the number of holes, Betti numbers, etc., one will be more

interested in thedistributionof such objects on noncompact

manifolds as one goes out to infinity.” —Isadore Singer, 2004

その他のランダムトポロジーに関する研究

Kolmogorov-Barzdin (1960s), Gromov-Guth (2011): グラフ (単体複 体) のユークリッド空間への埋め込み． Adler (1980s), Adler-Taylor(2003),栗木-竹村 (2000s): ガウス場の末 尾確率の評価 (オイラー標数)．

Pippenger-Schleich (2006)： ランダム triangulated surfaces

Dunfield-Thurston (2006): ランダム 3 次元多様体．

Farber-Kappeller (2007), Farber(2008): ランダムリンケージ

(Random linkages)

ランダム平面地図 (Random planar map): Schramm(2006, ICM) の問 題．Le Gall, Miermont, Sheffield, Curien...

n個の p 角形からなる平面グラフを一様ランダムに取り出し有限距

離空間 (Gn,p, d)とみなし，

Schramm-Loewner-Evolution(SLE) 2次元確率モデルのスケール極

限：Schramm (2000), Werner, Smirnov, Lawler.

Linial-Meshulam (2006), Meshulam-Wallach (2009): ランダム

1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 9 / 72

確率論とトポロジー

III

Erd˝os-R´enyi ランダムグラフ G(n, p) (1959,1960): n点上の完全グ

ラフにおいて，各辺独立に確率 p で辺を残して (確率 1 − p で辺を 除去して) 得られるグラフ．

Figure:G (10, p). From p = 0.1 to p = 0.9 with increment 0.1

G (n, p)に対して， E[次数] = (n − 1)p, E[辺の本数] = "_n 2 # p. p(n)∼c/nとすると，平均次数が ∼ c となる． 次数の分布は平均 c のポアソン分布に近い． 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 10 / 72

Erd¨os-R´enyi

ランダムグラフの相転移

I

1 p(n) = c/n(c < 1): O(log n)より大きいサイズの連結成分は存在し ない． 2 p(n) = 1/n: 最大の連結成分のサイズはO(n2/3). 3 p(n) = c/n(c > 1): 最大の連結成分のサイズはO(n). 巨大連結成分

(giant component)という．それ以外の連結成分のサイズは O(log n).

4 p(n) = log n/n: 連結性に対する閾値関数．つまり， PG (n,p(n))(G は連結である) → $ 0 p(n) = log n−ω(n)_n 1 p(n) = log n+ω(n)_n ただし，ω(n) は n → ∞ で発散する任意の数列．

Figure: From p = 0.1 to p = 0.9 with increment 0.1

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 11 / 72

Erd¨os-R´enyi

ランダムグラフの相転移

II

1 p(n) = c/n(c < 1): O(log n)より大きいサイズの連結成分は存在し ない． 2 p(n) = 1/n: 最大の連結成分のサイズはO(n2/3). 3 p(n) = c/n(c > 1): 最大の連結成分のサイズはO(n). 巨大連結成分

(giant component)という．それ以外の連結成分のサイズは O(log n).

Figure:n = 1000. From the left, p = 0.8/n, 1/n, 2/n.

Erd¨os-R´enyi

ランダムグラフの相転移

III

1 p(n) = log n/n: 連結性に対する閾値関数．つまり， PG (n,p(n))(G は連結である) → $ 0 p(n) = log n−ω(n)_n 1 p(n) = log n+ω(n)_n ただし，ω(n) は n → ∞ で発散する任意の数列．

Figure:G (n, log n/n) for n = 100.

p(n) = (1 + ϵ) log n/n: 孤立点の個数 In の平均は EIn= n(1− p(n))n−1 ≈ ne−np(n)= n−ϵ. p(n) = (log n + c)/n： 孤立点の個数 In に対する ポアソンの少数法則． ˜ β0≈ In⇒ Poisson(ed −c). 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 13 / 72

Linial-Meshulam

複体

Kn を n 点上の完全複体とする． Knの各 ℓ-単体 σ ∈ (Kn)ℓ を独立に確率 p で選んで集めた集合を T とあらわす． Y := (_Kn)(ℓ−1) % &' ( (ℓ− 1)-完全スケルトン * _%&'(T ℓ単体のランダム集合 はランダムな ℓ-次元複体を定める．このとき，Y _{∼ Y}ℓ(n, p)とあら わし，ℓ-Linial-Meshulam複体とよぶ． 例：(ℓ = 1). Y = (Kn)(0) % &' ( n個の孤立点 * _%&'(T ランダム辺集合 例：(ℓ = 2). Y = (_Kn)(1) % &' ( n点上の完全グラフ * _%&'(T ランダム 2-単体集合 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 14 / 72

Linial-Meshulam

複体

ℓ = 1: Y1(n, p)は Erd˝os-R´enyi ランダムグラフ G(n, p). Y _{∼ Y}ℓ(n, p)とすると， ˜ Hq(Y ) = 0 (q = 0, 1, . . . , ℓ− 2). Y に関して ˜βℓ−1(Y )は単調減少， ˜βℓ(Y )は単調増加．つまり， Y _{⊂ Y}′ _ならば ˜ βℓ−1(Y )≥ ˜βℓ−1(Y′), β˜ℓ(Y )≤ ˜βℓ(Y′). さらに， ˜ βℓ−1(Y ) = "_n − 1 ℓ # + ˜βℓ(Y )− fℓ(Y ).

Linial-Meshulam

複体に対する連結性の

Threshold

Yℓ(n, p): ℓ-Linial-Meshulam複体. (ℓ = 1) Erd¨os-R´enyi (1960) P(G(n, p) が連結) = P( ˜H0(Y1(n, p)) = 0)→ $ 0 p =log n−ωn n 1 p =log n+ωn n (ℓ = 2, q = 2) Linial-Meshulam (2006), (ℓ_{≥ 2, ∀q: 素数) Meshulam-Wallach (2009)} P( ˜Hℓ−1(Yℓ(n, p),Zq) = 0)→ $ 0 p = ℓlog n−ωn n 1 p = ℓlog n+ωn n ˜ Hℓ−1(Yℓ(n, p),Z) = 0に対する threshold についてはまだ未解決． Hoffman-Kahle-Paquetteが部分的な結果を出している．

1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 17 / 72

点過程，フィルトレーション，パーシステントホモロ

ジー

Input 1: 点クラウドデータと点過程 ⇓ ˇCech or Rips-Vietoris 複体などを通して． Input 2: フィルトレーション = 単体複体の増加列 ⇓ Output: パーシステント図 !10 !5 0 5 10 !10 !5 0 5 10 Poisson 1 2 3 4 t!0 1 2 3 4 t!1 1 2 3 4 t!2 1 2 3 4 t!3 1 2 3 4 t!4 2 4 6 8 2 4 6 8 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 18 / 72

点過程，フィルトレーション，パーシステントホモロ

ジー

Input 1: 点クラウドデータと点過程 ⇓ ˇCech or Rips-Vietoris 複体などを通して． Input 2: フィルトレーション = 単体複体の増加列 ⇓ Output: パーシステント図 !10 !5 0 5 10 !10 !5 0 5 10 Poisson 1 2 3 4 t!0 1 2 3 4 t!1 1 2 3 4 t!2 1 2 3 4 t!3 1 2 3 4 t!4 2 4 6 8 2 4 6 8 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 19 / 72

Erd¨os-R´enyi (1960)

の論文から

In fact,the evolution of graphscan be seen as a rather

simplified model of the evolution of certain communication nets (railway, road or electoric network systems, etc.) of a country or some other unit . . .

. . . one could obtain fairly reasonable models ofmore complex

real growth processes(e.g. the growth of a complex

communication net consisting of different connections, and even of organic structures of living matter, etc.)

— On the evolution of random graphs, Erd˝os-R´enyi (1960).

スケールフリーネットワーク

n_{→ ∞ の挙動を見る際に，p = p(n) として n に依存させて考える．}

1 Watts-Strogatz (1998), Albert-Barabashi (1999)：スケールフリー

ネットワーク, ネットワークトポロジーの研究．

(i) scale free: 次数分布がべき分布 P(k) ∼ k−γ _に近い．

(ii) small world property: グラフの直径が小さい．

(iii) cluster property: 各点の近傍グラフがクリークに近い．

Figure:Erd¨os-R´enyi, Duncan-Watts, Albert-Barabashi

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 21 / 72

Coupling of Erd¨os-R´enyi graphs

Figure:Independent samples from G (20,0.07) and G (20,0.1)

When p < p′,

E[β0(G (n, p))]≥ E[β0(G (n, p′))] ??

Couplingof G (n, p) and G (n, p′) is constructed by usingcommon randomness.

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 22 / 72

Coupling of Erd¨os-R´enyi graphs

Figure:Coupling of G (20,0.07) and G (20,0.1)

When p < p′_,

β0(G (n, p))≥ β0(G (n, p′))

Erd¨os-R´enyi graph process

For each edge e∈ Enof the complete graph Kn= (Vn, En), we assign

uniform random variable t(e) from [0, 1]. Take asublevel setof

t : En→ [0, 1]:

X (p) := Vn* {e ∈ En: t(e)≤ p}.

{X (p)}0≤p≤1 is calledErd¨os-R´enyi random graph process.

Since_{{X (p)}}0≤p≤1 is increasing

% &' (

filtration

, ˜β0(X (p)) is decreasing.

Erd¨os-R´enyi graph and ℓ-Linial-Meshulam complex process

Figure:Erd¨os-R´enyi graph process (ℓ = 1)

Figure:2-Linial-Meshulam process (ℓ = 2)

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 25 / 72 1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 26 / 72

Minimum spanning tree (MST)

Let Kn= (Vn, En) be the complete graph with n vertices and for each edge e _{∈ E}n, a uniform r.v. t(e) on [0, 1] is assigned independently. Minimum spanning treeis the spanning tree T which minimizes the weight wt(T ) =! e∈T t(e), Wn:= min T∈Sn wt(T ), where _Sn is the set of spanning trees in Kn. Remark that

|Sn| = nn−2 by Cayley’s theorem (1889). 0.1 0.5 0.3 0.4 0.2 0.6 0.1 0.5 0.3 0.4 0.2 0.6 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 27 / 72

Frieze’ result on MST

Theorem (Frieze, 1985)

As n_{→ ∞,} E[Wn]→ ζ(3) = 1.20206 . . . .

Remark. 1) The weight distributioin is not necessarily uniform distribution.

2) Kncan be replaced with other “balanced” graphs.

3) Asympotic expansion is also studied(Cooper et al., 2012). E[Wn] = ζ(3) +c1

n +

c2+ o(1)

n4/3 .

4) Minimum 1-matching in Kn,n is considered and the expected minimum

weight converges to ζ(2) = π2/6 (Aldous, M´ezard-Parisi).

Theorem (Janson, 1995)

(CLT) As n_{→ ∞,}

√

n(Wn− ζ(3)) → N(0, σ2), σ2= 6ζ(4)− 4ζ(3) = 1.68571....

A generalization of the problem of MST

The purpose of the first part of this talk is to extend Frieze’s result to higher dimensional objects.

(random weighted) graph =⇒ (random weighted) simplicial complex spanning tree =⇒ spanning acycle

We can interpret the weight of the minimum spanning tree in terms ofpersistent homology.

Kruskal’s algorithm of finding MST =_{⇒ Erd¨os-R´enyi graph}process.

Figure:Erd¨os-R´enyi random graph process for n = 6

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 29 / 72

Filtration

X = (X (t))t≥0： an increasing sequence of simplicial complexes.

1 2 3 4 t!0 1 2 3 4 t!1 1 2 3 4 t!2 1 2 3 4 t!3 1 2 3 4 t!4 1 2 3 4 t!5

...

X (0) ={1, 2, 3, 4, 12, 23_}, T (1) =· · · = T (23) = 0, X (1) =_{{1, 2, 3, 4, 12, 23,}14,34_} T (14) = T (34) = 1, X (2) =_{{1, 2, 3, 4, 12, 23, 14, 34,}13_} T (13) = 2, X (3) ={1, 2, 3, 4, 12, 23, 14, 34, 13,123_} T (123) = 3, X (4) =_{{1, 2, 3, 4, 12, 23, 14, 34, 13, 123,}134_} T (134) = 4.

T (σ) denotes thebirth timeof σ.

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 30 / 72

Persistent homology group (I)

ℓ-th chain group as a graded module on the polynomial ringF[x]:

Cℓ(X) := ) t≥0

Cℓ(X (t),F) = {(ct)t≥0: ct ∈ Cℓ(X (t),F)} with the right-shift actions

xs _{· (c}0, c1, . . . ) := (0, . . . , 0_{% &' (} s-times , c0, c1, . . . ) Boundary operator ∂ℓ(x) : Cℓ(X) → Cℓ−1(X): ∂ℓ(x)⟨⟨v0v1. . . vℓ⟩⟩ = ℓ ! j=0 (₋₁₎jxT(σ)−T(σj)_⟨⟨v 0v1. . . vj−1vj+1. . . vℓ⟩⟩.

Matrix representation of boundary operator

1 2 3 4 t!0 1 2 3 4 t!1 1 2 3 4 t!2 1 2 3 4 t!3 1 2 3 4 t!4 1 2 3 4 t!5

...

∂1(x) = ⎡ ⎢ ⎢ ⎣ X0\X1 ⟨12⟩ ⟨13⟩ ⟨14⟩ ⟨23⟩ ⟨34⟩ ⟨1⟩ −1 −x2 −x 0 0 ⟨2⟩ 1 0 0 −1 0 ⟨3⟩ 0 x2 0 1 −x ⟨4⟩ 0 0 x 0 x ⎤ ⎥ ⎥ ⎦, ∂2(x) = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ X1\X2 ⟨123⟩ ⟨134⟩ ⟨12⟩ x3 0 ⟨13⟩ −x x2 ⟨14⟩ 0 −x3 ⟨23⟩ x3 0 ⟨34⟩ 0 x3 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦

Chain complex: we can see that ∂ℓ(x)◦ ∂ℓ+1(x) = 0 and · · ·∂ℓ+2−→ C(x) ℓ+1(X) ∂ℓ+1(x) −→ Cℓ(X) ∂ℓ(x) −→Cℓ−1(X) ∂ℓ−1(x) −→ · · ·

Persistent homology group (II)

Structure theorem for persistent homology for_{X = {X (t)}t≥0}:

PHk(X) := Zk(X)/Bk(X) ∼= s ) i=1 (xbi_)/(xdi_)⊕ s+r ) i=s+1 (xbi₎

(xbi_)/(xdi_{)⇐⇒ persistent interval [bi, di) for an i-th homology class}

bi : birth time, di : death time, ℓi := di− bi : lifetime.

2 4 6 8 2 4 6 8 Figure:Persistence diagram

For simplicity, we suppose r = 0, i.e., finite lifetimes.

The sum of lifetimes of k-dimensional homology classes: Lk= s ! i=1 ℓi. 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 33 / 72

Persistent homology for random simplicial complex

deterministic

X = (X (t))t≥0⇒ k-th persistence diagram ⇒ the sum of lifetimes Lk

stochastic

Let_{X = (X (t))}t≥0 be an increasing stochastic process of simplicial complexes, e.g., the Erd¨os-R´enyi graph process

X = (X (t))t≥0=⇒ random k-th persistence diagram, k = 0, 1, 2, . . .

⇐⇒ point process ξ on ∆ = {(x, y) ∈ R2: x ≤ y}

=_{⇒ the sum of lifetimes L}k(ξ)

Observation

When_{X = (X (t))}0≤t≤1 is the Erd¨os-R´enyi graph process,

the lifetime sum L0(ξ) = the weight of MST

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 34 / 72

Spanning ℓ-acycle

Spanning tree T in the complete graph Kn satisfies the following:

1 |T | = n − 1 =0n−1 1 1 . 2 H˜₀(T ) = 0 ⇐⇒ connected. 3 _H˜_{1(T ) = 0 ⇐⇒ no cycle.}

Definition

A subset T of ℓ-faces is aspanning ℓ-acyclein the ℓ-complete complex

Kn(ℓ)over{1, 2, . . . , n} if 1 |T | =0n−1 ℓ 1 . 2 H˜_ℓ −1(XT) = a finite group 3 H˜_ℓ(X_T) = 0 ⇐⇒ no ℓ-dim. cycles. XT = Kn(ℓ−1) % &' ( (ℓ− 1)-complete skeleton *T

This definition was given by G. Kalai(1983) as_{Q-acyclic simplicial}

complex.

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 35 / 72

Example: Triangulation of the projective plane

RP

2

Facets: T =_{{124, 125, 135, 136, 146, 234, 236, 256, 345, 456}} 1 |T | =06−1 2 1 = 10. 2 H˜₁(X_T) =Z₂. 3 H˜₂(X_T) = 0 ⇐⇒ no 2-dim. cycles. 1 2 3 1 2 3 4 5 6 Figure:A triangulation ofRP2_{. (|V | = 6, |E | = 15, |F | = 10)} 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 36 / 72

Extension of Cayley’s theorem

Theorem (Kalai ’83)

Let _Sn(ℓ)be the set of spanning ℓ-acycle with (ℓ− 1)-complete skeleton on

n-vertices. Then, _!

T∈Sn(ℓ)

| ˜Hℓ−1(T )|2= n(

n−2 ℓ ).

For ℓ = 2, since ˜H1(T ) is trivial for n = 4, 5, |S4(2)| = 4( 4−2 2 ) = 4, |S(2) 5 | = 5( 5−2 2 ) = 125

For ℓ = 2 and n = 6, since ˜H1(T ) ∼=Z2for 12 spanning 2-acycles, |S6(2)| = 46620 ̸= 6(

6−2

2 ) = 66= 46656

Such a 2-complex is a triangulation of the projective plane as seen before.

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 37 / 72

Determinantal formula

X : a simplicial complex with ˜Hℓ−2(X(ℓ−1)) = 0.

L: an (ℓ_{− 1)-acycle, S: ℓ-faces with |S| = |K |.}

∂ℓ= 2 Xℓ−1\Xℓ Xℓ K ∂_K L ∗ 3 = 2 Xℓ−1\Xℓ S Sc K ∂_KS ∗ L ∗ ∗ 3

det ∂KS̸= 0 iff S is an ℓ-acycle.

Proposition (Matrix-Tree type theorem)

Let L_{∈ S}(ℓ−1) and set K = X_{ℓ−1\ L. Then,}

det(∂K∂KT) = ! S∈S(ℓ) (det ∂KS)2= ! S∈S(ℓ) | ˜H_ℓ−1(XS)|2 When ℓ = 1,_{| ˜}H_ℓ−1(XS)| = 1, this gives us det(∂K∂KT) =|S(1)|.

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 38 / 72

ℓ-Linial-Meshulam process

[n] =_{{1, 2, . . . , n}}

Fℓ:=0_ℓ+1[n]1: the set of ℓ-faces or (ℓ + 1)-subsets of [n]. {t(σ) : σ ∈ Fℓ}: i.i.d. uniform r.v.’s on [0, 1]： birth times.

Y(ℓ)(t) = Kn(ℓ−1)

% &' ( (ℓ− 1)-complete skeleton

* {σ ∈ Fℓ: t(σ)≤ t}

% &' (

ℓ-faces born before t .

(ℓ = 1) Y(1)_{(t) is the Erd¨os-R´enyi graph process (Y}(1)_{(t)= G (n, t)).}d

(ℓ = 2) Y(2)_{(t) starts from K}

n at time 0, a 2-face is attached at random birth time, and ends up with the complete 2-skeleton.

Sum of lifetimes of homology classes

(ℓi)i = di− bi: lifetimes. Lℓ−1:=4iℓi 2 4 6 8 2 4 6 8

Theorem (Hiraoka-S. (’17))

1 _{Let ˜βℓ}

−1(t) be the reduced Betti number at time t. Then,

Lℓ−1= 5 ∞ 0 ˜ βℓ−1(t)dt. 2 _{Let T}(ℓ)

min be the minimum spanning ℓ-acycle. Then,

Lℓ−1= wt(Tmin(ℓ))− wt(Xℓ−1\ T (ℓ−1) min ),

Exact computation

Let T (X ; x, y ) be a generalization ofTutte polynomialfor X defined by

T (X ; x, y ) = !

F⊂Xℓ

(x_{− 1)}βℓ−1(XF)_{(y− 1)}βℓ(XF)_{, (1)}

where XF = X(ℓ−1)* F and the sum is taken over all ℓ-faces.

Proposition (Hiraoka-S (’17))

Let T be as in (1). For the ℓ-Linial-Meshulam process over n vertices, E[Lℓ−1(n)] =E[ min T∈Sn(ℓ) wt(T )] = 5 1 0 1_{− t} t Tx(Kn(ℓ);1_t,_1−t1 ) T (Kn(ℓ);1_t,_1−t1 ) dt.

Remark: for ℓ = 1, this is proved by J.M.Steele. Exact values: for ℓ = 2

n 4 5 6 7 8

E[L1(n)] 6/5 1817/924 5337295/1939938 ?? ??

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 41 / 72

Asymptotic result

Theorem (Hiraoka-S. (’17))

Let Lℓ−1(n) be the lifetime sum of (ℓ− 1)-st persistent homology for the ℓ-Linial-Meshulam process on n vertices,

E[Lℓ−1(n)] =E[ min

T∈S(ℓ)_(n)wt(T )] = O(n

ℓ−1₎

as n_{→ ∞, where wt(T ) :=}4_σ∈Tt(σ).

See Random Structures and Algorithms 51 (2017), 315–340.

Lower bound: Use a representation for minimum spanning acycle. Upper bound: Use a Kruskal-Katona type result (by Linial et al.) to

E[Lℓ−1(n)] = 5 1 0 ˜ β_ℓ−1(t)dt. 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 42 / 72

Betti number ˜

β

1

(Y

(2)

(t)) in the case ℓ = 2

˜ β1(Y(2)(0)) = ˜β1(Kn) = "_n − 1 2 # ↘ 0 = ˜β1(Y(2)(1)) 0.2 0.4 0.6 0.8 1.0 20 40 60 80

Figure:β˜1(Y(2)(t)) for 2-Linial-Meshulam process when n = 15.

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 43 / 72

Limiting values I

ℓ−1 For ℓ = 1, let t∗

ℓ = 1.

For ℓ_{≥ 2, let tℓ}∗be the unique root in (0, 1) of the equation (ℓ + 1)(1− t) − (1 + ℓt) log t = 0.

Conjecture (Hiraoka-S (’17))

I_ℓ−1:= lim n→∞ E[Lℓ−1(n)] nℓ−1 = 1 2ℓ! 65 t∗ ℓ 0 (log s)2 (1_{− s)}ℓds + ℓ + 1 (1_{− t}∗ ℓ)ℓ−3(1 + ℓtℓ∗)2 7 . When ℓ = 1, I0= 1 2 5 1 0 (log s)2 1_{− s} ds = ζ(3).

Theorem (Kanazawa-Hino)

For_{∀p ∈ [1, ∞), Lℓ−1→ Iℓ−1} in Lp _{as n→ ∞.} 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 44 / 72

Clique (Flag) complex process

The clique complex Cl(G ) associated with a graph G is the maximal simplicial complex having G as a 1-dimensional skeleton.

X(1)_{(t): Erd¨os-R´enyi graph process}

C(t) = Cl(X(1)(t)), 0_{≤ t ≤ 1,}

The process starts from the 0-skeleton, i.e., n isolated vertices, and

ends up with ∆n−1. Namely,

∆(0)_n−1=_{C(0) ⊂ C(t) ⊂ C(1) = ∆}n−1.

The main difference from the Linial-Meshulam case is absence of monotonicity of Betti numbers.

Figure:Clique complex process on 5-vertices

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 45 / 72

Persistence diagram

0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 birth death pd1_1000_40 2 4 6 8 10 12 14 16 18

Figure:Persistence diagram for Erd¨os-R´enyi clique complex n = 40

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 46 / 72

Lifetime sum fo clique complex process

Proposition (Hiraoka-S (’17))

Let Lℓ−1(n) be the lifetime sum for the clique complex process on n-vertices. Then, for ℓ = 1, 2,

cnℓ−1≤ E[Lℓ−1(n)]≤ Cnℓ−1log n and for ℓ_{≥ 3,}

cn(ℓ+2)(ℓ2ℓ−1) ≤ E[L_ℓ−1(n)]≤ Cnℓ−1

Recently, the following was shown.

Theorem (Kanazawa-Hino)

As n→ ∞,

E[Lℓ−1(n)] = Θ(n

(ℓ+2)(ℓ−1)

2ℓ ) (ℓ = 1, 2, . . . )

♠ Limiting constant is yet to be obtained.

1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題

点過程，フィルトレーション，パーシステントホモロ

ジー

Input 1: 点クラウドデータと点過程 ⇓ ˇCech or Rips-Vietoris 複体などを通して． Input 2: フィルトレーション = 単体複体の増加列 ⇓ Output: パーシステント図 !10 !5 0 5 10 !10 !5 0 5 10 Poisson 1 2 3 4 t!0 1 2 3 4 t!1 1 2 3 4 t!2 1 2 3 4 t!3 1 2 3 4 t!4 2 4 6 8 2 4 6 8 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 49 / 72

Atomic configuration of SiO2

0 5 10 15 20 25 0 5 10 15 20 25 0 5 10 15 20 25 30 0 5 10 15 20 25 0 5 10 15 20 250 5 10 15 20 25 30 !10 !5 0 5 10 15 !5 0 5 10 !15 !10 !5 0 5 10

Atomic Configuration of SiO

2

liquid

glass

crystal

Note: they are obtained by MD simulations

Figure:T. Nakamura, Y. Hiraoka, A. Hirata, et al. PNAS 2016

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 50 / 72

1-dim. Persistence diagram

1-dim Persistence diagrams of SiO

2

liquid

glass

crystal

Figure:T. Nakamura, Y. Hiraoka, A. Hirata, et al. PNAS 2016

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 51 / 72

Point clouds and point processes

Two types of random points are mainly considered.

1 Binomial process: {X_i}_i: i.i.d. random variables.

Xn:={X1, . . . , Xn}

2 _{Point process: random point configuration over}Rd_.

Conf(Rd) =_{{Φ =}!

i

δxi : xi∈ R

d_{, Φ(K ) <}

∞ if K is cpt. }

Figure:Binomial model

!10 !5 0 5 10 !10 !5 0 5 10 Poisson !10 !5 0 5 10 !10 !5 0 5 10 Ginibre

Figure:Point processes 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 52 / 72

Topology of binomial processes on manifolds

Bobrowski-Oliviera: Let M be d-dimensional compact Riemannian

manifold. For 1_{≤ q ≤ d − 1,}

lim

n→∞P(Hq(C(n, r)) ≃ Hq(M)) =

$

1 Λ = log n + q log log n + ω(n),

0 Λ = log n + (q_{− 2) log log n − ω(n)},

where ω(n)_{→ ∞ and Λ = nω}drnd.

Goel-Trinh-Tsunoda: Law of large numbers of Betti numbers for binomial processes on compact Riemannian manifolds.

Trinh: Central limit theorem for Betti numbers on binomial and Poisson point processes.

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 53 / 72

Geometric graph G (

X, r)

Let_{X = {x}1, . . . , xn} ⊂ Rd be a point configuration (collection of points).

Figure:Geometric graph G (X , r) for a point configuration X xy_{∈ Edge[G (X , r)] ⇐⇒ d(x, y) ≤ r (x ̸= y)}

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 54 / 72

Filtration of geometric graphs

Figure:Geometric graph G (X , r): |X | = 100

Geometric graph and Boolean model

Figure:Geometric graph and union of balls (a realization of Boolean model) xy _{∈ Edge[G (X , r)] ⇐⇒ d(x, y) ≤ r ⇐⇒ B}r /2(x)∩ Br /2(y )̸= ∅

Point configuration to simplicial complex and filtration

ˇ Cech complex XC(r ) {xi0, xi1, . . . , xik} ∈ XC(r )⇐⇒ k 8 p=0 B(xip, r )̸= ∅. Rips-Vietoris complex XR(r ) {xi0, xi1, . . . , xik} ∈ XR(r )⇐⇒ B(xip, r )∩ B(xiq, r )̸= ∅ for any p ̸= q.

Figure:Rips-Vietoris complex

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 57 / 72

κ-complex

Function κ (birth time of simplices): Let_F(Rd) be the set of all finite

subsets in_Rd _{equipped with Hausdorff metric.}

1 κ :F(Rd)→ [0, ∞) is continuous.

2 _{κ is shift-invariant, i.e., κ(σ + a) = κ(σ) for every σ}∈ F(Rd) and

a_{∈ R}d_.

3 If τ ⊂ σ then κ(τ) ≤ κ(σ).

4 _{There exists an increasing function ρ : [0,}∞) → [0, ∞) such that

|x − y| ≤ ρ(κ({x, y})) (∀x, y ∈ Rd).

κ-complex and κ-filtration: Fix κ. For _{X ∈ F(R}d_{), we define the} κ-complexover_{X by}

K (_{X , t) := {σ ⊂ X : κ(σ) ≤ t}}

and theκ-filtrationby

K(X ) := {K(X , t), t ≥ 0}. 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 58 / 72

Examples

Examples: (1) Rips-complex κ(_{x1, . . . , xp}) := 1 21≤i<j≤pmax |xi− xj| (2)Cˇech-complex κ({x1, . . . ,xp}) := inf w∈Rd_1≤i≤pmax |xi− w|

Remark that both κ’s are 1-Lipshitz continuous with respect to

Hausdorff metric on _F(Rd).

dH(X , Y ) = max(max

x∈X d(x, Y ), maxy∈Y d(X , y ))

白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 59 / 72

Stability (continuity) of persistence diagrams

Stability Theorem (Hiraoka-S-Trinh (’17+))

Let Xκ(X ) be the κ-filtration of X ∈ F(Rd) and ξq(X ) the q-th persitence diagram for Xκ(X ). If κ : F(Rd)→ [0, ∞] is γ-Lipshitz

continuous with respect to dH, then

dB(ξq(X ), ξq(X′))≤ γdH(X , X′),

where dB is the ℓ∞bottleneck distance onF(∆).

Remark: This type of stability

theorem is first shown for the ˇ

Cech -filtration by

Cohen-Steiner-Edelsbrunner-Harer.

Window and persistence diagram

Let Φ be a stationary point process and Φ_|ΛL be its restriction to ΛL,

where ΛL= [−L/2, L/2)d is a window.

The q-th persistence diagram for Φ_|ΛL is denoted by ξq,Las a point

process on ∆ =_{{(b, d) : 0 ≤ b < d ≤ ∞}.}

Figure:白井朋之Poisson point process on(九州大学IMI) 確率論とパーシステントホモロジーR2 _{with windows of size L = 20, 20}Dec. 23, 2017√_{10, 200}61 / 72

Law of large numbers

Let Φ be a stationary point process and Φ_|ΛL be its restriction to ΛL,

where ΛL= [−L/2, L/2)d is a window.

The q-th persistence diagram for Φ_|ΛL is denoted byξq,L as a point

processon ∆ =_{{(b, d) : 0 ≤ b < d ≤ ∞}.}

Theorem (Hiraoka-S-Trinh (’17+))

Let Φ be a stationary ergodic point process onRd having all finite

moments. Then, for each q_{∈ Z≥0},

1 Ldξq,L

v

→ νq a.s.

where ν白井朋之q(is non-random.九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 62 / 72

Known result

Theorem (Yogeshwaran-Subag-Adler (’15))

Assume that Φ is a stationary ergodic point process having all finite moments. Then, for each r > 0 there exists a constant 9βq(r ) such that

1 Ldβq(X (r ))→ 9βq(r ) a.s. as L_{→ ∞.}

Realizable points

Let ∆ =_{{(b, d) : 0 ≤ b < d ≤ ∞}}

A point (b, d)_{∈ ∆ is a}realizable pointif there exists_{X ∈ F(R}d₎

such that (b, d)∈ ξq(X ).

Example. (b, d) = (5, 10) when q = 1.

Figure:the set∪x∈XBr(x) is drawn for r = 0, 1, 2, 5, 8, 10. A cycle appears

Realizable point and configuration

We denote by Rq(κ) the set of all realizable points in the qth persistent homology of the κ-filtration.

If κ ishomogeneousin the sense that κ(ασ) = ακ(σ) for every

α > 0 and σ_{∈ F(R}d), then Rq(κ) forms aconein ∆.

Example: Both κC and κRare homogeneous and hence Rq(κC) and Rq(κR) are cones for every q≥ 0.

For theCech complexˇ ,

Rq(κC) = ⎧ ⎪ ⎨ ⎪ ⎩ {0} × (0, ∞], if q = 0, ∆int, if q = 1, 2, . . . , d− 1, ∅, if q = d, d + 1, . . . . 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 65 / 72

Support of ν

q

For every compact set Λ_{⊂ R}d, the restriction of Π on Λ can be

considered as a probability measure on

Conf (Λ)≃

∞ > n=0

Λn/∼

The restriction Φ|Λ can be considered as a finite point process.

Theorem (Hiraoka-S-Trinh (’17+))

Let Φ be a stationary ergodic point process on_Rd _{having all finite}

moments. On each Λn_{, the distribution of Φ has a density function. Then,}

for every q_{∈ Z≥0},

suppνq=Rq(κ) (∀q ≥ 1).

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 66 / 72

Examples

Examples

Φ: Poisson, Ginibre, the zeros of random analytic function etc..., ˇ

Cech -complex built over a point process Φ,

suppνq = ∆ (q = 1, 2, . . . , d− 1) 0 50 100 0 50 100 100 50 0 0 50 100 100 50 00 50 100 100 50 00 50 100 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 67 / 72 1 イントロ 2 ランダムグラフとランダム複体 3 ランダム複体過程とフィルトレーション 4 ランダム複体過程，最小全域非輪体，パーシステントホモロジー 5 ランダム点過程とパーシステントホモロジー 6 関連した話題 白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 68 / 72

Maximally persistent cycle

Maximally persistent cycle: a cycle corresponding to (bmax, dmax) s.t. dmax/bmax= max{d/b : (b, d) ∈ ξq}.

Theorem (Bobrowski-Kahle-Skraba (’16))

Let Pn be a Poisson point process on [0, 1]d and consider Rips-Vietoris or ˇ

Cech filtration. For q = 1, 2, . . . , d_{− 1,} dmax bmax ≍ " _{log n} log log n #1/q w .h.p. 白井朋之(九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 69 / 72

Large torsions of spanning acycles

Example: V =_Z31and E =0V₂1and

T =?_{{x, y, z} ∈} "_V 3 # : x + y + z _{∈ {1, 2, 9} mod 31}@ |T | =0312−1 1

= 435 and XT = V* E * T forms a spanning 2-acycle.

The order of the torsion is

|H1(XT)| = 16844675348856829290625

= 5_{× 311 × 683 × 1117 × 11657 × 1948909.}

白井朋之 (九州大学IMI) 確率論とパーシステントホモロジー Dec. 23, 2017 70 / 72

Uniform sampling from spanning acycles

Kalai(’83) showed the following: for fixed ℓ_{≥ 2,}

(Upper bound)

|Hℓ−1(XT)|2≤ (ℓ + 1)(

n−2 ℓ ).

(Lower bound) For sufficiently large n, E|Hℓ−1(XT)|2>Aℓ + 1

2.8 B(n−2

ℓ )

,

where T is sampled uniformly from the set of spanning ℓ-acycles_Sn(ℓ).

Problem

How does the distribution of torsions look like as n_{→ ∞?}

Further directions

多様体学習や機械学習． 種々のデータのパーシステント図の極限定理 (大数の法則，中心極限 定理など) ランダム場のパーシステントホモロジー． 時系列や粒子の時間発展のパーシステントホモロジー論． Linial-Meshulam複体やクリーク複体の臨界点近くでの詳しい解析． 極限パーシステント図の具体的な表示． 大きい捻れ群の分布． 極大パーシステントサイクルの幾何的な性質・極限定理．