Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/dubna/2013/notes/chelkak-lectures.pdf Äàòà èçìåíåíèÿ: Sat Aug 3 13:51:00 2013 Äàòà èíäåêñèðîâàíèÿ: Sat Mar 1 20:55:42 2014 Êîäèðîâêà: IBM-866 Ïîèñêîâûå ñëîâà: trees

: , LERW SAW
,

1. : . 1.1. : . Z2 (0, 0) Z2 í . v , : v + , v - , v , v , , . í Z2 : , , , . , , í "" 1 , 4 (, , í : , : ). , v0 , v1 , v2 , . . .. vi í , v0 = 0 P(vn+1 = vn ) = 1 , = +, -, , . vn 4 n, . , , , [ . 2 ] n. , . , , * . 1.2. . R2 Z2 , R2 . . Z2 , , . , , ( ) : . : , ( ), , "", . : , . ( int ) : u, v , w, ..., "" ( , ) : a, b, c, ....
1


2

1.3. . , , (v , a). , v int , a. , 2 : í . . 1. (v , a) (1) (v , a) =
:v -->a

1 4

| |

, v a, | | , . . : v : v + , v - , v , v . (1) . [a, b] (v , [a, b]). [a, b] a, b . : a b (, ). , (v , [a, b]) (2) (v , [a, b]) =
c[a,b]

(v , c)

, (v , ) . , : 1. ( ). . d í ( ). , , d , . , : 41d . d q := 1 - 41d , q < 1. k d q k . q k 0, k , . 1.4. : . a ( , ) (v , a) ( ). (v , a) v int . (v , a) : , . b = a, a í : (b, a) = 0, b = a. a, (a, a) = 1.


3

(1) , v a : 1 (3) (v , a) = (v , a) 4
=+,-, ,

a , , H : (4) H (§) := (§, a) , Omega (§, a) : . 1. H , = int Z2 , , v int : 1 (5) H (v ) = H (v + ) + H (v - ) + H (v ) + H (v ) 4 1.5. . (§, a)? , a, 1. , (5). , (§, a) N , N í . í H (v ), v int ; H (a), a . : () , ( ). , x + y = 2; 2x - 3y = 3 x + y = 0; 2x - 3y = 0. ( í ): 1. N N , . , , í . . 2. (5), v int ; H (a) = 0, a . . : H . H v int ( -H ). (5) v , H v . , H (v ) = H (v ) = max H . H , , H = const, í , H 0. 1. C . . 1 2.


4

1 . 1.6. : . , - 1 . 1 , 1 .. A priori , - . , í . Z2 , > 0 Z2 . : . , , , . ( , í , ) H Z2 . , , (6) 1 + - H (v ) + H (v ) + H (v ) + H (v ) - H (v ) 4 , . . H (v + ) = H (x + , y ) = H (x, y ) + Hx (x, y ) +

2 H (x, y ) + . . . 2 xx . Hx , Hxx í x . H (v ) (6), , (7) 2 1 2 + - H (v ) + H (v ) + H (v ) + H (v ) - H (v ) = (Hxx + Hyy ) + . . . = H + . . . 4 4 4 3 . (8) 2. H () , ( ) : H := Hxx + Hyy = 0 (8) , H Z2 , H , , Hxx + Hyy = 0. 3 , 2 , . , 1 + - H (v ) + H (v ) + H (v ) + H (v ) - 4H (v ) 2 . (9) H =


5

2. : . 2.1. . H : [a, b] H (v ) , í . , [a, b] v . H : a b H , H = 0. , H , H , , . , . , 3. D a, b D . (z , [a, b]), [a, b] [a, b], b - z -1 ï 1 b-z - = ( - ) -1 a-z a-z ï 2 - í - z b , í za - - - - z -1 a z -1 b. ï ï (10) (z , [a, b]) = 1 2 arg . . , arg z (. 1). 2.2. : . , í , : Hxx + Hyy = 0 , . , : (x, y ) (x + a, y + b) (x, y ) (k x, k y ), k R. C z , z = x + iy , , z z + a, a C k : z k z , k R. , , k R k C. , k |k | arg k . , 1. A priori, , , , , . , , f (x, y ) = x2 + y 2 . , , (x, y ) (0, 0). , f í , , ( ).


6

- , ? í . 2.3. . f : R R . x. í , Hxx = 0. í : f (x) = ax + b, a, b R. ( ), í . : . : H (x, y ) í í , : C C. z , z = x + iy , w, w = u + iv . (z ) = u(z ) + iv (z ), u, v R. u, v í . . , , , C R. : , í . 2.4. Crash course . 2.4.1. . 3. : C, C z0 , . , (11) (z0 ) := lim
z z
0

(z ) - (z0 ) z - z0

: (, ). í z0 , . , z0 , : z z0 z0 z x0 , . z z0 , z = z0 + , R. (11) (12) lim (x + , y ) - (x, y ) = ux (z0 ) + ivx (z0 )

