Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/free-books/dubna/raigor-4.pdf Äàòà èçìåíåíèÿ: Tue Sep 30 19:37:54 2014 Äàòà èíäåêñèðîâàíèÿ: Sun Apr 10 07:08:42 2016 Êîäèðîâêà: IBM-866 Ïîèñêîâûå ñëîâà: ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï ð ï

ë ¨ ,

. .








. .

.



. . . íí .: , . ISBN --

. íí

. , . , ë ¨ ë ¨ , . .



.

ISBN

--

-

-

é . ., é , .

.



. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1. . . . . . . . . . . . . . . . . . . . . . . 1.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. . . . . . . . . . 1.5. . . . . . . . 1.6. 1.7. . . . . . . . . . . . . 1.8. . . . . . . . . . . . . . . . . . . . . . . . 1.9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10. . . . . . . . . . . . . . . . . . . . . 1.11. . . . . . . . . . . . . . . . . 1.12. 1.13. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.14. . . . . . . . . . . . . . . . . . . . . . . . . 1.15. . . . . . . . . . . . . . . . . . . . . . . . . . . íí . . . . . . . . . . . . . 2.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. íí . . . . . . . . . . . . . 2.3. . . . . . . . . . . 2.4. . . . . . . . . . . . . . . . 2.4.1. . 2.4.2. ............... 2.4.3. ............... 2.4.4. ............... 2.5. . . . . . . . . . . . . . . . . . . . 2.5.1. 2.5.2. ............... 2.5.3. ..................... 2.5.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .




2.6. . . . . . . . . . . . . . 2.6.1. , . . . . . 2.6.2. . . . . . 2.6.3. : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.4. : ................ 2.6.5. 2.6.6. : . . . . . . 2.6.7. : . . 2.6.8. : . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.9. : 2.6.10. .................. 2.6.11. Yk Xk , ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.12. u ................. 2.7. 2.8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9. . . . . . . . . . . . . . . . 2.10. . . . . . . . . . . . . . . . . . . . . . 2.10.1. . . . . . . . . . . . . 2.10.2. . . . . . . . . . . . . . . . . 2.10.3. . . . . . . . . . . . . . . . . . . . . . . . 2.10.4. . . . . . . . 2.11. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11.1. . . . . . . . . . . . . . . . 2.11.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11.3. . . . . . . . . . . . . . . 2.11.4. . . . . . . . . . . . 2.11.5. . . . . . . . . . . . . . íí . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1. . . . . . . . . . . . . . . . . 3.2. . . . . . . . . . . . . 3.3. . . . . . . . 3.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1. . . . . . . .......... .......... .......... .......... .......... ..........




3.4.2. . 3.4.3. . . . . . 3.4.4. . 3.4.5. . . . . . . . . . . . . . 3.4.6. ë¨ 3.5. . . 3.6. . . 3.7. . . . . . . . . . . . . . . . . . . . . 3.7.1. . . . . . . . . . . . . . . . . . . . . . . . 3.7.2. . . . . . . . . . . . . . . . . . 3.7.3. ................. ................. 3.7.4. 3.8. . . . . . . . . 3.9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - . . . . . 4.1. íí 4.2. íí . . 4.2.1. 4.2.2. , 4.2.3. . . . 4.2.4. 4.3. . . . . . . . . ... ... ... .. ... ... ...... ...... ...... ...... LCD- ...... k=1 . . ...... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .




íí . , . , , - . , ë ¨ ë ¨ , . , íí íí . . , . , , . , , , . . , . , , . , , , . , , . íí , , , . , , , . , íí . -




. , , , : , , ë¨ . ë¨, . , , . . , , , , , , ( ) . , , , . , - , - . , , , , [ í ]. . - , - , , .


.
. , , . [ í ].

. .
íí , . , : , , , , . , , . , . , , . , 6 . . 1 , ..., n . , , . , n . , , () i1 , ..., ik . , ë , ¨ , ë ¨, ë ¨, ë ¨. , . , 6 , k .
n 3 1 1


. .

. . , = {1 , ..., n } . , . . , íí , | | = 2n . , P ( ëprobability¨ (.), ëprobabilit‡¨ (.) . .). , e 0, , ...,
1 n | A| n-1 , 1 : P ( A) = . n n

(, , P ) () . , . A, B , A B íí , , , , A, B. , A B íí , , A B. , A A: A = \ A. : ) A P ( A) [0, 1]. ) P () = 1, P () = 0. ) A, B , P ( A B) = P ( A) + P ( B) - P ( A B). , A B = , P ( A B) = P ( A) + P ( B). ) A P ( A) = 1 - P ( A).

. .
, ; . , . , , . . ë¨ ë¨ ? íí ë¨? , . . , p [0, 1] íí . , íí q = 1 - p : .


.

ë¨ . , , ; , , . ë¨ n . . n. , , . , ( x1 , ..., xn ) x1 , ..., xn ? , x1 , ..., xn . , = ( x1, ..., xn ), P ( ) = p
n i =1

x

i

q

n-

n i =1

x

i

.

. : . íí íí , , , 2n . , íí . , ë n k k ¨ Cn íí , k . n 22 . , P íí , [0, 1]. , A , A : P ( A ) = P (). , ,
k , Cn p k q n-k . . , (, , P ) íí . , . n = {1, ..., n}. , i , i - ; . U n ( ). V W . : , U V W U V ? A . A


. .

, ë¨ U , V , W : ( x1 , x2 , ..., xn ), ( y1 , y2 , ..., yn ), (z1 , z2 , ..., zn ). A , , i i xi = 1, yi = 1, zi = 0 xi = 0, yi = 0, zi = 1: , i - n U V , W , , A U V W ; W U V . . 1, 1, 0 , , p 2 q ; 0, 0, 1 q 2 p . , , ë¨ , , , 1 - ( p 2 q + q 2 p ) = 1 - pq ( p + q ) = 1 - pq . , P ( A ) = (1 - p q ) n . , . íí .

. .
. ( , ) n1 , n2 , ..., nk , ... i ni , i . , , pi [0, 1] ( ). .

. .
. , íí .


.

. , , íí , : ) A, B A B ; ) A, B A B ; ) A A = \ A ; ) . . , ? , ë¨ ( ), ë ¨ ( ) ë¨ ( ). , , ë - ¨, . . íí , ë¨ = . , , íí , . , , P íí [0, 1] íí . . , (, , P ) íí . , = {1 , ..., n } P (1 ) = p1 , ..., P (n ) = pn , A , P ( A) = pi , , , p1 + ... + pn = P () = 1. .
i A

. .
(, , P ). , . , B = {i1 , ..., ik } . , , . : , , A = { j1 , ..., jl } ? . A , , B , A , . , , A íí , 6 , , , A = ; 6 3
2 1 1


. .

2, 4, 6 ( , B) . , 3 . . , , B. , A P ( A| B), P ( A| B ) =
| A B| . , | B| | A B |/ | | | A B| P ( A B) = = . P ( B) | B| | B |/ | | 1

, P ( B) = 0, . . , - , P ( B) = 0. . , P ( A| B) P ( B) = P ( A B), P ( B) = 0, . , , : B1 , ..., Bk ( = B1 ... Bk , , ), P ( A ) = P ( A | B 1 ) P ( B 1 ) + ... + P ( A | B k ) P ( B k ). , , , : i {1, ..., k } P ( B i | A) =
k

P ( A| B) =

P ( A B) , P ( B)

P ( A| Bi ) P ( Bi ) P ( A| B j ) P ( B j )

.

j =1

ë ¨, , [ ]. íí . , A B ? , , P ( A| B) = P ( A) P ( B| A) = P ( B).


.

P ( A B) = P ( A) P ( B), P ( A) = 0 P ( B) = 0. . , , , . , , : , . A1 , ..., An , , k n i1 < i2 < ... < ik P ( A i 1 A i 2 ... A i k ) = P ( A i 1 ) § P ( A i 2 ) § ... § P ( A i k ). , . .

. .
. , ë ¨ . , , ë ¨ . , . íí (, , P ). . . () , () , íí . : { An }=1 . n , íí , , , - ( ë-¨), ë¨ . , -


. .

, . . , íí . . , , . -. . . . = [0, 1]2 , , , íí () . - . ( ); ë¨ . , , ë¨ ë¨ : , . . , , ë¨ , , , . : ? ë¨ . , , . ( ) . : : . . : , . íí . ? , . , : , ( )
. , ; , .


.

. , , ( x , y ) [0, 1]2 , x íí , y íí . , | x - y |
7 1 . 4

. 16 , - , ë¨ ( , , ), , . , , 16 . ë ¨, .
7

. .
(, , P ). íí , : . , ë¨, . . (-, x ] -: { : () x} ( { x } ). : F ( x ) = P ( x ). , . , , , , : { y1 , ..., yk }. , pi = P ( = yi ), i = 1, ..., k ; p1 + ... + pk = 1. . , . , , . . p1 , ..., pk , , íí p : , , -


. .


(ë¨ , ,
x

p (t ) d t)
-

. F ( x ) =
-

p (t ) dt . ,

, . , . . . { y1 , ..., yk } = {0, 1, ..., n}. x P ( = x ) = Cn p x (1 - p )n- x , x {0, 1, ..., n}. Binom (n, p ) n p . n = 1 , íí . , , : , n p . . . {0, 1, 2, ...}. , , - . P ( = k ) = =
k e- , > 0. , e = k!
k =0

k ( k!

), , p1 + p2 + ... ... = 1 . Poisson (). ëPoisson¨ íí () . . . t [a, b] p (t ) = 0 . p (t ) = b-a R(a, b). : , , [a, b] , . . . . . . p (t ) = N (², 2 ).
1 e 2
-
(t-²)2 22

1

,

²

, > 0.


.

. , , { x } { y }. , , P ( x, y ) = P ({ x } { y }) = P ( x ) P ( y) x, y . , ( ). , . , .

. .
. , . . íí . íí . M E . . { y1 , ..., yn },
n

M =
i =1

yi P ( = yi ).

, , . íí . -: M =


( ) P ( ).

. , , . ,


M =
-

t p (t ) d t .

-, , .


. .

íí . , c1 , c2 1 , 2 M (c1 1 + c2 2 ) = c1 M 1 + c2 M 2 . ( ), . . -, Binom (n, p ). M .
n

M =
k =0 n

k k Cn p k q

n- k

n

=
k =1

k

n! pk q k!(n - k)!

n- k

= = np ( p + q )
n -1

= np
k =1

(n - 1)! p (k - 1)!((n - 1) - (k - 1))!

k -1 (n-1)-(k -1)

q

= np .

, , . . , = 1 + ... + n , 1 , ..., n íí () . , . M = M 1 + ... + M n , M i = 1 § p + 0 § q = p i , , , M = np . ! -, , . . , m : U1 , ... ..., Um . - . = (U1 , ..., Um ), Ui , U j , Uk {U1 , ..., Um }, Ui U j Uk Ui U j . M , , . , , P ( = 1) , . ë ¨. , N , 3 . , N = 3Cm ( , ë¨ Uk ). , T1 , ..., TN , ë¨ i , , , Ti . , i íí . , . , M i = (1 - pq )n . , = 1 + ... + N . M = N (1 - pq )n. ! (. [ , ]).


.

: , , M = M M . , . , , Poisson (), M = ( !). , . , . . D = M ( - M )2 = M 2 - ( M )2 . . , . , D (c) = c2 D , . , D (1 + 2 ) = D 1 + D 2 , 1 , 2 . , Binom (n, p ), D = D 1 + ... + D n = n p q . , D = M = . , M = ² D = 2 , N (², 2 ).

k - M k . k - k - M k = M ( - 1) § ... § ( - k + 1). f , Poisson (), M k = k . f . , p (t ) = , . . , , . , , - . . , ( ) . .
1 1 § 1 + t2


. .

. .
. . {0, 1, ... ..., n}.
n

P ( = k ) =
r =k

(-1)

k +r

Mr f k!(r - k)!

.

: , . . ? : ( ) , ; , ( ) . íí , , (. [ , ]). , , , ë ¨. , : (-1)
2k

Mk f k!

=

1 M ( - 1)...( - k + 1) = k!

=

1 k!

n i =k

i (i - 1)...(i - k + 1) P ( = i ).

, : { y1 , ..., yk }, f íí ,
k

M f ( ) =
i =1

f ( yi ) P ( = yi ).

:
1 k!
n i =k

i (i - 1)...(i - k + 1) P ( = i ) = =
(k + 1)! 1 k ! P ( = k ) + P ( = k + 1) + ... . 1! k!

? ( ) . -


.

, P ( = k + 1). . k!1! P ( = k ) ( ), . , , . . {0, 1, ...}. , , m
r

(k + 1)!

lim

( M r ) r f r!


m

= 0.
Mr f k!(r - k)!

P ( = k ) =
r =k

(-1)

k +r

.

. . , , , . , . . , () , . , An = (n , n , Pn ), n = 1, 2, ..., íí . , , . . = = ( x1 , ..., xni ) ni Pni () = pi
ni k =1

x

k

q

ni - i

ni k =1

x

k

.
n
i

