1)

let G~ be a random graph process

(random graph process -

taking all possible edges in G of n vertices,

giving them order by a member of S(n*(n-1)), and at each stage adding the next edge

)

prove that **whp** (with high probability) in G~ the first triangle appears before the graph is connected

2)

let $\displaystyle \epsilon>0$ be a constant.

prove that **whp** a random graph G(n,m) (random graph with n vertices and m edges), with $\displaystyle m=n*(1+\epsilon)$ is not planar

(planar - the graph can be drew on 2D without any edges crossing each other)

3)

let H be a graph with a cycle.

prove that there exist a constant $\displaystyle a=a(H)>0$ such that $\displaystyle t(n,H) >= n ^ \((1+a)$ for all suficently large n.

where t(n,H) is the Turan number of H, which is the maximun number of edges in a H-free graph on n vertices

4)

prove that **whp** in G(n,0.5) (G(n,p) - a random graph with n vertices and a probability of p to generate each edge. the probability is independent)

$\displaystyle a(G),w(G) = (1+o(1))2 * ln(n)/ln(2)$

$\displaystyle a(G)$ - the biggest group of independent vertices of G

$\displaystyle w(G)$ - the biggest klik G

next questions soon

10x