Tomoyuki Shirai Institute of Mathematics for Industry, Kyushu University 1 Erdös-Rényi Erdös-Rényi 1959 Erdös-Rényi [4] 2006 Linial-Meshulam [14] 2000

Size: px

Start display at page:

Download "Tomoyuki Shirai Institute of Mathematics for Industry, Kyushu University 1 Erdös-Rényi Erdös-Rényi 1959 Erdös-Rényi [4] 2006 Linial-Meshulam [14] 2000"

あおいぜんじゅう
5 years ago
Views:

1 Tomoyuki Shirai Istitute of Mathematics for Idustry, Kyushu Uiversity Erdös-Réyi Erdös-Réyi 959 Erdös-Réyi [] 6 Liial-Meshulam [] (cf. [, 7,, 8]) Kruskal-Katoa Erdös- Réyi ( ) Liial-Meshulam ( ) [8]. Kruskal G = (V, E) w : E R (G, w) (miimum spaig tree) (G, w) T ( T ) wt(t ) := e T w(e) W (G) := mi T S () (G) wt(t ) S () (G) G RIMS o July 8, 5. No.665, (B)No.6879 ( AIMR)

2 .. Cayley (859) K S () (K ) = (G, w) Kruskal [] w e, e,..., e m (m = E ) {T k } m k= T =, { Tk {e k }, T k {e k } T k = T k, T k {e k } {T k } k k m T k = V T k = T k (k k ) T k. Frieze K = (V, E ) K e E w(e) {w(e)} e E [, ] w : E [, ] (K, w) {w(e)} e E () W := W (K ) Frieze W. (Frieze [6]). ζ(s) = = s Riema E[W ] ζ() = (cf. [])... Jaso ([]) (W ζ()) N(, σ ) σ = 6ζ() ζ() = Frieze

3 . Erdös-Réyi Kruskal Frieze K = (V, E ) {w(e)} e E Kruskal. t = w(e) e e w(e) ( ) E (t) = {e E : w(e) t}, G (t) = (V, E (t)) G = {G (t)} t Erdös-Réyi ( ) G (t) G () G () = K t G (t) t t Erdös-Réyi G(, t) p Erdös-Réyi G(, p) p t (K, w) Kruskal Erdös-Réyi G(, p) G(, p) () {G(, p)} p G = {G (t)} t. ( ) iput : via Čech or Rips-Vietoris etc. iput : = output:

4 5 5 Poisso t t t t t : iput (iput) (iput) iput (Čech Rips-Vietris ) ([8]) ( ). V σ V σ = k + σ k- (k-simplex) k-face dim(σ) = k.. X V (V, X) () {v} X for all v V, () σ X, τ( ) σ = τ X () X d = max σ X dim(σ) (V, X) d V X.. X = {,,,,,,,,, } X facet {,, } ( ).() facet,, X = {,,,,, }{{}}, {{, }}{{} } X X {{ } X () : a graph X k = {σ X : dim(σ) = k} X k-face X (k) = {σ X : dim(σ) k} X k- X }

5 : X V = [] = {,,..., } d d K (d) K K () k =,,..., dim X T X k X k X T := X (k ) T (T = k ). G = (V, E) T E. G (V, T ). G (V, T ). T = V..5. (i) (ii) H (X) Z- β (X) = rak H (X) β (X) Q- H (X, Q).6 ([]). X d- (d )-Q-acyclic β i (X) = (i =,,..., d ). X k- T X (k =,..., d) k simplicial spaig tree 5

6 . T (k ) = X (k ).. Hk (T ) =.. βk (T ) =.. T k = X k β k (X) + β k (X)..6 k G. Kalai [].7 ([8]). X β k (X (k) ) = β k (X (k ) ) = T X k k (k-spaig acycle). Hk (X T ) =.. H k (X T ) <..8. X β k (X (k) ) = β k (X (k ) ) = T -.7 (base).9 ([6]). X k- T X k k-base. Hk (X T ) =.. T σ X k \ T H k (X T {σ} ) =... k : C k (X) C k (X) k- T k-base.7 K ( ) β k (X (k) ) = β k (X (k ) ) = d K ( ) Kalai[]. Cayley. ([]). S (d) ( ) X := K ( ) T S (d) H d (X T ) = ( d ) 6 d

7 ...7 T H d (X T ) < d = T H d (X T ) = S (). Cayley.. d = =, 5 H (T ) = S () = ( ) =, S () 5 = 5 (5 ) = 5 = 6 H (T ) = Z, H (T ) = S () 6 = 66 6 (6 ) = 6 6 = :. (V, X) X = (X(t)) t X = (X(t)) t=,,,... s < t X(s) X(t) X(t+) = t<u X(u) = X(t). T X(t) = X(T ) ( t T ) t t t t t t t : 7

8 . ( (birth time)). X = (X(t)) t T t(σ) = t if { σ X(t) \ X(t ) (X( ) = ), T = {,,,... } σ X(t+) \ X(t) T = [, ) σ (V, X) X = (X(t)) t=,,,... []( ) [8].5 (k- C k (X)). F X k- { } C k (X) := t=c k (X(t)), C k (X(t)) := a σ σ : a σ F σ X(t) k σ F- F[x] C k (X) x (c, c, c,... ) = (, c, c, c,... ) x C k (X(t)) C k (X(t + )) C k (X) F[x]- x {}}{ ι t : C k (X(t)) C k (X) σ (,,...,, σ,,,... ) { Ξ k := σ := ι t(σ) σ, σ X k := } (X(t)) k t Ξ k C k (X) F[x]- C (X) = (,,,,,... ), = (,,,,,... ), = (,,,,,... ), = (,,,,,... ), = (,,,,,... ) rak C (X) = 5.6 ( ). k (x) : C k (X) C k (X) t k (x) σ := k ( ) j x t(σ) t(σj) σ j. j= σ j σ = v... v k σ j = v... v j... v k 8

9 .7. (i) σ j σ x t(σ) t(σ j ) (ii) σ σ x = k (x) k (x) = B k (X) := Im k+ (x) Z k (X) := ker k (x).8. k H k (X) := Z k (X)/B k (X) F[x].9. F M = i M i F[x]- M = p ( (x b i )/(x d i ) ) i= p+q i=p+ (x b i ). b i, d i Z, b i < d i.9 H k (X) H k (X) = p ( (x b i )/(x d i ) ) i= p+q i=p+ (x b i ) b i, d i i k i = p +,..., p + q b i }{{} X = iput p {(b i, d i )} i= p+q i=p+ {(b i, )} } {{ } output (.) PHAT(Persistet Homology Algorithm Toolbox [9] (.) (b i, d i ) l i := d i b i i p + i p + q l i = L k = p i= l i k {(b i, d i )} p i= [7, ]. ([8]). X d {,,..., dim X}. X = {X(t)} t [, ] X L k k L d = 9 β d (t)dt. (.)

10 β i (t) X(t) i Betti β d (X (d) ) = β d (X (d ) ) = L d = mi wt(t ) max wt(x d \ S). (.) T S (d) S S (d ) S (k) k S X (k) wt(s) = σ S t(σ).. (.) mi T S (d) wt(t ) + mi S S (d ) wt(s) wt(x d ) (d ) d d =.. d-liial-meshulam V = {,,..., } := K ( ) ( ) (.) V facet ( ) d V d- σ ( ) d t(σ) [, ] X (d) (t) = K (d ) {σ ( ) d : t(σ) t} d X (d) := {X (d) (t), t } d Liial-Meshulam([]) t X (d) (t) X (d) d-liial-meshulam ( LM (d) -process) d = X () () = K () = V ( ) X () Erdös-Réyi 5: Erdös-Réyi graph process (d = ) d = X () () = K () ( ) -face LM (d) -process ( d+) d-face ( ) X () () = K () X (d) () = K (d ) X (d) () = K (d) 6: -Liial-Meshulam process

11 .. LM (d) -process t X (d) (t) k Betti β k (t) (k =,,..., d ) (d ) Betti β d (t) ( ) β d () =, β d () = d.. LM (d) -process (.) q = l i, i =,,..., p ( d i ) L k = p i= l i p dim(σ) d t(σ) = (.) (.) L d = mi T S (d) wt(t ). (.) LM (d) -process (miimum spaig acycle) Frieze Liial-Meshulam. Frieze.. d N L d LM (d) -process X d (d ) E[L d ] = E[ mi T S (d) wt(t )] = O( d ) (.).. lim (d ) E[L d ] [8] E[L d ] (.) (.) (i). LM (d) -process X (d) = {X (d) (t)} (d )-face η t(η) = (.) T (d ) L d = wt(t ) L d = wt(t ) T i= u i u u u ( d) {t(σ), σ ( ) d } T = ( ) d T E[L d ] E[u i ] = i= T i= ( d+ i ) = O( d ). +

12 (ii) E[L d ] (.) β d (t) β d (t) (d )- ( d) ( ) E[L d ] = β d (t)dt dt = O( d ) d Betti Kruskal-Katoa. Kruskal-Katoa [] = {,,..., }, F [] F F := {E [] : F F s.t. E F ad F \ E = } [] k ( ) [] k = {F [] : F = k} F ( ) [] k F = m F F F F km Kruskal-Katoa k-. (k- ). m N k N a k > a k > > a s ( ) ( ) ( ) ak ak as m = (.) k k s m k-.. k = ( ) ( ) ( ) ( ) ( ) ( ) = + +, =, 5 = +, ( ) ( ) ( ) ( ) ( ) ( ) 6 = + +, 7 = +, 8 = + ( ) ( ) ( ) ( ) 5 9 = + +, =,... ( ) + ( ),.5 (Kruskal-Katoa). F ( ) [] k F = m m k- (.) F F ( ) ak k + ( ) ak k + + ( ) as s (.)

13 .6.. (k = ).5, m = 5, m = 6, m =, F 8, m = 5 9, m = 6, 7, m = 8, 9,..., F facet X F X - m - m = - 6 F Lovàsz x k ( ) x k = x(x ) (x k+) k k! x k ( ( x k) x k) = m x k.7 (Kruskal-Katoa Lovàsz ). F ( ) ( [] k F = m = x ) k (x k). ( ) x F k.5.7 [5] Kruskal-Katoa.8 ([5]). Y d Y d = ( x d+) (x d + ) d : C d (Y ) C d (Y ) ( ) x rak d d Y rak d d + Y d. Betti Y d (d ) K (d )

14 Y d- Y (d )-Betti d : C d (Y ) C d (Y ) d : C d (Y {σ}) C d (Y {σ}) rak R d (Y ) = {σ Y d : β d (Y {σ}) = β d (Y ) } β d (Y ) d+ R d(y ).. [8] ( )LM (d) -process X (d) = {X (d) (t)} Y = {Y t } (.).9 E[L d ] = E[ β d (Y t )]dt d + E R d (Y t ) dt LM (d) -process.. LM (d) -process ( ) E R d (Y t ) dt 8 d. [8].9.. E[L d ] = E[ β d (Y t )]dt d + E R d (Y t ) dt d + ( ) 8 d = O( d ).. Liial-Meshulam Frieze [8] Liial-Meshulam.

15 [] C. Cooper, A. Frieze, N. Ice, S. Jaso ad J. Specer. O the legth of a radom miimum spaig tree. arxiv:8.57v. [] A. Duval, C. J. Klivas ad J. L. Marti. Simplicial matrix-tree theorems. Tras. Amer. Math. Soc. 6 (9), [] H. Edelsbruer, D. Letscher, ad A. Zomorodia. Topological Persistece ad Simplificatio. Discrete Comput. Geom. 8 (), 5 5. [] P. Erdös ad A. Réyi. O radom graphs I. Publ. Math. Debrece 6 (959), [5] P. Frakl. A ew short proof for the Kruskal-Katoa theorem. Discrete Math. 8 (98), 7 9. [6] A. M. Frieze. O the value of a radom miimum spaig tree problem. Discrete Applied Math. (985), [7] R. Ghrist. Barcodes: the persistet topology of data. Bull. Amer. Math. Soc. 5 (8), [8] Y. Hiraoka ad T. Shirai. Miimum spaig acycle ad lifetime of persistet homology i the Liial-Meashulam process. [9] Y. Hiraoka ad T. Shirai. (RIMS 95) [] [] G. Kalai. Eumeratio of Q-acyclic simplicial complexes. Israel J. Math. 5 (98), 7 5. [] S. Jaso. The Miimal spaig tree i a complete graph ad a fuctioal limit theorem for trees i a radom graph. Radom Struct. Alg. 7 (995), [] J. B. Kruskal. O the shortest spaig subtree of a graph ad the travelig salesma problem. Proc. Amer. Math. Soc. 7 (956), 8 5. [] N. Liial ad R. Meshulam. Homological coectivity of radom -complexes. Combiatorica 6 (6), [5] N. Liial, I. Newma, Y. Peled ad Y. Rabiovich. Extremal problems o shadows ad hypercuts i simplicial complexes. arxiv:8.6v. 5

16 [6] R. Lyos. Radom complexes ad l -Betti umbers. J. Topology Aal. (9), [7] R. Meshulam ad N. Wallach. Homological coectivity of radom k-dimesioal complexes. Radom Struct. Alg. (9), 8 7. [8] A. Zomorodia ad G. Carlsso. Computig persistet homology. Discrete Comput. Geom. (5), 9-7. [9] PHAT (Persistet Homology Algorithm Toolbox). 6

数理解析研究所講究録第1986巻

数理解析研究所講究録第1986巻 1986 2016 55-70 55 Tomoyuki Shirai Institute of Mathematics for Industry, Kyushu Un\ iversity 1 Erd\"os-R\ enyi Erdos-R\ enyi 1959 Erd\"os-R\ enyi [4] 2006 Linial-Meshulam [14] 2000 (cf. [3, 7, 10, 18