²ni , . ., , ²ni () = xk .
k =1

: An n : n {0, 1, ...}. . n


. .

{0, 1, ...}. , , r M r n r f n , > 0 íí . Pn (n = k )
k e- . k!

ë¨ íí (. ). , n . . . , > 0 r , r = 1, 2, ... : ë¨ , ë ¨. . . , , 1 , 2 , , i (n) 0 n i r , n (1 + 1 ( n ))
r

Mr f

n

(1 + 2 ( n )) r .

, M r n r . , , . ? f , M r n = 1 - f
er r . n

r M r n r ; 1 , f r Mr f
n

(1 + 1 ( n )) r ,

! , . n, k


Pn (n = k ) =
r =k

(-1)

k +r

Mr f

n

k!(r - k)!

.

,

, , .


.

, ,


Pn (n = k )
r =k

(-1)

k +r

(1 + 1 (n))r = (1 + 1 ( n )) k!(r - k)!

i =0

(-1)i k !i !

k+i

=

= (1 + 1 ( n )) , Pn (n = k ) , Pn (n = k )

k k!

i =0

(-)i k e- = (1 + 1 ( n )) . i! k!

(1 + 2 ( n ))

k e- . k!

k e- . k!

, . . pi ni > 0 i . Pni (²ni = k )
k e- . k!

, . , , . , . .

.

.

. , . , . . , . íí .


. .

. Pa
²n - n p n pq

b



1 2

b

e
a

-

x2 2

dx.

a b. , , . , [ í ]. .

. .
. . . , . . > 0 P (| - M | )
D . 2

, . . . ë¨: D =
y

( y - M )2 P ( = y ) =
)2
2

=
y : ( y -M

( y - M )2 P ( = y ) +

y : ( y -M 2
2

)2

<

2

( y - M )2 P ( = y ) ).

y : ( y - M )2

P ( = y ) = 2 P (| - M |

, . .


.

. , > 0 P ( )
M .

.

. .
íí , , = 1 + ... + n , i = 1
1 1 i = -1 2

(1 , ..., n ). , , 2 , , , -1. . a > 0 P ( a) e
-
a2 2n

.

, . , M = 0 P ( a ) = P ( - M a - M ) P (| - M | = P (| - M | a - M ) = a)

n D 1 D n = = 2. a2 a2 a

a = n2/3 (), P ( a) n-1/3 . 1/3 P ( a) e-n /2 . n , n-1/3 , . n . , n. . > 0. P ( a ) = P ( a) = P e


e

a

e

- a

M e .

. , 1 , ..., n , Me


= ( Me

1

) § ... § ( Me

n

).


..

, Me
i

=

e + e 2

-

= c h .

, 2 ch e /2 . P (
a n

a)

e

- a

§e

n

2 2

.

= , . P ( a) e
-
a2 n

+n

a2 2n2

=e

-

a2 2n

,

. , , n2 /2 - a. , , .

. .
. , , . . , (, , P ) íí . D 1 , ..., n P (i ) = 0 i . A , A D
n

P ( A | D ) = P ( A | D )( ) =

i =1

Ii () P ( A|i ),

Ii () = 1, i , Ii () = 0 . , P ( A| D ) , P ( A|i ), i . n . : { y1 , ..., yk }. D


.


k

M ( | D ) = M ( | D )( ) =

j =1

y j P ( = y j | D )( ).

: {z1 , ..., zl } D = {1 , ..., l }, i = { : () = zi }, i = 1, ..., l . M (|) M (| D ). D1 ,...,m M (|1 , ..., m ). . . . c1 , c2 1 , 2

M ( c 1 1 + c 2 2 | D ) = c 1 M ( 1 | D ) + c 2 M ( 2 | D ). . M ( M (| D )) = M ( ). . D , . . , M (| D ) = M (| D ). , M (| D ) = . . , M (|) = M . (. [ ]),
k

. íí M ( M ( | D )) = M ,

, . , . ,
k

j =1

y j P ( = y j | D )

=
j =1

y j M ( P ( = y j | D )).

n

M ( P ( = y j | D )) =

i =1

P ( = y j |i ) P (i ) = P ( = y j )

. ,
k

M ( M ( | D )) = .

y j P ( = y j ) = M ,
j =1


. .

.

.

. , ë¨ . , . 0 , 1 , . . , i - (i - 1)- . . . 0 , 1 , ..., m íí , -1, 1 . i i - . i = 0 + ... + i , , 0 , ..., m íí . ë¨ ë¨ ( , ). . . . .

(, , P ) íí 0 , 1 , ..., m , i M (i |i-1 , ..., 0 ) = i-1.

. .
( ). 0 = 0 , 1 , ..., m íí , |i - i-1 | 1 i . a > 0 P (
m

a)

e

-

a2 2m

.

, , , . . . . > 0. P (
m

a ) = P (

m

a) = P e

m

e

a

e

- a

Me

m

.


.

0 = 0, m = ( m - e
m -1

) + (

m -1

-

m -2

) + ... + ( 1 - 0 ),
1

i = i -
m

=e

m

§e

i -1 m-1

.

§...§e

, , . . : Me
m m

=M
i =1

e

i

m

=M M
i =1

e =M

i

|

m -1

, ...,
i

0

=
m

m -1 i =1

e

Me

|

m -1

, ...,

0

.

. h( x ) = ch + x sh . x , , e x h( x ), > 0, | x | 1 ( !). |m | 1: Me
m

|

m -1

, ...,

0

M h(m )|

m -1

, ...,

0

=
m -1

= h M ( m -

|

m -1

, ..., 0 ) .

M (m |m-1 , ..., 0 ) = m-1 . M (m-1 |m-1 , ..., 0 ) = m-1 , ë ¨ , . h ( M ( m -
m -1 i =1 i m -1

|

m -1

, ..., 0 )) = h(0) = ch

e2.
m -1 i =1

2

, , M e Me
m

|

m -1

, ...,

0

e2M

2

e

i

.

ë¨ , Me
m

e

2 m 2


. .

, , P (
m

a)

e

- a

§e

2 m 2

.

, : a = . m 0 = c, P ( m - c P ( m - c . . P (|m - c| a) 2e
-
a2 2m

a)

e

-

a2 2m

- a)

e

-

a2 2m

,

.

c = M i i , , (ë ¨) .


. íí
íí íí .

. .
, . , , , , ë¨ , . , íí ë¨ . , , . ë¨, , , . , íí G = (V , E ), V íí ( , ) , E íí ( x , y ) x , y V , ) x = y ( ), ) ( x , y ) = ( y , x ) ( ), ) E ( ). ), ë¨ ë¨; ), ë¨ ë¨ (. . ); ), ë¨ ë¨; ë¨, ë¨ . . , , íí , , . : [ í ] . . . íí .


. . í í

. . íí
n V = {1, ..., n}. 2 . . N = Cn e1 , ..., e N , V , . , e1 , ..., e N íí Kn . p [0, 1] {e1 , ..., e N } p (. ç . ), . . E , íí . G = (V , E ). , , íí = ( x1 , ..., x N ) . : xi = 1 íí , ei E ; xi = 1 íí , ei E . G (n, p ) = (n , n , Pn, p ), , , |n | = 2N = 2Cn ,
2

Pn, p (G ) = p |E | q

2 C n -| E |

.

- : íí p . G (n, p ) , ë G (n, p )¨. . , , . . : , A? A , , A. , A íí , ë ¨ Pn, p ( A) = Pn, p (G ). . ë¨ , . . n. . . , G (n, p ) , (. ç . ). . {n1 , n2 , n3 , ...} =
G A


. í í
2 2 2 = {C2 , C3 , C4 , ...} p = p (n). , , p = 2 1 1 n, , p = p = 1 - , íí . n ln n { An } íí - G (n, p ). , An , n, , , An n ( , ), n , . . , An (. .), Pn, p ( An ) 1 n . , , , . , . G (n, p ) . . - . , ë ¨. . .

1

. .
, G (n, p ), . . M N M {e1 , ..., e N }, , , G = (V , E ). G (n, M ) = (n , n , Pn,M ), , , Pn,M (G ) =
1 M . , CN

() , . , , , . [ ]. G ( n , p ) .

. .
. , . .


. .

. . . . T3,n G (n, p ), 3 . , T3,n ( Kn ) = Cn , G T3,n (G ) = 0. . . íí n, n . , p (n) = n n . T3,n = 0 (. . ). . p (n) n , c > 0 íí . T3,n =
c3 . 6 c ( n )

. íí n, n . , p (n) = n . T3,n 1 (. . = n ). , íí . , p (n), ë ¨ n ( c 1 , . ); p (n) ; p = o
n 1 ( n )

n 1 , n = o( p ). , 1 - : n ,

, . . , ( ) .. ; ( ) .. ; íí íí ( ) , . , Pn, p (T3,n = 0)
0 e- =e 0!
-
c3 6

(0, 1).


. í í

, , , . , , n ë¨, ë ¨ ë ¨, , ë ¨, , , ë¨. , . . . . , Pn, p (T3,n = 0) 1 n . Pn, p (T3,n 1) 0. (. ç . ): Pn, p (T3,n 1) MT3,n . , , , . (. ç . ), , V = {1, ..., n}, , , 3 3 1 , ..., Cn , i {1, ..., Cn } T3,n,i (G ) = 1, i G ( ), T3,n,i (G ) = 0 . , T3,n = T3, MT3,n = MT3, MT3,
n,i n,1 n,1

1

+ ... + T3,

n,C

3 n

,

+ ... + MT3,

n,C

3 n

.

3 = p 3 i , , , MT3,n = Cn p 3 .

, p = :
3 MT3,n = Cn p 3 =

n

n(n - 1)(n - 2)3 3 3 n! § 3= 0 6(n - 3)! n 6 6n3

, . . . . . , , . -


. .

(. ç . ): Pn, p (T3,n = 0) = Pn, p (T3,
n

0) = Pn, p (-T3,

n

0) =
n

= Pn, p ( MT3,n - T3, ,
DT3

MT3,n )

DT3

,n

( MT3,n )2

.

,n

( MT3,n )2

0, -

. , ; . , DT3,n = MT32,n - ( MT3,n )2 , . . . . MT32,n = M (T3,
n,1

+ ... + T3,

n,C

3 n

)2 .

, , , T3,n,i . ( )
2 MT32,n = MT3, n,1

+ ... + MT32,

n,C

3 n

+
i= j

M (T3,n,i T3,n, j ).

i , j ; . , T32,n,i = T3,n,i , MT32,
n,1

+ ... + MT32,

n,C

3 n

= MT3,n .

,
i= j

M (T3,n,i T3,n, j ) = M 2 T3,n . f

i , j , i , j . : DT3,n = MT32,n - ( MT3,n )2 = MT3,n + M 2 T3,n - ( MT3,n )2 . f , , : ) MT3,n ; ) M 2 T3,n ( MT3,n )2 , , M 2 T3,n = f f


. í í

= (1 + o(1))( MT3,n )2 . Pn, p (T3,n = 0)
DT3
,n

( MT3,n )2 1

=

MT3,n + M 2 T3,n - ( MT3,n )2 f ( MT3,n )2

= = o(1) + o(1) 0,

= MT + 3 ,n

(1 + o(1))( MT3,n )2 - ( MT3,n )2 ( MT3,n )2

. ) ). ) :
3 MT3,n = Cn p 3 = 6(n - 3)! . ,

n!

§

n(n - 1)(n - 2)3 3 3 = 6 , n3 6n3

), - . M (T3,n,i T3,n, j ).
i= j

M 2 T3,n = f

M (T3,n,i T3,n, j ) , i = j . i j = , p 6 ; |i j | = 1, ; |i j | = 2, p 5 . : p 6 , íí p 5 . , 3 32 33 Cn Cn-3 + 3Cn Cn-3 , íí 3Cn (n - 3). M 2 T3,n = f
i= j 3 M (T3,n,i T3,n, j ) = (Cn C 3 n -3 3 + 3C n C 2 n -3 3 ) p 6 + 3Cn (n - 3) p 5 .

,
M 2 T3 f
,n

( MT3,n )2

1.
n
2

,
3 Cn C 3 n -3

6,

n

3

C

2 n -3

2,

n - 3 n,

M 2 T3,n f ,
n4 p 5 1 1 0, =2= n ( n ) np n6 p 6 n6 n5 n6 n4 n4 + 4 p 6 + 2 p 5 36 p 6 + 2 p 5 . 36


. .

M 2 T3,n 36 p 6 . f
3 ( MT3,n )2 = (Cn p 3 )2

n

6

n6 6 p, 36


M 2 T3 f
,n

( MT3,n )2

1.

) , . . . . , , , , : , , , . . , , , T3,n . , . . . , - c 3 , Cn p 3 . p , n , MT3,n =
n(n - 1)(n - 2) 3 n 3 c3 c3 §p § 3= . 6 6n 6

, : , , r M r T3,n f r (. ); r = 1 . , M r T3,n f r n . r = 1 r = 2 (. . . . ) : , íí 2 . . . . , T3,n i , j T3,n,i , T3,n, j . r - : M r T3,n = f M (T3,
i1 ,...,i
r

n,i

1

§ ... § T3,

n,i

r

),