0


7

z z0 , z = z0 + i, R. (11) (13) lim uy (z0 ) + ivy (z0 ) (x, y + ) - (x, y ) = = -iuy (z0 ) + vy (z0 ) i i

0

(12) (13) , , . 4. : C z0 , = u + iv , u, v , (x, y ), z0 : (14) ux = vy , vx = -uy

(14) -. , í - u, v , = u + iv . 2. (u v ) . . , -, : uxx = vyx vxy = -uyy . v ( , ), : vyx = vxy , uxx = -uyy , . v . , í , z (, z ) , exp(z ) . , í , , x z . 2.4.2. . , , . 2. : C í , H (§) í , H í . 2, . , : | (z0 )| arg (z0 ) ( (z0 ) = 0). . , , . : u v , := u + iv í . 2 .


8

2.4.3. . ~ 4. : , . í . , z0 (z0 ). : ~ 5. : , í , z (z ) = 0. , (z ) = 0 : z exp z . 2.5. . , (z , [ab]) : (z , [ab]) = [a,b] (z ), [a,b] í [a, b], (z ) = 1, z [a, b] (z ) = 0, z [a, b]. / ~ 3. : ~ . z [a-, b] , : (15) (z , [ab]) = ((z ), [(a), (b)]) ~ : , . . , - . , : H , . í H1 , H2 í , H1 - H2 í . , - ( í H2 - H1 ) , ( ). í . , (15) 2. 2.6. - . - , az + b (16) z , ad - bc = 1 cz + d , . ( , ).


9

5. - : 1. k C: z k z 2. z z + c, c C 3. ( ): z z -1 . 2 . , , , - + : 1, 2, 3. D = {|z | < 1} z0 . - , z0 : (17) :z z - z0 1 - z0 z ï

z - z0 z - z0 = |z | = 1 ï 1 - z0 z ï z - z0 ïï

(18)

|z | = 1

- , D (0, [a, b]) = b2a . , 3 , D (z0 , [(a), (b)]) , D (z0 , [c, d]) c, d D.

2.7. . : , , . , í . , : , ( ). , . , , , . 4. C z0 : D , (z0 ) = 0, z0 . ( , , ). : , , (z0 ) R (z0 ) > 0. , (a) = 1, a í . , (z0 , [a, b]) C , 2.6. 2.8. .


10

2.8.1. . : p+ ( v v + ), p- ( v v - ), p í ( v v ) p ( v v )í . , . , p , = +, -, , . , (v , [a, b]) [a, b], , p ( )? : , . , , (3): (19) (v , [a, b]) = p+ (v + , [a, b]) + p- (v - , [a, b]) + p (v , [a, b]) + p (v , [a, b])

, (v , [a, b]), p , (19) [a, b]. 2.8.2. . , : , . , , . , : , . , , . (§, [a, b]) , . , . , (§, [a, b]) . , ( ) . (., , 4 ), , : , í ( ). , , , , , ... : , , . , , ( ). 3. : . 3.1. . , , ( ). , : (v , a) , .


11

(20)

(v , a) =
:v ->a

1 4

| |

=

1 4

(v , a)
:v ->a

t, í t + 1. , (20), : t t + 1: "". 3.2. . Z : , (0, 0). , , , a . RW (0, a) (random walk) 0 a. , , a, , 0 a, 4-| | P[RW (0, a) = ] = (0, a)

(21)

, , - 0 a: (0, a) = :0->a 4-| | . , , a: , v , a. v v , = +, -, , , -, v , -, (: a ). , , (§, a) . N (v , u) u , v : (. 3). v = u (22) N (v , u) = 1 4 N (v , u)
v ,=+,-, ,

3.3. . , N Z2 R = N . R N : , . , LERW (loop erased random walk). LERW , . :


12

. . , . . , , 5 ( ): N R 4 . , , > 0 N = N (, ) , (23) n > N : P R
5 4

-

nR

5 4

+

>1-

, , , LERW ( N N ). , , , LERW , . : , . LERW RW, . : í , . : . ( ), LERW . . , . LE RW (0, a) í , a . (21). 3.4. LERW. , RW (0, a) = RW (a, 0) : (21), 0 a. , : 6. LE RW (0, a) = LE RW (a, 0) , : , . , : , , , . , 3. 3.4.1. : . G , , - G. G T (G). . , - .


13

