Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 15, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Dieter Mitsche
In 1998 Alon, Krivelevich and Sudakov showed how to find a clique of size k=c √n in a random graph G(n,1/2,k), which is generated in the following way: add each edge with probability 1/2 independently, then choose a random subset Q of size k and force it to be a clique by joining each pair of vertices of Q with an edge.
This talk generalizes the problem of reconstructing a clique in the G(n,p,q,k) model: choose a random subset Q of size k; each edge incident to two vertices of Q is included with probability p, each other edge is included with probability q, where p > q.
Automatic MiSe System Software Version 1.4803M | admin login