. í í

r , 3 Cn . , (i1 , ..., ir ), i1 , ..., ir , . 1 = 1 (n, r ); 2 = 2 (n, r ). : ) 1 r ; ) 2 = o(1 ). . ). 1 , r {1, ..., n} r . , p 3r . (. . r n- ) , 3r > n,
3 Cn § C 3 n -3

§...§C

3 n-3(r -1)

. , . , 3r n
3 1 = C n § C 3 n -3

§...§C

3 n-3(r -1)

§ p 3r .

r
3 r (C n p 3 )r ,

n .
-1)


3 3 3 Cn-3(r Cn Cn-3 1 r 3§ 3 §...§ 3 Cn Cn Cn

.

i {1, ..., r }
C
3 n-3(i-1) 3 Cn

C

3 n-3(i-1) 3 Cn

1

=

(n - 3i + 3)(n - 3i + 2)(n - 3i + 1) = n(n - 1)(n - 2) 3i - 3 n 3r

= 1-

1- n-1 1- n-1
3r

3i - 3

1- n-2
3r

3i - 3

1- n

1- n-2

1- n-2

3r

3

1.

, r 1 r , n , ) .


. .

). , 2 = o(1 ), n . 1 r = const. , 2 = o(1). 2 (i1 , ..., ir ), {i1 , ..., ir } ( ). 2 2 =
3 r -1 s =4

s , , s i1 , ..., ir t , s (.

s M (T3,n,i1 § ... § T3,n,ir ) |i1 ... ir | = s. , |i1 ... ir | = s, i1 , ..., ir , . ). , M (T3,
n,i
1

§ ... § T3,

n,i

r

) = pt

1 ct 1 = n § O ns , nt

O , .

a) r = 4 , s = 7 , t = 1 0
.

) r = 3, s = 8, t = 9

, s s s C (s, r ), (s, r ) n. Cn = O (n s ),
s n

2 =

3 r -1 s =4

s =

3 r -1 s =4

s C n § ( s, r ) §

1 1 §O s n n

=
1 1 §O s n n

= ) ,

3 r -1 s =4

O (n s ) §

=O

1 n

= o(1).

.


. í í

. .
, , . . . , . , , , ë¨ ë¨ . . . . . . p = n . c > 1, . c < 1, . ! , , . . ( ) . . . . . . p = n . c
c ln n c ln n

3n
1 n

100,

Pn, p (G ) > 1 - . . ë ¨: , . . . . . , , , . , , , . . , - (. . ). ë ¨. , q . , q ,


. .

.

ë¨ ? ? ! - , -. : . , q íí , p . . , p =
3 ln 2000 0,01 ( , q 0,99), 2000 1 1 - > 0,999. , 2000

? ë¨ 0,99 , , 0,999! , , , , , . , , , , . , : 2 íí C100000 ... , . , , -


. í í

. , , -, ., . , , . , : , , (. ., , ). , - . , . . . . , . . G (n, p ): Xn = Xn (G ) = 0, k, G , G k .

, Xn , Xn = 1. , Pn, p ( Xn = 0) 1 n . Pn, p ( Xn 1) 0. (. ç . ) Pn, p ( Xn 1) MXn , . Xn Xn = X
n,1

+...+ X

n , n -1

,

Xn,k = Xn,k (G ) íí k - G . k - V k () : K1 , ..., KCn . , , k Xn,k = Xn,k,1 + ... + Xn,k,Cn , X
n,k ,i

=X

n,k ,i

(G ) =

1, 0

Ki G , .
n -1 C
k n

M Xn = MX
n,k ,i

.

k =1 i =1


. .

, MX
n,k ,i

= Pn, p ( Ki G ) Pn, p ( Ki V \ Ki G ).

, G , ë¨ Ki ( G |Ki ). (. . ), Pn, p ( Ki V \ Ki G ) = q , , MX
n -1 C n k =1 i =1
k n

k (n- k )

,

q

k (n- k )

=

n -1 k =1

k Cn q

k (n- k )

.

k

K

n-k
i

V
.

, k n - k . k = 1: nq
n -1

= n (1 - p )

n -1

ne

- p (n-1)

e

-

3(ln n)(n-1) n

.

n nq
n -1

n-1 n

0,9. , =
1 . n2,7

e

-2,7 ln n

:
C
k+1 (k+1)(n-k-1) q n k Cn qk(n-k)

=

n-k §q k+1

- k + n - k -1

.


. í í

k

n n . , , k ,
2 8 n-k §q k+1
- k + n - k -1

(n - 1)q
-
9 ln n 4

3n 4

-1

(n - 1)e
-2 ln n

-

9 ln n 4

+p

ne

-

9 ln n 4

+1

.

n ne
+1

ne

= n.

1

, k
n

n 8
p n2 16

. k > 8 :
k C n < 2n ,

q

k (n- k )

q

nn § 82

=q

n2 16

e
-
3n 16

-

e

-

3(ln n)n 16

.


k Cn q k (n- k )

2n § n

.

n , k = 1 ( ). , MX . . . . , - . -, , , c > 1, . . -, c < 1? , Pn, p ( Xn > 1) 1, n . . : . ( ) . . . , . ( ) ë ¨.
n -1 n k =1

1 . n2,7

1 n < 2,7 0, n2,7 n

n ,


. . ln n

, p n . . . . p =
ln n + c + o(1) . n
-e
-c

Pn, p (G ) e
ln n

.

, p = n e-1 . [ ], . , . . . . , . . p = . c < 1 n = (c) > 0, ln n . c > 1 = (c) (0, 1), , n. , , [ í ]. , , . , . , , [ ] [ ]. . , ë ¨, . . p n (. [ , ]). , , . ë¨ , . ë¨ 1 - , n , , , íí n. . , , :
1 1 c


. í í

, , íí íí . , íí . . . , . íí , íí . , ë¨. , . . , , p íí , [0, 1]. n, p n ; , . ; , p n .
ln n 1

. .
: . . . . , , G = (V , E ) (G ), , , . , (G ) = min{ : V = V1 ... V , i x , y Vi ( x , y ) E }. ë¨ , Vi . íí ë¨ . , , . . , . , , ? , íí , , .


. .

[ í ] , . , . , , . , (G ) = max |W | : W V , x , y W ( x , y ) E , (G ) = max |W | : W V , x , y W ( x , y ) E . (G ) G , (G ) . , , ë¨ (. . ) . , (G ) ( G ) ( G )
|V | . ( G )

, , , , , íí , . , , . . = ( n) = o . p = 2 . = n ,
,p

1

log2 n

Pn

(G ) -

n > ( n) 2 log2 n
-

0,
5

n .

. p = n u = u(n, ), Pn, p (u

, > 6 . u + 3) 1, n .
2 log2 n

(G )

, ë n . ¨ n , , ( ) , . ë ¨, p = 2 1


. í í

(. ç . ), . . íí , . ë ¨ , , ë¨ , . . : ë¨ n n (1 + ) , (1 - )
2 log2 n 2 log2 n

> 0 íí ; n (.
2 log2 n

. ). , . , , , , n ! , , íí . - n n (, , );
log2 n

. , , , , -, . , {u, ..., u + 4}, . u. . , . . p = const = ; p , n- . , . [ , , ]. , , : > 6 , u + 3 u + 1. .
5 1 2


. .

. íí . . . , , . . . . , . . íí . . ( ), . . u . . . . . , . . . íí G (n, p ). 2 Y0 , ..., YN , N = Cn . , e1 , ..., e N íí n . G n i {0, ..., N } Yi (G ) = M (| H n : j i e j E ( H ) e j E (G ) ). E (G ) íí , , . .
k

M ( | A ) =

i =1

yi Pn, p ( = yi | A).

, . , Y0 , ..., YN íí (. ç . ), , . (. [ ]). , Y0 = M , YN = . . : Yi (G ) = M (| H n : x , y i ( x , y ) E ( H ) ( x , y ) E ( G ) ),

i = 1, ..., n.

Y1 , ..., Yn íí . , Y1 = M , Yn = .


. í í

( ), |(G ) - ( H )| 1, G H ( ). , : (), () , . . |Yi - Yi-1 | 1 i . . , , . . , (. ., , ) . íí m . N n - 1 . : , . . . , . , Pn, p (| (G ) - M | Pn, p (| (G ) - M | a) a) 2e 2e
- -
a2 2(n-1) a2 2N

,

.

, . íí . . . . : . . p = n- , > 6 . V íí G (n, p ). n Pn
,p

5

S V , |S |

n ln n, (G |S )

3

1-

1 . ln n

, , . , . . . . . , , n . íí . n, > 6 .
5


. .

n u = u(n, ), Pn, p ( (G ) Pn, p ( (G ) , u u Pn, p ( (G ) u) >
1 . ln n

u n

3, n) = 1

n, . u - 1)
1 Pn, p ( (G ) ln n

u)

1-

1 . ln n

, u íí , , . - , (G ) u + 3. : íí . Y , S V , V u: Y (G ) = min |S| : S V , (G |
V \S

)

u.

, Y . : Pn, p (Y (G ) - MY Pn, p (Y (G ) - MY a = a) - a) e
-
a2 2(n-1)

, .

e

-

a2 2(n-1)

2(n - 1) ln ln n. Pn, p (Y (G ) - MY Pn, p (Y (G ) - MY a) - a)
1 , ln n 1 . ln n

, MY Pn, p (Y (G )

a. , 0) Pn, p (Y (G ) 0) = Pn, p ( (G ) M Y - a) u) >
1 . ln n 1 . ln n

Pn, p (Y (G ) .


. í í

, MY < a. Pn, p (Y (G ) . . Pn, p (Y (G ) 2 2(n - 1) ln ln n) 1- 2a) Pn, p (Y (G ) M Y + a)
1 , ln n 1 . ln n

A1 , . . , S V , |S | n ln n, (G |S )
1

3.

. Pn, p ( A1 ) 1 - ln n A2 , (G ) , Pn, p ( A2 ) , , A3 íí Y (G )
1 1 . 1- ln n

u.

2

2(n - 1) ln ln n.

, Pn, p ( A3 ) 1 - . ln n A1 A2 A3 . G , : ) (G ) u; ) Y (G ) 2 2(n - 1) ln ln n ) (G |S ) 3, G A1 A2 (G |V \S ) u. ) (G ) u + 3. Pn, p (u (G ) u + 3) 3 1, ln n

P ( A1 A2 A3 )

n .

. . . . :
1 , ln n

Pn
,p

S V , |S |

n ln n, (G |S ) > 3

n . , , n . , S V , |S | n ln n, (G |S ) > 3


. .

. , , S , . ., S , x S S \ { x } . , , : A = T V , 4 |T | n ln n , T , (G |T ) > 3 .


S V , 4

|S |

n ln n, (G |S ) > 3 ,

, = [ n ln n], A=
t =4 T V , |T |=t , T

A t ,T ,

A
t ,T

G A | E ( G | T )| (G |
T \{ x }

= T , |T | = t , (G |T ) > 3 .
t ,T

t T ,

3t . 2

, x T . , ) 3, , (G |T ) 4. , x G |T (. . E (G |T ), x ) . | E ( G | T )| 2 . A B
t ,T

3t

t ,T

Bt ,T ,
3t . 2

=

= T , |T | = t , | E (G |T )| ,


Pn, p ( A)
t =4 T V , |T |=t , T

Pn, p ( At ,T )
t =4 T V , |T |=t , T

Pn, p ( Bt ,T )
t =4 T V , |T |=t , T s Cr p s ,


. í í

r = Ct2 , s =

3t 2

. . , ).
t =4 ts Cn Cr p s .

( § ,

C

b a

ae b

b

, e = 2,71828... íí

. , .
t =4 ts Cn Cr p s t =4

ne t ne § t

t

§
te 3

re s

s

§p

s

t =4

ne t
t

t

§


t2 e 2 § 3 t /2

3t /2+1

§n

-§3t /2

=

3/2

=
t =4 t =4 t =4

§n

-3/2

§3


te

t =4

t 3§n§ t§n

-3/2 t

t 3§n§ §n t 3n
5/4-3/2

-3/2 t

t =4

t 3§n§

n ln n § n

-3/2 t

ln n .
5 3

t

, > 6 . , 4 - 2 = - < 0. ,


5

t 3n
t =4

5/4-3/2 [ln n]

ln n
-

t



=
t =4 t

t 3n

-

ln n

t

= ln n
- t

=
t =4

t 3n

ln n +
t =[ln n]+1 -

t 3n ln n
4

-

[l n n ] § [l n n ] § 3 n

+ n § n § 3n

ln n

[ln n]

<

1 . ln n

n , . . . . . n , log2 n

) 1 = 1 (n) = o Pn
,1/2

(G )

n - 1 ( n ) 2 log2 n

1,

n ;


. . n , log2 n

) 2 = 2 (n) = o Pn
,1/2

(G )

n + 2 ( n ) 2 log2 n

1,

n .

. Pn
,1/2

((G )

[2 log2 n] - 1) 1,

n .
|V | , , ( G )

? , , (. . . . ), (G )