G (Wilson's algorithm). G. "", Tk G ( ): § T0 í () r , , ; § Tk+1 Tk rk+1 Tk Tk (!) LERW, G, rk+1 , Tk . 3 , : , , , , |T (G)|-1 ( ) . 6 ( , 3), , LERW , , . , . 3.5. LERW. , , , , , . í , , \ . a : aint aout . aint , aout . p ( a), , , a 0, a , a í aint . , a í , . p , p p , a , a , a . \ {a} , aint . 2. (24) (0, a) =
=,,



\{a}

(0, a ) §
:a ->aint

1 4

| |

½

1 4

, 0 v .


14

3. =, , (25) p := P[LE RW (a, 0) a ] =
\{a}

(0, a ) \{a} (0, a )

7. v (26) (v , a) = (0, a) p


\{a} (v , a ) \{a} (0, a )

2 3. ,a) , (v,a) , (0 , a, v = 0. ( 5 2). ( ). , . : ( ) LERW. [1].

4. : . 2010 , [2]. , : , ( ) , . 4.1. SAW: . (self-avoiding walk) H, , . , í . n: . , , ( o). cn í n, o. Paul Flory . , , 2 , n, R = n3/4 . 2 ( ). 3 Flory R = n3/5 . , , 3 : 0.59... , , , : .


15

4.2. : . cn : cn 2n/2 : , n n , n 2 2 . . : cn 43n-1 , . , cn . 8. n, m : (27) () . , n + m n m. í , . 4. (27), (28) ²crit := lim n cn
n

c

n+m

cn c

m

1. (29) cn C ²n it n cr
-1

,n

²crit , - 1 í , ( , - 1 11 ) - 1 = 32 . , SAW, . , , n : c2 n C1 ²2nit n -1 cr C n1- c2 C2 ²2nit n2 -2 n cr


(30)

P[ SAW ] =

1 4.3. . n cn ² . ² , , . ²crit í , : 1 1 x := ² , n cn xn xcrit = ²crit . ,

n

(31)
n

c

n

1 ²

n

=
SAW

²

-n

.

, . :


16

(32)

P { S AW } =

²


-| |

²

-| |

. 4.4. ²crit . . , ²crit = ²0 := 2 + 2 , F , , . , ( ). . , RW (§, a) . LERW (§ (0,a)) , . ,a F . 6. C í , || = 1. , a , z , (33)
o F (z ) := :a->z , , SAW

²

-| |



-

, , , : , ï = -1 . , , , ²-3 -3 . 4.5. . - v , . : . () , (), (). v , ( , v ). , , z1 . z2 , z3 í , . a := exp( 23 i ). , F (z ) , . , 9. ² , v z1 , z2 , z3 : (34) F (z1 ) + F (z2 ) + 2 F (z3 ) = 0

. , , . : (35) -(F (z1 ) + F (z2 ) + 2 F (z3 )) = 0


17

, ( , , ). 9 í . , , . . í . , a, z1 , z2 , z3 . : § zi , i = 1, 2, 3. : v , , zj . , . , , z1 , z2 , z3 . § , 3 z1 , z2 , z3 : , SAW v : . , , , v . (34): . , (34). , . , 1 , 2 , 3 í . | | í ( ). , , ï (36) (1 ) + (2 ) + (3 ) = .1 - . 1 ²| | 1 + + 2 ² ²
, 1 + ² + 2 ² : , ². , 1 , 2 . : |1 | = |2 | = | |. T í a ( zi ), 1 2 . ( ) ï

ï (1 ) + (2 ) = T ²| | 4 + 2 4 ï , 4 + 2 4 . ï (37) , Re( 4 ) = 0 , , = exp(i), = 24 + 4n . , n = -1, 5 = - 24 . (36) (37) 1ï 2 7 2 ( + )) = 1 + cos ï = 1 - cos = 0 ² ² 8 ² 8 1 , ²0 = 2 cos = 2 + 2 8 . í , ²0 . (38) Re(1 +


18

4.6. : ²crit ²0 . , ² = ²0 . , . ST , T - 1 . ST 3T + 1 (39) V (ST ) = {z V (H : 0 Re z )} 2 ST ,L : , . (40) V (ST ,L ) = {z V (ST ) : | 3 Im z - Re z | 3L} , a ( ) ST ,L . ST ,L , ST ,L , . ï (9) : í , í : (35). F (z ) ST ,L . ï . , , , , (41)
:o->

²

-| | 0

, , , (42)
:o->

²

-| | 0

Re( 2 )

, : ï (43)
:o-> ï

²

-| | 0

2 Re(ï )

, , : , (44)
:a->

²

-| | 0

Re(-3 )

, : (45)
:o->

²

-| | 0

+
:o->, ï

²

-| | 0

Re( 2 ) +
:a->

²

-| | 0

Re(-3 ) = 1


19

5. , . .

²

-| | 0

1.

4.7. . , 1 ²0 . , ² > ²0 . , ²crit = ²0 . 4.
[1] Gregory F. Lawler, Oded Schramm, Wendelin Werner Conformal invariance of planar loop-erased random walks and uniform spanning trees [2] Hugo Duminil-Copin and Stanislav Smirnov. The connective constant of the honeycomb lattice equals 2 + 2 Preprint, arXiv:1007.0575v 2, 2010. [3] Wilson, D. B. 1996. Generating random spanning trees more quickly than the cover time. [4] R.Lyons, Y. Peres Probability on Trees and Networks