G(n,p） ® V=n Vu,v∈V independently Pr[{u,v}EE]=p uniform random graph:G(n
|V | = n ⇥u, v V G(n, p) independently Pr [ {u, v} E ] = p uniform random graph: G(n, 1 2 )
G(n,P) Probability space: 2(g) Pr[G]=plGl(1-p)(3)-IGI
G(n, p) Probability space: 2( [n] 2 ) Pr[ G ] = p|G| (1 p)( n 2)|G|
Threshold Pr[G(n,p)has property P] 1 p 0 1
Threshold p Pr[G(n, p) has property P] 0 1 1
Threshold Property P p(n)is a threshold for property P: p=o(p(n)) Pr[G(n,p)has P]=o(1) p=w(p(n)) Pr[G(n,p)has P]=1-o(1)
Pr[G(n, p) has P ] = 1-o(1) Pr[G(n, p) has P ] = o(1) Threshold Property P p(n) is a threshold for property P: 㱺 㱺 p = o(p(n)) p = (p(n))
Property k-clique:contain a k-clique as a subgraph. Theorem The threshold for k-clique is f(n)=n-2/(k1) p=o(f(n)) Pr[G(n,p)contains a k-clique]=o(1) p=w(f(n)) >Pr[G(n,p)contains a k-clique]=1-o(1)
k k 2/(k1) k k k Property -clique: contain a -clique as a subgraph. Theorem The threshold for -clique is p = o(f(n)) p = !(f(n)) f(n) = n Pr[G(n, p) contains a -clique] = o(1) Pr[G(n, p) contains a -clique] = 1 o(1)