, . k = [2 log2 n] Xk , G k . Pn
,1/2

((G )

[2 log2 n] - 1) = Pn

,1/2

( Xk = 0).

, 1 - MXk , , MXk 0. : M Xk = C C
k n k n

1 2

C

2 k

.

1 2

C

2 k

nk - §2 k!

k2 2

+

k 2

n

2 log2 n

k!

§ 2-

(2 log2 n-1)2 /2+log2 n

=
e k
k

=

1 § 22 k!

log2 n-2 log2 n+3 log2 n-1/2 2 2

=

1 § 23 k!

log2 n-1/2

§ 23

log2 n

,

k ! : MX
k

k e

k

( ). 23
log2 n+2(log2 e) log2 n-[2 log2 n] log2 [2 log2 n]

23

log2 n+k log2 e-k log2 k

.

, . , MXk 0, .


. í í

. . .

:

ë¨ . , . , . . , íí . , , . , , . . . .
n

:

, Pn,1/2 ( A) 1, n , 2 log2 n m = m(n) = o log2 n A = S V , |S| = m, (G |S ) k .

, k = k (n)

G A. A K1 k ( n > m). K1 . K1 V . n - k m, A K2 V \ K1 , . , Kl m . , l
n-m k



n . 2 log2 n

1 1 1 1 1 1 k 2 2 2 2 2 2 k l+1 l+2
.

K

1

K

2

lll lll k

K

l


. .

l + 1, l + 2, ... , n l+m
2 log2 n

(. . ). , Pn
,1/2

( ( G )

l + m)

Pn

,1/2

( A) 1,



.

. . . : -, m =
n . , , log2 n 2
C
2 k

k 2 log2 m 2 log2 n,
k Cm 2-

> m4 .

. . , , . , m k Pn,1/2 ( A) 1. , , , Pn
,1/2

( A) 0.

A = S V , |S| = m, (G |S ) < k =

AS ,
SV , |S|=m

AS = S, |S| = m, (G |S ) < k . , Pn Pn
,1/2 ,1/2

( AS ) S. ,
,1/2 m ( AS ) = Cn Pm ,1/2

( A)
SV ,|S|=m

Pn

((G ) < k ).

Yk íí G (m, 1/2), k , : Yk (G ) = max | |: = { K1 , ...}, Ki íí G | Ki K j | 1.


. í í

Pm
,1/2

((G ) < k ) = Pm

,1/2

(Yk = 0).

, Yk (. . . . ), , , Xk (. . . . ). , {(G ) < k } ë¨ {Yk = 0}, , , { Xk = 0}. . . Yk , . Pm
,1/2

(Yk = 0) = Pm

,1/2

(Yk
,1/2

0) = (-Yk 0) = Pm
,1/2

= Pm

( MYk - Yk

MYk )

e

-

(MYk )2 2 2Cm

.

. MYk
m2 (m), 2k4

(m) 1. , :
m Cn Pm ,1/2

((G ) < k ) < 2n Pm

,1/2

(Yk = 0)

2n e

-

(MYk )2 2 2Cm

2n e

-

m4 2 4k8 m2

= 2n e

-

m2 2 4k8

.

, , , n. , , ë ¨ . : , ? : , . . . . :

, ë ¨ k . , , . ? , ? , , . G m = { K1 , ..., K x (G )} k . G


. .

, x (G ) ; , Xk , . G x (G ) p , . i , ë¨ Ki , íí . = (G ) k - G ( ). , G . , ë ¨ íí íí . (G , (G )), , . . Pm
,1/2, p


(( G ,

(G )) = Pm

,1/2

( G )( p )

| (G )|

(1 - p )

x (G )-| (G )|

.

, M | | = p M |
k | = p M x = p MXk = p Cm 2-Ck .
2

, , íí , . . G (m, 1/2). . G (m, 1/2), íí . ,


W = W (G ) = {( Ki , K j ) : Ki , K j


,2

| Ki K j | ,2

k - 1}, k - 1}.

W = W (( G ,

(G ))) = {( Ki , K j ) : Ki , K j

| Ki K j |

, () () k - , íí , Yk . , M |W | = ( p )2 M |W |. M |W | íí . , . , |W | = Wr = ( Ki , K j ) : Ki , K j , | Ki K j | = r .
k -1 r =2

|Wr |,


. í í

(. . ) M |W | =
k -1 r =2

M |Wr | =

1 2

k -1 r =2

k Cm C

k -r m- k

r Ck 2-

2 2C k + C

2 r

.

- . - ! , - . . , M |W |
( MXk )2 k4 . 2 m2

K r K
i

j

k k m
.

V

. G (G ) W . = (G ), , . , MYk M|


|

M | | - M |W | = p M X k - p =
m2 . ( M X k )k 4 1 (m )

( p )2 ( MXk )2 k4 1 (m) , 2 m2

1 (m) 1.

, , , m
k MXk = Cm 2- C
2 k

>m

4

0 < p <

1 < 1. m 2 k 4 1 (m )

( , - !) MYk =
m 4 k 4 1 (m ) m2 m2 - = 4 (m), 28 2 k 1 (m ) 2 m k 1 (m ) 2k
4

1 . . 1


. .

.. . , . ,

.

, . , , G m Yk (G ) c
m2 , k2

c > 0.

, , 2 Yk , Ck ( ), ( 2 ). íí Cm . 2 2 , Yk (G ) Cm /Ck , . , MYk c
m2 , k2

c > 0,

, , , m k . k 2 4 log2 m. , , , 2 , - . , .
m2 (m) 2k4

MYk

c

m2 , k2

c > 0,

, , . ? , . , Pm
,1/2

(Yk = 0)

e

-

m2 2 4k8

,

, Pm
,1/2

(Yk = 0)

e

-

m2 ck 4

.

( , . [ , , ]); , , - .


. í í

. . . Yk Xk , ? , Xk , . . , , , Yk . ( Yk ) . . . ,
m Cn Pm ,1/2 m Cn Pm,1/2 (Yk = 0), m Cn Pm,1/2 ( Xk = 0). , . . . . , Xk . , . , ( , , ). (. . . . . . . ):

((G ) < k ) 0.

Pm

,1/2

( Xk = 0) = Pm

,1/2

(X

k

0) = Pm

,1/2

( M Xk - X

k

M Xk )

DXk . ( MXk )2

, m . m k , . . . , MXk > m4 , , , . ? , 2 MXk : M 2 Xk = f M ( X k , i X k , j ),
i= j k i , j {1, ..., Cm },

Xk,i íí ëi - k - ¨. () . ? M |W | . . ! , , ( MXk )2 m .
m Cn =

DX

k

n(n - 1)...(n - m + 1) = m! m n 1 2 m-1 = m! 1 - n 1 - n ... 1 - n

m nm 1- n e(m/2)m

m


. .

( m! e(m/2)m ). , íí
n m
m

(log2 n)m , 2

. ,
m Cn Pm ,1/2

((G ) < k ) 0,

Xk . , : m k . , . . , k1 2 log2 n k2 2 log2 n, , , , , : ) ) k2 . G (n, 1/2) k1 ; G (n, 1/2) m -

, k2 , . , . . . . u íí . , , u . u , , p = n-0,9 . , Pn, p ( (G ) ln n) 1. , .

. , , (. . . . ) Pn
,p

(G )

n ln n

1


. í í

MXk 0, , n
k M X k = C n (1 - p ) C
2 k

k=

n . ln n

ne k

k

e

- pC

2 k

(3 ln n ) k e

-

p k2 4 1,1

e .

k ln ln n+k ln 3-n

/16 ln2 n

0

. .
. . , Pn
,1/2

((G )

[2 log2 n] - 1) 1,

n .

, G (n, 1/2) . , (G ) íí . , (G ) (G ) n (G ) (G ) . íí , . . . - , (G ) = (G ) ( ). íí . , : H ( H ) = ( H ). , . . , , ? , , . ( ), ë¨ . , (. . ) . , , ( , , íí ).


. .

- ë¨ . : , , . . , ë ¨, : , 5 ( ). . , .

.

-, , ë¨ ( ), , ë ¨. , 5 , íí . . . , . . ( ). (. [ ]) ! , .

. .
, : , . , , , , ,


. í í

íí . . . , s, t . R(s, t ), n, Kn K s Kn , , Kt Kn , . , . , R(3, 3) 6: , , , ; , , . , , , R(3, 3) = 6. , . R(s, t ), . , : R(s, t ) íí n, G n (G ) s, (G ) t . G , , G , íí . ( K s Kn ) (G ) s, ( Kt Kn ) (G ) t . , . [ ] . . (. [ ]). , . . , , , . . [ ]. , , ( ) R(s, t ) . . : [ , , , í ]. . R(s, t ). , R(s, t ) = R(t , s), R(1, t ) = 1 R(2, t ) = t . . , , [ ], .


. .

, R(s, t ) < . , (. [ , ]) R( s , t )
t -1 R(s, t ) C s+t -2. s = t ( R(s, s) ). (., , [ ]):

R(s - 1, t ) + R(s, t - 1),

n! C
s -1 2 s -2

2n e

n

n

.

=

(2 s - 2)! ((s - 1)!)2

(2(s - 1))(s - 1)

2(2 s - 2)(2 s - 2)2

s-2 2-2s

e

2s-2 2-2s

e

=

4

s-1

( s - 1 )

.

, 4s . , , , , , , . , , íí ë¨. R(s, s) (. [ ]): R( s , s )
4 e
s ln2 s/ ln ln s

.

íí , , , , e . . R( s , s ) (4 - ( s )) s , (s) 0, (s) - > 0. . , R(s, s) (4 - )s ( = 10-6 = 10-1000 ), . , . . , G n (G ) < [2 log2 n] (G ) < [2 log2 n]. s = [2 log2 n], R(s, s) > n. n s. : s 2 log2 n n 2
s/2 ln2 s/ ln ln s

= o(4 s ),

.


. í í

. . ( . ) , R( s , s ) (1 + o(1))
1 s2 e2
s/2

.

(. [ ] [ , , ]), . (!) (. [ , , ]). (1 + o(1)) , , ( 2 + o(1))
s

2 s2 e

s/2

R( s , s )

4 e

s

ln2 s/ ln ln s

,

R( s , s )

(4 + o(1))s .

, , , 2 log2 n, . ( ). , ( ). (. [ ])!

. .
, - , , , , , . . G . g(G ). ëgirth¨ íí ë¨. , , . , , . : , -


. . n ) 2 log2 n

