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 be a constant.
prove that whp a random graph G(n,m) (random graph with n vertices and m edges), with 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 such that 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)
- the biggest group of independent vertices of G
- the biggest klik G
next questions soon
10x