( (G )

- ((G ) 2 log2 n). , íí , , , , . , k -
2 Ck 2 , , -

k

2

k : k , . 2 . . . k , l G , g (G ) > l (G ) > k . , ? . 0,
1 l

k

2

G (n, p ),

p = n -1 . Zl , l .
l

M Zl =
i =3

C

i n

(i - 1)! i p. 2

i (i - 1)! Cn 2 íí i - Kn (i - 1)! ( , i 2

), i , l , . :
l

MZ , i

l i =3

ni (i - 1)! i § §p < i! 2

l

(n p )i .

i =3

1 l , < . , l

(n p )

i

n

l

= o( n ).

M Zl = o(n), l íí . Pn
,p

Z

l

n 2

M Zl = o(1). n /2


. í í

n1 , n > n1 Pn t=
3 ln n . p
,p

Z

l

n 2

< 2 Pn

1

,p

Zl < 2

n

> 2.

1

: Pn, p ((G ) t ) = Pn, p ( X = ne
-
p (t-1) 2

t

1) ne
-

t

p ((3 ln n/ p )-1) 2

t M X t = C n (1 - p ) t

C

2 t

nt e

-p

t(t-1) 2

=

ne =

-1,5 ln n+ p /2 t

=
t

1 (1 + o(1)) n

= o(1).

, n2 , n > n2 Pn, p ((G ) t) <
1 1 Pn, p ((G ) < t ) > . 2 2 n , (G ) < t 2

, n > max{n1 , n2 } Pn
,p

Zl <

> 0, .

. . G n , n 2 , l , t . i - (i l ) G n G , ,
2

, l , - (G ) < t . , (G )
np n /2 n = . t 6 ln n 6 ln n

n > n3 (G ) > k , . . n > max{n1 , n2 , n3 } g(G ) > l (G ) > k . .

.

.

. (., , [ ]), , ,


. .

. íí , , , . , , . . . .

. ë¨, . , , , [ , ]. , - ë ¨. , , ( ): ë¨ ë¨, . . . , (ë¨). , , , (=), , ë¨ ë=¨, , , ë¨, . , ë ¨ ë ¨ . . , , . , ë ¨: . - , , . , . . . . x y z ( x y ) ( x z ) ( y z ).

. p = p (n) íí , pn (1 - p )n > 0, A íí , ,


. í í

. , , p . , p íí , (
1 , ln n 1
1/10000

A , . , Pn, p ( A) 1, Pn, p ( A) 0.

n

) ,

. ! . . , . . , . . . . , . . . . . . p = n- , > 0 íí , A íí , , A , . , Pn, p ( A) 1, Pn, p ( A) 0.

, - . , , ? . ! , . , A íí ë ¨ = 1. c = 1 Pn, p ( A) 1 - e
-1/6

{0, 1}. , ,

, . . , . , . . . . .

. .

íí G = (V , E ) H = (W , F ). íí . k . . . (, ë¨ ) . , i


. .

G xi V . , yi W . íí x1 , ..., xk V y1 , ..., yk W . ; . , G |{
x1 ,..., xk }

,

H |{

y1 ,..., x y }

, . . i , j {1, ..., k } ( xi , x j ) E , ( yi , y j ) F . , , , . EHR(G , H , k ) , Ehrenfeucht (. [ ]). , . , . , EHR(G , H , k ), , , . íí G (n, p (n)) G (m, p (m)). íí V ( n) W ( m) íí , p , n m . G ( G (n, p (n)) H ( G (m, p (m)) (G , H ) Pn
, m, p

((G , H )) = Pn

, p (n)

(G ) § Pm

, p ( m)

( H ).

, , . , , P ( n, m , k ) = = Pn
, m, p

(G , H ) : EHR(G , H , k )

.

íí . p , k
n , m

lim P (n, m, k ) = 1.


. í í

[ ], [ ]. , . . . .

, G = (V , E ) k , a, b, a + b k , u1 , ..., ua , v1 , ..., vb V x V , ( x , ui ) E ( x , vi ) E i . G H k , EHR(G , H , k ) . , i k x1 , ..., xi-1 G y1 , ..., yi-1 H . i - () xi G . x1 , ..., xi yi H , y1 , ..., yi . . , , k , P (n, m, k ) 1 . , . A
u1 ,...,ua ,v1 ,...,vb , x

, , x ui vi . u1 , ..., ua , v1 , ..., vb , x . , Pn, p ( A , Pn
,p u1 ,...,ua ,v1 ,...,vb , x

) = p a (1 - p ) b . = 1 - p a (1 - p ) A
b n- a - b



x {u1 ,...,ua ,v1 ,...,vb }

A

u1 ,...,ua ,v1 ,...,vb , x

.

, Pn
,p



a,b : a+ b k



u1 ,...,ua ,v1 ,...,vb



x {u1 ,...,ua ,v1 ,...,vb } 2k

u1 ,...,ua ,v1 ,...,vb , x

k n (1 - )

k n- k

,

= min{ p , 1 - p }.

, , : a b, a + b k ,


. .

u1 , ..., vb , x x ui , x vi . , , . , k 2 n k (1 - k )
2 n- k

k 2 nk e

- k ( n - k )

.

, k k , k íí ( ). , n
1/(2k )

, ) § n, .

k, . , n k n = ( n . . e , nk e .
-n - k n 1/(2k ) k


-n

0,

. .
íí . , - , , , . . , . . . . , íí . -, íí , : n - 1 n . , , Tk , , k - . , k 2. . : ) p = o(n-k/(k-1) ), Tk = 0;


. í í
-k /(k -1)

) p cn

, Tk
c
k-1 k-2

=
k /(k -1)

k k!

;

) pn pk n - ln n - (k - 1) ln ln n -, Tk 1; ) pk n - ln n - (k - 1) ln ln n x , Tk = ; k § k! ) pk n - ln n - (k - 1) ln ln n , Tk = 0. . p ( ), ë¨ : ; p , , ; p , ... , p ? ? , - , , : , p n ; ? íí . [ ], . MTk ; ; ; ; , , MTk 0. , k k k-2. (. [ ]). , Tk (. ç . ). . . (. [ ]). p
c . n
k -2 k -1

e

-x

ln n

. k
e-ck , k!

2 c > 0 íí .
(c - 1)(ck)k-1 e k!
-ck

k = n k

c

2 = k
x

k -

1+
t2 2

,

( x ) =
-

e

dt .


. .

sup Pn
x ,p

Tk - k

k

x - ( x ) = O

1 . n

íí : k k (. . ). . p = , c < 1. n , . (. [ ]). , c . , p = n , c < 1, ë-¨ ( ), íí . (. . p
1 ) . n c

. . . . , , c p = , c < 1, n . , , p . , , p = n- , 1, : . , > 1 íí ( , ), . . , > 2 , . , < < 1 6 . (. . . . ), . .
5


. í í

. . . , , . , K4 (. . ), K5 . , , . (. [ ]): , K5 K3,3 . K3,3 íí (. . ), , (. . ).

.

.

.

. (. [ ]) íí , .


. .

K5 K3,3 , . , . . , . . p = n . c < 1 , c > 1 . c < 1 , , , . c > 1 . , n 3n - 6 . ! , , n . . . . . ( íí ) . , . . , v G (n, p ) deg v , v , Binom(n - 1, p ). , : d1 d2 ... dn . di [ ]. , . . p = 2 . i [3 log2 n] di - di+1 3. , di i . , .
1 1 c


. í í

. . . . n. : , n , ? . , . (. [ í ]), , , , , ... . , . . . p = . n 2 n , Pn,1/2 ( n ) 1, A, G , H n O (n2 ) A G H . : , . . n . G n . G : di (. ) xi . m = [3 log2 n] . i di - di+1 2, , G n (. ). a(i , j ) = 1, xi x j i = j , a(i , j ) = 0 ,
m

1

f ( xi ) =
j =1

a ( i , j )2 j ,

i = 1, ..., n.

i , j , f ( xi ) = f ( x j ), , G n . , n . , G , H n n O (n2 ) . , G , H n , A . f ( , ); G , H , . O (n2 ) . , , íí , Pn,1/2 ( n ) . -


. .

: . , . ë¨ di ( ), [ ].


. íí
íí .

. .
n V = {1, ..., n}. , 2 . , N = Cn e1 , ..., e N V . N , ( ) p [0, 1]. i j pij , . -, . . : N , - . , - , pij , , n. , . . G (n, pij ). G (n, pij ) = n , |n | = 2N , Pn
, pi
j

n

, Pn

, pi

j

, (1 - pij ).

(G ) =
(i , j ) E

pij §

(i , j ) E

. , , , (., , [ ]). . n ( n ) n = ( n , n ), n = V , n {e1 , ... ..., e N }. p = p (n) [0, 1] pij = p ,


. .

(i , j ) n , pi, j = 0, (i , j ) n . , n , , n , . G( |n | = 2| n | , Pn, p (G ) = p |E | (1 - p )
|
n

n

, p ) = ( n ,

n

, Pn, p ).
|-|E |

.

, n = {e1 , ..., e N } íí : G ( Kn , p ) = G (n, p ). . ë¨ (. . . . . . . )? . n . , ( , / ). ( n ) íí ë¨ ë ¨.

. .
n , íí n- ( 2n ), n- [0, 1]n , , . , íí ( , )-, n . ,
2

= ({(0, 0), (0, 1), (1, 0), (1, 1)},

{((0, 0), (0, 1)), ((0, 0), (1, 0)), ((1, 1), (0, 1)), ((1, 1), (1, 0))}). G ( n , p ). . . , , . . ë¨
ln n 1 . , n 2


. í í 1

. p < 2 , 1 G ( n , p ) . p > , 2 G ( n , p ) . , . . ë¨, . . p = 2 ln n e-1 . , p = n íí G (n, p ). . . p = . n o(2n ). c > 1 2n .
c 1

c < 1 G ( n , p ) = (c) (0, 1),

: o(2n ) íí , , , 2n . , c c , c < 1, , p , c > 1, p
n

, p > íí . 2 , ( !), , , . ! , n G (n, p ) ( n G ( n , p )) n G ( n , p ) . n íí , íí : n = log2 2n . ( p = p (n)) . m = 2n : p = p (m) =
1 ; log2 m 1 p = . 2 ln n 1 , : , 2 n 1 1 . n log2 n

1

n





[ ].


. .

. .
n

k íí . n = 4k . = ( n , n ) ,
n

= x = ( x1 , ..., xn ) : xi {0, 1}, x1 + ... + xn = 2k ,
n

|x - y|, , x, y n . , n íí ( , )-, , , . n , 2k . , , , k . , x = ( x1 , ..., xn ), y = ( y1 , ..., yn ) < x, y >= x1 y1 + ... + xn yn : |x - y| = 2k < x, y > = k .

= (x, y) : |x - y| =

2k ,

n . ë¨ : , íí ë¨. , , : 2k , . . , , . , ( ) íí n , ( ). . , , . n , ( ). n íí íí íí , . (. [ , í ]). .


. í í

, G ( n , p ). n , . : n n , íí , -. , n m = Cn /2 = | n | G ( m , p (m)) ( , n m n ). m n, (. . G m ). , , íí . , Kn . . ( ) m . , , .

. .
. . . . m = m(n) n . (. ç . ): m=C
n/2 n

=

n! 2nnn e-n 2 n(n/2)n e-n = ((n/2)!)

2 2n . § n

: m=
2 2n § (1 + 1 ( n )), n

1 íí , n . : ln m = ln
2 (1 + 1 ( n )) + n ln 2 - ln

n.


. .

, n=
ln m (1 + 2 ( m )), ln 2

2 = o(1).

. . . . . (
m

)

4

n+2
3n +5 4

n3

(1 + 3 ( n )),

3 (n) 0,

n .

. n = 4 a , íí , (
m

)

4n 2 § n/4 § (1 + 4 (n)), 3 n 27

4 (n) 0, n . . n (
m

)

(1,99 + o(1))n .

, ; . , n = 4 a (. . , k íí ) . (
m

)=

4 3
3/4

+ o(1)

n

= (1,754... + o(1))n .

n , ( ) : (1,754... + o(1))
n

(

m

)

(1,99 + o(1))n .

. .
n/2

F = x = ( x1 , ..., xn ) m . . )

m

:
i =1

xi =

n 8

-1 .

, F íí F n , (. 4 .


. í í

>
n 8

-1
n 2

n 4

0

n

.

q=

n
n i = 2 +1

xi =

n - 2

n 8

-1 .



n - , [0, 1), 8 n n 3n nn q= 2- - 1 = 2 - 8 + 1 + = 8 + 1 + . 8 n 8

=

|F | = C

[n/8]-1 q Cn/2 n/2

=C

[n/8]-1 2 n/2

.

, 1 = = 1 + , , 2 2 (
m

)

=



|F | =

n 2

!

n 8

- 1 !q !

=
n
n 2

n 2

!

n 8

- 1 !

3n 8

+ 1 !

n 2

e

n -2

=

n 4

- 21
1 3

n 8

- 1

n -1 8

e

n - 8 +1

3n 4 n 2 n

+ 21

3n 8

+ 1

3n +1 8

e

-q

2

½ (1 + ( n )) =

n
3 16

n2

2

=
3 16

n 8 nn 2

- 1

n -21 4

3n 8

+ 1

3n +21 4

2 (1 + 3 ( n )) =

½

n

n 8

n -21 4

1-

81 n

n -21 4

3n 8

3n +21 4

1+

81 3n n+2

3n +21 4

2 (1 + 3 ( n )) =

=
3 16

1 2

n
3n +21 4

n 4
n+2

1 8

n -21 4

(1 + 3 ( n )) =

4 n3

3 8

3n +1+21 4

(1 + 3 ( n ))

n3

3n +5 4

(1 + 3 ( n )).


. .

n, , 1 + n e. . . - k -1 , ( m ) 2Cn-1 ( k ). [ ], . : (
m

1

n

)

2C

n/4-1 n -1

=
n 4

2(n - 1)! -1 !
n -1 4

=
!
-n+1 3n 4
3n 4

3n 4

=

n-4 2

2
n 4

2(n - 1)(n - 1)n-1 e -1 e
n - 4 +1



3n 2

e

- 3n 4

1 (1 + 4 ( n )) =

=

4

2(n - 1)(n - 1)n
n 4

-1 3n 4
3n 4

3 n ( n - 4 )

-1

n -1 4

1 (1 + 4 ( n )) =

4n 2 § § (1 + 4 ( n )). 3n 27n/4

. . , [ ]. . . . . ? n. ( [ ].) , n + 1 m . n + 1 n . , , - (. [ ]). : , m (n - 1)-! . . () n ½ n, ‘1 (. . n ). , .


. í í

-1 ( ) ( ) , , . n > 1 ( ...), , , . n. . , n > 3 , , , , . , . . n . 4 , n . 1 1 ... ... ... 1 -1 ... ... ... ... -1 1 ... 1 -1 ... -1 1 ... 1 -1 ... -1
.

, - , n, . , n - 1 , - (n - 1)- m . , , . , , > 0 n0 , n > n0 n (1 + )n n , n ½ n . [ ] [ ]. , , , . , , ( m ) n - 1 ( ) n = 4k ( m ) = n - 1. . . . , (G )
C 2C
n/2 n n/4-1 n-1

. . n = 4 a (
m

|V | , ( G )

)

=

2 + o(1) 1,754...

n

= (1,139... + o(1))n .

n (
m

)

(1,01... + o(1))n .


. .

, n (
m

)

(1,139... + o(1))n . ].

[ ( m ) = (1,139 + o(1))n ,

n . . , , íí íí íí n . , ( n ), , n , : (
n

) = min{ :

n

= V1 ... V , i x, y Vi |x - y| = 1}.

. [ , , ] [ , ]. ( n ) n . [ ] , (
n

)

(3 + o(1))n .

? , G íí n , ( n ) (G ). , n = 4 a (
n

)

(

m

) = (1,139... + o(1))n .

( n ) n ( o(1), ). (. [ ]). , (1,139... + o(1))
n

(

n

)

(3 + o(1))n .

. n . : (1,239... + o(1))n ( n ) (3 + o(1))n . , 1,139 1,239, , ë ¨. ,


. í í

, ( . [ ]). , . . . . (. [ , ]). , , íí . f (n), f , n f . , íí . , [ , , , ] [ í ]. . . . = ( m ). , W m , . , > ? , , W . ? r (W ) m W . , r (W ) = | F |, (., , [ , . . |W | = l > , r (W ) F = (x, y)
m

: x W, y W .

]) -

. . |W | = l (n + 1), (n) 0, n , r (W ) >
l 2 - n l + 1 n2 2
2

l l2 -. 2 2

(1 + ( n )).

, l n , , n = o(l ) . . , W A G = (W , F ), . = | A|. , . ,


. .

A, W \ A ( F ) A. W \ A L K . K íí , x K y A ( x , y ) F (. . ). , K = { x W \ A : |{ y A : ( x , y ) F }| = 1}, L = (W \ A) \ K = { x W \ A : |{ y A : ( x , y ) F }| 2}.

A

K
.

W

, | K | n . . x A, |{ y K : ( x , y ) F }| y1 , ..., yn
+1

n + 1.

{ y K : ( x , y ) F }.

yi , y j . M = ( A \ { x }) { yi , y j }. | M | > | A|, M G . , ( yi , y j ) F . , y1 , ..., yn+1 n , . . n- . ( , )-, , , , (. . . . ). . , | K | n n. , , F = ( x , y ) : x K , y A ( x , y ) : x L, y A ( x , y ) : x W \ A, y W \ A .


. í í

, F1 = ( x , y ) : x W \ A, y W \ A , | F | = |{( x , y ) : x K , y A}| + |{( x , y ) : x L, y A}| + | F1 | 2(l - ) - | K | + | F1 | 2(l - ) - n + | F1 | 2(l - ) - n + | F1 | = 2l - (n + 2) + | F1 |. , W W1 = = W \ A, A A1 ( W1 , ), 1 = | A1 | , L K L1 K1 , W1 \ A1 = L1 K1 , . . l1 = |W1 | l - F2 = ( x , y ) : x W1 \ A1 , y W1 \ A1 , | F1 | = |{( x , y ) : x K1 , y A1 }| + |{( x , y ) : x L1 , y A1 }| + | F2 | 2(l1 - 1 ) - | K1 | + | F2 | 2(l1 - 1 ) - n1 + | F2 | 2(l - 2) - n + | F2 | = 2l - (n + 4) + | F2 |. k =
k

l - n

. -

|F |

i =1

(2l - (n + 2i )) + | Fk |,
-1

Fk = ( x , y ) : x Wk

\A

k -1

, y Wk

-1

\A

k -1

.

, i {1, ..., k } |Wi | = |Wi-1 \ Ai-1 | l - i l - k n, , Li , ë ¨ G , | Ki | ni n. W0 = W , A0 = A . . , l (n + 1) k 1, i k . | Fk |. , , G Wk . , Wk Ak , Wk , G . , -,


. .

Wk \ Ak Ak . , Ak |Wk | - | Ak | l - k - | Fk |. . Wk . l - k - i (i íí ) | Fk |. , |Wk | n, , n.
n

| Fk | ,
k n

i =1

(l - k - i ),

|F |
k i =1

i =1

(2l - (n + 2i )) +
n

i =1

(l - k - i )

(2l - (n + 2i )) +

i =1

(n - i ) =

= k (2l - n) - k (k + 1) +
l - n - 2l 2 - 3l n l 2 - nl +

= =

n ( n - 1) 2 n ( n - 1) l - n l - n 1 (2l - n) - +1 + = 2 (l - n)2 + (l - n) 2 (n2 - n) + n 2 2 - (2l - n) - + = 2 122 1 122 l 2 - nl + 2 n n + 2 n 2 - l 2

- (2l - n) =



(1 + ( n )).

. . . . ë¨ - , . : G = (V , E ) íí ( ), |V | = 4n, n , (G ) n; , | E | 7n. -, |E |
16 n 2 4 n - 2 = 6n. 2n

7n íí . (. [ ]). | E | 6n, | E | 7n.


. í í

, G = (V , E ) íí . |V | = 4n W V , |W | n + 1, x , y W , ( x , y ) E . Q1 V , V , . , |Q1 | n. , Q1 V \ Q1 Q1 . , E 3n . V Q1 . G1 = (V1 , E1 ), |V1 | 3n W V1 , |W | n + 1, x , y W , ( x , y ) E1 . Q2 V1 , V1 , . , |Q2 | n. , Q2 V1 \ Q2 Q2 . , E1 2n . , , , , E 5n . , | E | 6n. , G íí . , íí , íí , . , . . , V \ Q1 Q1 . V \ Q1 íí W1 W2 . W1 , Q1 , W2 íí , . , |W1 | 2n, , | E | 3n, , 4n . 7n. , |W1 | > 2n. Q1 q , x1 , x2 , x3 W1 . - xi , x j , q Q1 xi , x j . , |Q1 |. , x1 , x2 , x3 , q . . , . . -, | E | 7n. ! -, -


. .

. c > 0

. , en n , en cn4/3 e
n

ne

c ln n ln ln n

,

c > 0.

! [ ].

. .
. , ë¨ . . , , , . . (n) = o(1), n G n (G ) (1,0005 + (n))n (G ) 11. ? , , , n , . , , , . , , , : . . , , . , . , , , n . , (n) , n . , , (1000) = -0,0005, n = 1000 : , . -


. í í

. - : n0 , n n0 n G , (G ) (1,0004)n (G ) 11. , , ( ). , (. [ ]). . . ), c = 1,999 = o(1), n . =
4 3
3/4

= 1,754... (.

c (c, 2). (n) = G = (V , E ) n , (G ) 11
2 + ( n) c
n

(G )

.

, c = 1,9990001
2 c

1,0005,

. , , , c > c. , , c = 1,9990001. n = 4 a , . (n) (n) = o(1). G ( m , p ), p = n , = 0,88. ,
,1 . c

, n ( n, , ). G ( m , p ) Xl , l G . Ym m . l = [(c )n ]. , n l < | m | = (2 + o(1))n , , , Xl . , , Pm, p ( Xl = 0) > 2 ,
1

Pm, p (Y12 = 0) > 2 .

1


. .
n

G , (G )

( G )
m

11 (G )
2 + ( n) c
n

l . ,

|

l

|

=

. , . : Pm, p ( Xl = 0) 1 - M Xl , M Xl <
1 , 2

Pm, p (Y12 = 0)
1 . 2

1 - MY12 .

, , MY12 <

MXl . , (. . . . ) M Xl =
W
m

, |W |=l

(1 - p )

r (W )

.

, , c > , l > = ( m ) (. . . . ) n, , , W m , |W | = l , r (W ) - (. 2 2 ,
l l2 - 2 2 ((c )2 + 1 (n))n = ( + 2 (n))n l
2

l

).
(c )2 + 3 ( n )
n

,

1 (n) = o(1), ,

2 (n) = o(1),
l
2

3 (n) = o(1).

A l = 2 - 2 , ( i (n) = o(1)) MX
l l C m § (1 - p ) A
l

l

em l

l

§ (1 - p ) §e
-p
(c )2

A

l

2 + 4 ( n ) c

(c +5 (n))n

+ 3 ( n )

n

=e

(c +6 (n))n -

§(c )2

+ 7 ( n )

n

.

>

§ (c )2 > c , . . . , c

( c + 6 ( n )) n - e

§ (c )2 + 7 ( n )
§(c )2

n

-,

(c +6 (n))n -

+ 7 ( n )

n

0.


. í í 1

, n MXl < 2 , 1 MY12 < . 2 MY12
1 Cm2 p C
2 12

1 = Cm2 p 66 m12 § 66n = (2 + 8 (n)) 8 (n) = o(1).

12n 66n



,

, 212 § (0,88) , n < (0,9 + 9 (n))n < 2 , 9 (n) = o(1). n (, n > n0 ) n = 4 a , n. n. , 4 n. n = 4 . , n G (G ) (1,0005 + (n ))n (G ) 11. n n , G n . . ? . , n - n = o(1) (. [ , ]). , MY12 (2 + 8 ( n )) (G ) (1,0005 + (n ))n = (1,0005 + (n - (n))) (n) = o(1). (1,0005 + o(1))
- ( n )


66

< 0,9.
1

12n 66n

n - ( n )

,

, (n - (n)) = o(1), . . (G ) (1,0005 + (n))n , (n) = o(1). . . . , . . , . , ? , (. . . . [ ]) . , , . = 1 + o(1),


. .

(. [ ]) , . : ? , : k k . [ ].

. .
. , , , . . , , , . . p G ( m , p ) 1 (n) = o(1) 2 (n) = o(1), (G ) (1,139... + 1 (n))n , (G ) (1,139... + 2 (n))n .

, , 1 2 . , , , , , , , íí .

. .
ë¨ (. ç . ). . . . , R(s, t ) m, G m (G ) s, (G ) t . , , , , . . G = (V , E ) íí . H = (W , F ) G , H G . , , H íí G (. . W = V ), , , H G . G = (V , F ) Km (. ., , G íí


. í í

m ), ( ) [G ] = (V , F ) Km , ( x , y ) F , ( x , y ) F . R(s, t ) : m, G Km G K s , [G ] K t . Km K s , : R(s, t ) íí m , G Km G Km s , [G ] Km t . G m . ( ) [G ]dist m , , G , m . , G = ( m , ) [G ]dist = m . . , , k . m p { mrime } { m }=1 m , k = a k a. s, t Rdist (s, t ) m , m G m G m s , [G ]dist m t . , Rdist (s, t ) R(s, t ), Km m . prime , , Rdist (s, t ) p m , m { mrime } G m G m s , [G ]dist m t . . , Km , ( -


. .

K s ), ë¨ m - s . , ë¨ (. . ), , . . . , m . Km K1 . prime Rdist (s, t ) Rdist (s, t ). . . . . , ë ¨, . . s = t . . c=
4 3
3/4

,

=

ln 2 , ln c

b=

35 243 = 1 6 . 42

> 0 s R
dist



( s, s)

16

2 (ln c )

1 2

-

b s (ln s )

-

1 2

(1 + ).

, , ë¨, , . prime Rdist (s, s) . . , (s) = o(1) s prime Rdist (s, s) s+(s) . (. ç . ). . . c= 1 =
1 , 4 3
3/4

,

=
2

ln 2 , ln c d
1 /2

d= ,
2

2 , 3

2 =

1 1 -, 2 2

3 =

(ln 2)

4 =

ln 2 23 ( - 1)
2



.

> 0 s, R
prime dist

( s, s)

4 s (ln s )

--1 2

(1 - ).


. í í

ë-¨. , , ë s¨ , , ë s. , íí , , . . . , (s) = o(1) s prime Rdist (s, s) s+(s). . . = R
ln 2 . ², ln 1,99

²(s) = o(1) s
dist

( s, s)

s

+²( s)

.

, Rdist (s, s) s. (. . . . ). . . . . , , , [ ]. . . . , s m m ( m ) s. G = ( m, E ) s. W , |W | = s, íí m (G ) m . , H = (W , E |W ) = (W , ) m G . , G , [G ]dist m s , , . , s n m = Cn /2 n = 4k m
ln

16

2 (ln c )

1 2

-

b s (ln s )

-

1 2

(1 + ),

(

m

)

s.

h( s) =

b s(ln s)(1+ ) ln c

ln c

,

0 < < .


. .

, s h(s) , , n n = 4k , h(s) + 4 h(s). m (
m

)

4

n+2
3n +5 4

n3

(1 + 3 ( n )) = =

1 cn § (1 + 3 ( n )) = bn 1 eh(s) ln c § (1 + 3 ( n )). b h( s ) + 4

1 en ln c § n (1 + 3 ( n )) b

s n, , 3 (n) = (s), (s) 0, s . , (
m

)

1 1 eh(s) ln c § (1 + ( s )) = § b h( s ) + 4 b

bs(ln s)(1 + )
ln
b s(ln s)(1+ ) ln c

(1 + ( s )) =
+4

(ln c)

ln c

=

s(ln s)(1 + ) ln
c4 b s(ln s)(1+ ) ln c

(1 + ( s )) =

s(ln s)(1 + ) (1 + ( s )), (ln s)(1 + (s))

(s) 0, s .

> 0, ( s) ( m ) > s. , . . , : m=
2 2n § (1 + 1 ( n )) n 2 § 2 § 1 h( s ) 1 h( s )
ln

2 2h(s)+4 § (1 + 1 ( n )) = h( s )
ln c

b s(ln s)(1+ ) ln c

= 16 = 16

§2 §

(1 + 1 ( n )) =


bs(ln s)(1 + ) ln c

(1 + 1 ( n )).

, h(s) m 16
2 § 1
ln s ln c

ln s s. , ln c


§

bs(ln s)(1 + ) ln c

(1 + 1 ( n ))
2 (ln c )
1 2

16 s ,


-

b s (ln s )

-

1 2

(1 + ),

(1 + ) (1 + 1 ( n )) .

1 + .


. í í

. . . . , . c, , d , 1 , 2 , 3 íí , . n = 4 a (
m

)

3 (ln m )2 m 1 (1 + 4 ( m )),

4 (m) 0, m .

. . .

m= , ln m n ln 2. 3 (ln m )2 m

1

2 2n (1 + 1 ( n )). § n
1 /2
n

3 n2 (ln 2)



2

2

c n

1/(2)

=

d § cn . n

, , , (
m

)

d § cn (1 + 4 ( n )). n

. , , > 0 . 4 a , íí , a íí . = {8, 12, 16, 20, 28, 32, 36, 44, 52, 64, ...}. m . n , = {70, 924, 12870, 184756, ...}. m s
--1 2

m = 4 ( s ) (ln s )

(1 - ) ,

=

. 2

s = s . s, . s m = m(s), . , m ( s ) 4 s (ln s )
--1 2

(1 - ), (1 - ).

. . s m ( s ) > 4 s (ln s )
--1 2


. .



, s0 s R
prime dist

,

( s , s ) > m = m ( s ),

. , s . m = m(s) m . , G m , , m , s . G ( m , 1/2). . . , W m , |W | = s, r (W ) W . , , AW íí , , G , m W . , Pm
,1/2

( AW ) = 2

1 2

r (W )

,
s
2

, , r (W ) 2 - 2 . , s > = ( m ): , ,
3 (ln m )2 m 1 (1 + 4 ( m ))
--1 2

s



3 ( ln s )2 4 1 s



1

(ln s )

§

1

(1 - )
s2 2



1

= O ( s (ln s )-1 ).

Pm

,1/2 W
m

A

W

2C

s m

1 2

-

s 2

.

, 2C , Pm .
m
s

s m

1 2

s2 2

-

s 2

< 1,

(1)

,1/2 W
m

A

W

> 0,

s Cm < s -s , ( ) se

2m s s s e-s

1 2

s2 2

-

s 2

< 1.


. í í



2m s s s e-s 1 2
s2 2

:
s2 23 (ln m)2 m1

-

s 2

2m s s s e-s

1 2

(1+

1 (m))

,

1 (m) = o(1),


2m s s s e-s 1 2
s2 23 (ln m)2 m1

(1+1 (m))

< 1.

, . , --1 m 4 s (ln s ) 2 (1 - ), ln m ln s . , ln 2 + s ln m - s ln s + s -
s2 (ln 2)(1 + 1 (m)) 23 (ln m)2 m1 - - 1 s ln ln s - s ln s + s - 2

ln 2 + s ln(4 (1 - )) + s ln s + -
s2 (ln 2)(1 + 2 (m)) 23 ( ln s)2 4 1 s
1

(ln s)

1

--1 2

=
(1 - 1 )
1 4
1

= ( - 1)(1 + 3 (m))s ln s - = ( - 1)s ln s (1 + 3 (m)) -

ln 2 2 3 2

§

(1 + 2 (m)) § s (ln s ) (1 - 1 )1

1 2

-

1 2

1 +2+

1 2

=

(1 + 2 (m)) (1 - 1 )1

<0

s. , , R
prime dist

( s, s) = m.

p , m < m, m { mrime }, . , , m, . , ,

R .

prime dist

( s, s) > m.


. .

. .
, , . , , m , . . . m1 = C
n/4 2 n/2

.

. . p =
c ln m1 . c > 1, m1

. c < 1, . . p = m . c < 1 1 = (c) > 0, ln m . c > 1 = (c) (0, 1), , m. ? , íí m1 n - 1 n. , . . . , , , .
c

. .
. G (n, p ). : G ( m , p ) ? , . , L, : ,


. í í

. : x1 x2 x3 x
4

( x1 x4 ) ( x2 x4 ) ( x3 x4 ) .

k1 , k2 íí . n ni = 4k i , mi = Cnii /2 . {k1 , n1 , m1 } m1 , x1 = (1, ..., 1, 1, ..., 1, 0, ..., 0, 0, ..., 0), x2 = (1, ..., 1, 0, ..., 0, 1, ..., 1, 0, ..., 0), x3 = (1, ..., 1, 0, ..., 0, 0, ..., 0, 1, ..., 1). k1 , x1 , x2 , x3 . ( ), , m1 . {k2 , n2 , m2 } . ( ), , m2 , x4 , . , > 1, x1 , x2 , x3 m2 Ax1 ,x2 ,x3 m2 , | Ax1 ,x2 ,x3 | > n2 , x1 , x2 , x3 . lim Pn1 , p (G L) = 0.
n 1

Pn
2

,p

(G L)

C

3 m

2

Pn

2

,p

( x1 , x2 , x3 x4 A
3 C m (1 - p 3 )
2

x1 ,x2 ,x

3

(( x 1 x 4 ) ( x 2 x 4 ) ( x 3 x 4 )))



n2

( m 2 )3 e

- p3

n2

.

, p , , . . p (m2 ) > 0. m2 = = (2 + o(1))n2 , , p , . , , , p 3 n2 > n2 /2 , ,
n 2

lim Pn

2

,p

(G L) = 1.

.

, lim Pn, p (G L) ,
n


. .

, , , . . , , ( ) j , . . , .


. -
, íí , , . . - , , , . .. . . , - . . íí . . . , íí . íí .

. . íí
[ í ] , . , íí , , . , (, , .) ë¨. , , . -, : , , , . , - . , . , . , . , - , (


. . í í

). ë¨. , ë¨ íí . íí . , . -, - íí . t k t , k 1 íí . , t Ct2 = (t 2 ) (. ë¨ ). íí -, íí - . (, íí , íí .) (. [ ]) íí . , ë ¨. , , ë íí ¨. : ë¨ , íí . , . . , - , . , - : , , , . -, - . , - d (. . d ), c/d , 2,1, c íí , ë ¨. íí , , . ë ¨ (. . , c/d ), . , íí . p ( ), , . G (n, p ) n - 1 p (. . . . ), p , -


. -

- (. . p = (1/n)), , . . , , , . ? , , . , , , . , , . , . . , . . . f (n), n 2, íí , f (2) = 0, f (n) f (n + 1) f (n) + 1 n 2 f (n) n . íí , , n , f (n) .

íí . . . .

. . íí
[ ] [ ]. [ ]. , , . , . , . . . .
n () {G1 }, n n.


. . í í
n {Gk }, n n, k n, k . 1 , G1 = ({1}, {(1, 1)}), . . n . G1 -1 . {1, ..., n - 1}, n - 1 . n (n, i ),

(n, i ) 2n - 1 , deg i íí n i G1 -1 . , ,
n -1 i =1

i {1, ..., n}. (n, n) 2n - 1 ; deg i

1

deg i 1 2n - 2 1 + = + = 1. 2n - 1 2n - 1 2n - 1 2n - 1

n G1 , . k n Gk . G1 n . k n k n . k :

{1, ..., k },

{k + 1, ..., 2k },

...,

ë¨, , . . , , íí . íí , . n, íí - k n. . . . . , LCD- , . -, (., , [ ]), -. , 2n : 1, 2, 3, ... ..., 2n. , , . (linearized chord diagram , , LCD -). , , . LCD . ln =
(2n)! . 2n n !

{k (n - 1) + 1, ..., k n}.


. -

LCD n n . . , - . i1 . {1, ..., i1 } . i1 + 1 i2 . {i1 + 1, ..., i2 }. . n , n . . , , . . . n, n (. . ).

1

2

3

4

5

6

7

8

9

10 11 12

{5, 6}

{7} {1, 2, 3, 4} {8, 9} {11, 12}
.

{10}

LCD , . . 1/ln . . , n G1 . n k n , . . . . íí , ë¨, ë¨ , , .


. . í í



. k
ln n ln ln n

2 > 0
n k

P (1 - )

diam G

(1 + )

ln n ln ln n

1,

n .

, . , : ( ) ln n/ ln ln n. - íí ? . 107 . ,
ln 107 7 ln 10 6. = ln 7 + ln ln 10 ln ln 107

. , . [ ] . [ ] . . k 1 d n1/15 M
i = 1, ..., n : indegGn i = d
k

n



2 k ( k + 1) , (d + k)(d + k + 1)(d + k + 2)

(2)

indegG n i íí , i k n Gk . k íí , ( ) const/d 3 . ! , , , (. . [ ]). . , d , , 2,1, . íí d n1/15 , . n 1012 , () , d 104/5 , . . . íí - , d . , ( ) d = o(n). . , , .


. -

. . LCD-. n H íí . ( H , Gk ) n , Gk , H . ? . , [ ] , . . k 2. K3 íí .
n M ( K3 , Gk ) = (1 + o(1)) §

n . . k l .

k § ( k - 1) § ( k + 1) § (ln n ) 48

3

2l

3. Cl íí
l

n , ck,l íí . , k ck,l = (k l ). . . ( , ) . . H , d1 , ..., d s . (di = m) H , m.
n M ( H , G k ) = n (di =0)

n M (Cl , Gk ) = (1 + o(1)) § ck,l § (ln n)

§ ( n)

(di =1)

§ (ln n )

(di =2)

.

k . , [ ], . . , K3 . , K3 (di = 0) = (di = 1) = 0,
n M ( K3 , Gk ) = ((ln n)3 ),

(di = 2) = 3.

. ( ). K4 íí , íí , - . , ë¨ .


. . í í

, , . , , , . íí , . k = 1. LCD-. . . . k = 1

ë¨ . . di íí i n n G1 , . . di indegG1 i , . Dm = d1 + ... + dm . { Dm - 2m = s}, 0 s n - m. , n , n - m G1 s - m . , m G1 2m, , , s m Dm G1 . , , , m- 2m + s. . ë¨, . . ln (. . . . ) , : ) 2m + s ; ) - s {1, ..., 2m + s - 1} - s {2m + s + 1, ..., 2n}, s ( {1, ..., 2m + s - 1} íí {2m + s + 1, ..., 2n}) ( s!); ) {1, ..., 2m + s - 1} ( 2m - 2) - (), {2m + s + 1, ..., 2n} ( 2 n - 2 m - 2 s ). P ( Dm - 2m = s) =
s!(2m + s - 1)C
s l 2m+s-2 m-1

C

l

s l 2n-2m-s n-m-s s+1

=

n

=

2

(2m + s - 1)!(2n - 2m - s)!n! . s!(m - 1)!(n - m - s)!(2n)!


. -

ë ¨ Dm - 2m, . . s, ps = P ( Dm - 2m = s). rs = ps+1 / ps : rs = p = 2 (s + 1)(2n - 2m - s) . s , , rs . ? , ps , , , . , rs 1. rs = 1, s. , rs , rs = 1 . ,
rs+1 = rs ps+1 (2m + s)(n - m - s)

1-

2m - 1 (s + 2)(2m + s)

n-m (2n - 2m - s - 1)(n - m - s) 2m - 1 n-m - 2m-1 1- 1- e 2n2 § e 2 2 2n 2n

1-

-

n-m 2n2

e

-

1 2n

.

rs . , , rs = 1, . s0 = -2m + 4mn - 2n + 1/4 + 1/2 ,

ps . Dm - 2m . . , rs0 1. , x > 0 rs
0

+x

rs

0

+ x -1

e

-

1 2n

rs

0

+ x -2

e

-

2 2n

...

rs0 e

-

x 2n

e

-

x 2n

.
x ( x -1) 4n

p
s0 + x

p

s 0 + x -1

e

-

x 2n

p

s 0 + x -2

e

-

x 2n

e

-

x -1 2n

...

ps 0 e
s0 - x

-

x ( x -1) 4n

e

-

.

p n P | Dm - (2m + s0 )| 3 n ln n 2e

. , =o n .
1

-

8n ln n 4n

m s 0 - 2 m n - 2m 2 n,


. . í í

P Dm - 2 mn 4 n ln n = o n ,
1

. . Dm m 2 mn. P indeg
G
n 1

(m + 1) = d | Dm - 2m = s = P d

m +1

= d + 1| Dm - 2m = s .

Dm - 2m = s , LCD . , 1, ..., 2m + s - 1 A s, , - 2m + s + 1, ..., 2n; {1, ..., 2m + s - 1} \ A , , 2m + s; 2m - 2 - -. s ë¨ LCD s!C2n-2m-s ln-m-s . . t LCD dm+1 = d + 1, : ) 2m + s + d + 1 , B = {2m + s + 1, ..., 2m + s + d } ; ) A B ( s + d ) x 2m + s + d + 1; ) {2m + s + d + 2, ..., 2n} ( 2n - - 2m - s - d - 1) C , s + d - 1 , A B \ { x }; ) {2m + s + d + 2, ..., 2n} \ C ( 2n - - 2m - 2s - 2d ) . , t = ( s + d )C
s + d -1 ( 2 n -2 m - s - d -1

s + d - 1)!l

n- m- s - d

.

s + d íí x , íí C , (s + d - 1)! A B \ { x } C , ln-m-s-d .


. -

, Pd
m +1

= d + 1| Dm - 2m = s =

( s + d )C

s+d-1 (s + d - 2n-2m-s-d-1 s s!C2n-2m-s ln-m-s

1)!l

n-m-s-d

=

= 2d (s + d ) (2n - 2m - s) , d+1

(n - m - s)d

( a) b =

a! . (a - b)!

m, d s . 1 ( 2 ). , M = [n4/5 / ln n]. m M m n - M . d 0 d n1/15 . s 2m + s = D , D íí , | D - 2 mn| 4 n ln n. , D íí Dm . , 1 s + d = D - 2m + d = 2 m n - 2m + O = 2 m n - 2m + O n ln n , n ln n , n ln n + O n
1/15

=

n - m - s = n + m - 2 mn + O

.................................................. n ln n ,

n - m - s - d = n + m - 2 mn + O

- . 2n - 2m - s = 2n - 2 m n + O n ln n ,

............................................ n ln n

2n - 2m - s - d = 2n - 2 m n + O

-. , Pd
m +1

= d + 1| Dm - 2m = s = = 2d 2 m n - 2m + O n ln n
n + m - 2 mn + O 2n - 2 m n + O n ln n n ln n

d

d+1

.

, , 2 m n - 2m + O n ln n 2 m n - 2 m .


. . í í

, , n + m - 2 mn + O 2n - 2 m n + O n ln n n ln n
d d +1

n + m - 2 mn , 2n - 2 m n
d +1

d

.

, , . , n + m - 2 mn + O n ln n
d

=
d

= n + m - 2 mn , 1+O
n ln n n + m - 2 mn
d

1+O

n ln n n + m - 2 mn

d

.

e

O

d n ln n n+m-2 mn

,

,
d n ln n 0. n + m - 2 mn

m

n - M ,
d n ln n n- m
2

d n ln n = n + m - 2 mn

=

d n ln n n 1-
1 n1/5 ln n 2 m n 2

d n ln n n 1- d n ln n n O n2/51ln2 n (ln n)5 n1/30
/2 n- M n 2

=

=
n 1- n
1/15

d n ln n 1-O

=

=

=O

n ln n ln2 n n3/5

=O

= o(1).

. , P (d
m +1

= d + 1| Dm = D )
2 m n - 2m 2m - 2 m n 2 n- m 2 n - mn
2

d



m 1- n

m n

d

,

D 1 , . . D , D - 2 mn 4 n ln n. , ,


. -

(. ç . ) P (d
m +1

= d + 1) = +
D : | D -2 mn|>4 n ln n

P (d
D : | D -2 mn| 4 n ln n

m +1

= d + 1| Dm = D ) P ( Dm = D ) +

P (d
m n m n

m +1 d

= d + 1| Dm = D ) P ( Dm = D ) = P ( Dm = D ) +

= (1 + o(1)) +O

1-

D : | D -2 mn| 4 n ln n

P ( Dm = D )
D : | D -2 mn|>4 n ln n

=

= (1 + o(1)) 1
D : |D -2 mn| 4 n ln n

m 1- n

m n

d

+ o(1/n),

P ( Dm = D ) = P | Dm - 2 mn|

4

n ln n

(1 - o(1/n)) 1,
D : |D -2 mn|>4 n ln n

P ( Dm = D ) = P | Dm - 2 mn| > 4
1

n ln n = o(1/n).

, m, d , s P (d
m +1


d

= d + 1) = (1 + o(1))

m 1- n

m n

+ o(1/n).

m + 1 m [ M , n - M ] dm+1 = d + 1 ( - 1 ). M =
n- M m= M

P (d

m +1

= d + 1) = o(1) +

n- M m= M

(1 + o(1))

m 1- n

m n

d

.

M : M i = 1, ..., n : indeg
G
n 1

i=d

=
n- M m= M

= O ( M ) + o(1) + (1 + o(1))

m 1- n

m n

d

.


. .

( ),
n- M m= M

m 1- n

m n

d

n
1- M /n ( M +1)/n 1

v (1 - v ) d d v n

0

v (1 - v ) d d v .

v = (1 - u)2 :
1 0 1

v (1 - v ) d d v = 2 (1 - u )2 u d d u =
0 1

= 2 ( u d - 2u
0

d +1

+u

d +2

) du =

4 , (d + 1)(d + 2)(d + 3)

, , M i = 1, ..., n : indeg
G
n 1

i=d

=
4n 4n , (d + 1)(d + 2)(d + 3) (d + 1)(d + 2)(d + 3)

= O ( M ) + (1 + o(1)) .

. .
, . íí . . , . , . , . , . . (. [ ]). (0, 1) d 1, d . , . . . -. d - (, d ). t . Gt = (Vt , Et ). Vt = {u1 , ..., u s }, s t , . . , d . Gt u s+1 d , u s+1. p Vt ( Vt ). u s+1 Vt . i , i {1, ..., d },


. -

, (ë ¨) 1 - (ë ¨). , u s+1 Vt ( Vt ). , i - p . , d . . . , - . , . , ( , ). , ( p íí , ). , ( ) - . . , 1 - íí , , , . [ ] íí . . Nt ,r íí r Gt . = r lim t t
N
t ,r

-

2- 1-

.

, . , ( íí ), 2,1, . íí . . , íí (. ); . , , . . , .


.
, . , , . f g n. f = o( g) f (n) = o( g(n)) ( ë f - g¨), = (n), n f (n) = (n) g(n). g n, n . , . . ) f (n) 0 n , f = o(c), c íí . f = o(1). f = o(2) . ) , n = o(n2 ), n2 = o(n3 ), . . ) 2 o(2n ) . , n = o(2n ), n 2 n = 2n-log2 n = 2o(n) , n - log2 n = o(n). )
o(n)

f (n ) 0 g (n )

2

n

f (n) = (2 + o(1))n ,

f (n) = (3 + o(1))

n

. .

, = o(1), . , , , , f (n) = (2 + o(1))n , f (n) 2n . , f ( n) = 2 + n
1
n

= 2n § 1 + 2 n

1

n

,

e (. . f (n) , 2n ). f ( n) = 2 +
1 n
n

= 2n § 1 +

1 2n

n

,

f (n) n e n/2 , . . .


.

ë-¨ ë¨: (1 + o(1))(2 + o(1)) = 2 + o(1), (3 + o(1))
n-o(1)

(1 + o(1))
37

17-o(1) n

= 1 + o(1),

= (3 + o(1)) ,

n

n (2 + o(1)) = (2 + o(1))n , ...

(4 + o(1))n = (2 + o(1))n , (2 + o(1))n

. íí f = O ( g) ( ë f - g¨). , c > 0, n | f (n)| c| g(n)|. c ! O (1) O (10000) . ., . . ) f = o( g), f = O ( g). : f (n) = n, g(n) = n/2. ) , n = O (n), n2 = O (n2 + n), . . f = ( g). , g = O ( f ). , f = ( g) , f = O ( g) f = ( g), . . f g , n . n2 = 2n2 + n . íí f g ( ë f g¨). , f (n) = g(n) + o( g) , , f (n) = (1 + o(1)) g(n). g(n) = 0, ,
f (n ) 1. , n2 n2 + n g (n )

2+

1 n

n



e § 2n .

ln(1 - x ) - x ln(1 - x ) = O ( x ), 1 - f ( n) = 1 + O ( f ) f = o(1).



. . . . . . . . . . . . . . . . . . . . . . . . . . . ‡ Bollobas B. Random Graphs. nd ed. Cambridge Univ. Press, . . . . .: , . ‡ Janson S., Luczak T., Rucinski A. Random graphs. Wiley, NY, . Durrett R. Random Graph Dynamics. Cambridge Univ. Press, . . . . .: , . . . . .: , . . . .: , . . ., . ., . . . .: , . . . í . í .: , . . . // í í . .: , . . . . . . .: , . . . .: , . . . .: , . ., . . .: , . . . .: , . . . .: , . . . . : , . . . : - . ., . . . . .: , . Erds P., R‡nyi A. On random graphs I // Publ. Math. Debrecen. . V. . o e í í . P. Erds P., R‡nyi A. On the evolution of random graphs // Publ. Math. Inst. o e í Hungar. Acad. Sci. . V. . P. í . Erds P., R‡nyi A. On the evolution of random graphs // Bull. Inst. Int. Statist. o e í í . Tokyo. . V. . P. ., . . .: . , . Ledoux M. The concentration of measure phenomenon // Mathematical Surveys and Monographs . AMS, . Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph í theorem // Ann. of Math. . V. , . P. í . Ramsey F. P. On a problem of formal logic // Proc. London Math. Soc. Ser. . í í . . V. . P. P. Erdos, Szekeres G. A combinatorial problem in geometr y // Compositio í í Math. . V. . P. .




. Graham R. L., Rothschild B. L., Spencer J. H. Ramsey theor y. nd ed. NY: John Wiley and Sons, . . . . .: , . . . . . .: , . . . . - . .: , . . http://en.wikipedia.org/wiki/Ramsey's_theorem. . . . . .; : , . . Conlon D. A new upper bound for diagonal Ramsey numbers // Ann. of Math. í í . V. . P. . . . ., . . .: , . . . ., . ., . . . .: , . . . . // , .: í í. , . . . Barbour A. D. Poisson convergence and random graphs // Math. Proc. Camb. í í Phil. Soc. . V. . P. . . ., ., . . .: , . . Hopcroft J., Wong J. Linear time algorithm for isomor phism of planar graphs // Proceedings of the Sixth Annual ACM Symposium on Theor y of Computing. í í. , P. . Booth K. S., Lueker G. S. Testing for the consecutive ones proper ty, inter val graphs, and graph planarity using PQ-tree algorithms // J. Comput. System í í Sci. . V. . P. . . Booth K. S., Lueker G. S. A linear time algorithm for deciding inter val graph í í. isomor phism // Journal of the ACM. . V. , . P. . Luks E. M. Isomor phism of graphs of bounded valence can be tested in polynomial time // Journal of Computer and System Sciences. . V. . í P. í . . . . . .: , . . . . . .: , . . . . í í. // . . . . , . . . Raigorodskii A. M. The Borsuk par tition problem: the seventieth anniversar y // í Mathematical Intelligencer. . V. , . P. í . . . . // . ë ¨. . í í. . . . . . : , // . . . . .




. Sz‡kely L. A. Erdos on unit distances and the Szemer‡di í Trotter theorems // e eí Paul Erdos and his mathematics (Budapest, ). Budapest: J. Bolyai Math. í í Soc., . (Bolyai Soc. Math. Stud.; V. ). P. . . Brass P., Moser W., Pach J. Research problems in discrete geometr y. Springer, . . . ., . . . .: , . . Boltyanski V. G., Martini H., Soltan P. S. Excursions into combinatorial geometr y // Universitext. Berlin: Springer, . . Frankl P., Rèdl R. Forbidden intersections // Trans. Amer. Math. Soc. o . í í V. . P. . . Horadam K. J. Hadamard matrices and their applications. Princeton University Press, . . . . . .: , . . Larman D. G., Rogers C. A. The realization of distances within sets in Euclidean í space // Mathematika. . V. . P. í . . Frankl P., Wilson R. Intersection theorems with geometric consequences // í í Combinatorica. . V. . P. . . Aigner M., Ziegler G. M. Proofs from THE BOOK. Berlin: Springer-Verlag, . . . ., . ., . ., . ., . ., . . // . í í . . . . . . . . ., . . // . . . . , í í . . . . . . .: , . . . . . .: , . . . ., . ., . . // í . . . . í . . . ., . . {0, 1}n // . . . . , í . . í . ‡ . Barabasi L.-A., Albert R. Emergence of scaling in random network s // Science. í í. . V. . P. ‡ . Barabasi L.-A., Albert R., Jeong H. Scale-free characteristics of random netí work s: the topology of the world-wide web // Physica. . V. A . P. í . ‡ . Albert R., Jeong H., Barabasi L.-A. Diameter of the world-wide web // Nature. í í. . V. . P. ‡ . Bollobas B., Riordan O. Mathematical results on scale-free random graphs // í Handbook of graphs and network s. Weinheim: Wiley-VCH, . P. í . . . . . .: , .




. Stoimenow A. Enumeration of chord diagrams and an upper bound for Vassiliev í. invariants // J. Knot Theor y Ramifications. . V. , . P. í ‡ . Bollobas B. Riordan O. The diameter of a scale-free random graph // Combií natorica. . V. , . P. í . ‡ ‡ . Bollobas B., Riordan O., Spencer J., Tusnady G. The degree sequence of a scalefree random graph process // Random Str uctures Algorithms. . V. , . í í P. . . Kumar R., Raghavan P., Rajagopalan S., Sivakumar D., Tomkins A., Upfal E. Stochastic models for the web graph // Proc. st Symposium on Foundations of Computer Science. .


. . . 60 ½ 90 / . . . . . , . . . . , , ., . . . ( )

í

í

O ë "¨. "
ë ¨, ., . . . ( ) í í . E-mail: biblio@mccme.ru